Overview

On this page, you can find more details on:

1. Source and Collaboration policy (or how not to get an F in this course);
2. Preparing your homework submissions (or how not to get a zero on a question);
3. Grading details (or what to expect on how your homework submissions will be graded);
4. Other helpful tips (or how to do better on the homeworks and in the course).

Source and Collaboration policy

Allowed sources

You can ONLY use the following sources for reference once you start working on the homework problems:

1. the Kleinberg-Tardos textbook,

   Other textbooks are not allowed

   While you can use other textbooks (e.g. those listed in the syllabus) to better understand the lecture material, you cannot use them once you start working on the homeworks.

2. any material linked from this webpage or the CSE 331 piazza page (including any discussion in the Q&A section),

   One-click rule

   When using webpages that are allowed as sources, you cannot click on the links in that source. (Otherwise within a constant number of clicks one can reach any webpage one wants.)

3. specific mathematical results from a previous course,
4. anything discussed in the lectures, recitations and/or office hours and
5. any notes that you might have taken during class or recitation.

Note that the above restriction applies to all questions on the homeworks (including the programming question).

In order to ensure compliance with this, here are the various rules you will have to follow:

• For every question in a HW that you submit, you will have to explicitly cite which one of the above sources you used. You will do this when you submit your submissions online on Autolab. If you did not use any of the sources (which is of course also fine), then just state None as your source.
• If while writing up your solution for a question you think you should cite some other source than the ones allowed above, it means you have consulted a source that was not allowed. In such a case, do not submit the question. If you are unsure, see the procedure outlined below.
• You will not be able to submit your HW if you do not choose the appropriate source for each of the questions in the HW that you submit your solution for.
• In the spirit of trust but verify, there will be specific questions in the Homeworks that are specifically designed to see if you used a source other than those allowed. Note that if you can find a solution easily online, then so can we!

Collaboration policy

Collaboration is generally allowed on the non-programming questions on the homeworks. Here are the policies regarding collaboration:

1. You are allowed to collaborate provided you have thought about each problem for at least 30 minutes on your own. This will help you in the exams.
2. You can collaborate on any homework in a group of size at most 3, including yourself. Note that you cannot collaborate with different groups for different problems.
3. You must write the name of everyone in your group on your submission. You will have the ability to do this in your Autolab submission.
4. You can only discuss the problems with your group till you come up with the ideas (e.g. proof ideas): the details (e.g. the formal proof) is something you should work on alone.
5. Your submitted homework must be written in your own words. Everything, including the proof idea, has to be written up individually. In particular, at no point of time should you have in your possession the written homework of someone else.

Some clarifications

In addition to your collaborators, for your Homeworks you can talk to:

• the instructor and the TAs;
• any other student in the class (who is not a collaborator) but only up to the extent of understanding the statement of a question on a homework. You are not allowed to discuss your solutions or solution ideas with students who are not your collaborators.

Other than your collaborators and the two rules above, you should not discuss the homework questions with anyone else (including but not limited to tutors and students who have taken CSE 331 before).

Preparing your homework submissions

Please keep the following points in mind when you are working on writing up your solutions (note that not following some of them will result in you losing ALL points irrespective of the technical merits of your solution):

• We encourage you to typeset your homework using some text editor-- this is not mandatory though. However, if you are writing up your homework, please make sure that your handwriting is legible and the PDF scan of your submission is legible.

  Be warned

  We reserve the right to deduct up to $100\%$ of the total points for submitted work that is hard to read (either due to the handwriting or the quality of the scan).

• When a problem asks you to give an algorithm, we expect you to analyze the correctness and running time of the algorithm.

  What is an efficient algorithm?

  By default, an efficient algorithm means one that runs in polynomial time.

• Remember that when solving a problem, you can only use the information given in the problem statement. For example, you may not use information that is "common knowledge" but not specified in the problem statement. If for some reason, you want to assume something, please state it explicitly at the beginning of your answer. However, note that it will be up to the grader's discretion whether your assumption is reasonable. (See next point.)
• Be very precise in what you write in your answers. Given a statement that could mean either (i) you did not get the main idea or (ii) you got the main idea but were not precise enough in stating it; the grader will assume that you did not get it.
• When a problem asks for a proof, we ask you to divide up your proof into two parts: the first (typically smaller) part will spell out the main idea(s) in your proof and the second (typically longer) part will contain all the details of the proof. For example, the first paragraph in the proof of $(1.3)$ in the textbook is the proof idea, while the second paragraph has the entire proof. (For more examples see some of the pages on the CSE 331 support page.) By default, the Proof idea part will be worth at least $50\%$ of the points for the proof.

  Avoid getting a $0$ on a question

  You will get a ZERO if you only present the proof details without the proof idea (even if your detailed proof is correct). On the flip side, if you make a mistake in the details of your proof, you are guaranteed a certain fraction of the grade if you had the right proof idea. For your convenience, we will provide LaTeX and Word templates for Q1 and Q2 on all homeworks. But remember that all submissions have to be in PDF.

  Also a proof written in English is much easier to understand than one that is heavy with mathematical notation. For this reason, we ask you to write your proofs in as much English as possible. This can be a bit confusing so for more clarification see the following video by Alan Cline :
• An algorithm that is stated in English is easier to understand than one written in pseudocode. However, pseudocode is sometimes better, especially for a precise definition. We ask that you divide your algorithm description into two parts along the lines of proof idea/proof details. An algorithm idea will provide an English description/summary of your algorithm and then the algorithm detail provide the pseudocode if necessary. (See CSE 331 support pages for more examples.)

  Avoid getting a $0$ on a question

  You will get a ZERO if you only present the algorithm details without the algorithm idea (even if your detailed algorithm is correct). For your convenience, we will provide LaTeX and Word templates for Q1 and Q2 on all homeworks.

• The only results that you are allowed to quote without proof are those that appear in the book (or were covered in class). Solved exercises in the book are considered as such results but unsolved exercises are not. Results from previous homeworks are also allowed. All other results that you use in your homework must be proved. (Also results that you have seen in your earlier courses such as discrete math and data structure are permissible. However, for such results you are required to give a reference.) Using a result other than those above, will result in deduction of points. To be on the safe side, it is always good to give a reference for any result that you might be using.

  Re-use allowed results as you would use libraries when you code

  There always seems to be some confusion on this so let me re-state this: if you want to use a result with a proper reference (as outlined above), then you are strongly encouraged to do so. Just like you are encouraged to use existing libraries while coding (to save yourself work among others), you should try and re-use existing results. This is also strongly encouraged in the exams, i.e. you can quote a HW problem in the exams with proof (excluding the quiz 2 and final exam).

• Typically we will not take in re-grading requests, especially if it is of the form of not agreeing with the partial credit given. For each homework, we will provide the grading rubric that was used, so please consult that first before going to the TA with a grading question. However, if there is a genuine reason for re-grading (e.g. your correct algorithm was marked as incorrect), please contact the TA within a week of when the graded material is handed back in Autolab.
• If you are stuck thinking about a problem on the homework, we strongly encourage you to go and talk to the instructor and/or the TA and/or post a comment on piazza. However, please be aware that you might not get a response if you contact us after 5pm on the day before the homework is due.

• No late submissions are accepted

  No homework will be accepted after 8:00am the Monday it is due. This time deadline will be strictly enforced by Autolab.

  Avoid getting a $0$ on a HW

  Unfortunately, every year there are cases where students forget about the deadline and ask to be able to submit their homeworks after Autolab is no longer accepting submission. If you have put in a lot of time working on the homework, then you owe it to yourself to make sure you submit before the deadline (you are encouraged to submit well before the deadline and note that you can submit multiple times). Under no circumstances will I accept a late submission.

Grading details

Submitting your homework

We will be using Autolab for homework submission and grading. In particular,

1. The third question will be a programming assignment and will be auto-graded by Autolab.
2. The other two questions will be for designing algorithms and/or analyzing its correctness. You will submit your solutions for the two questions (and each of their two parts) separately as PDF documents: i.e.

   4 PDFs to submit!

   If you are submitting everything then you should have to upload four (4) PDFs: one each for Q1 part (a), Q1 part (b), Q2 part (a) and Q2 part (b).

   Typeset homeworks are preferred but we will accept handwritten homeworks that are scanned as PDF. The TAs will grade the submitted homeworks and add grading notes on your Autolab submission that you will be able view on Autolab itself.

   PDFs cannot be more than 3MB

   Please note that Autolab will not accept files of size more than 3MB. This is almost never an issue if you are typesetting your homeworks but it can be an issue if you are scanning your handwritten solutions. If you are beyond 3MB, then you will need to compress your PDF file: if you do not know how, just Google it .

Grading scheme

We now outline the general grading framework that we will use for all homework submissions. Note that this framework by necessity is abstract: the actual interpretation of the abstract "levels" below will depend on the actual problem on hand. Next we present the framework for the programming assignment followed by those for the non-programming question.

Grading guidelines for programming question

1. Each programming question will have $10$ test cases:
   • $4$ easy test cases
   • $4$ medium test cases
   • $2$ hard test cases
2. Passing of each test case will get you $10\%$ of the points (and no points if your submission fails a test case). Note that a submission that does not compile automatically means the code failed all test cases.
3. Your entire submission will also have a timeout limit (this is to make sure you are implementing an efficient algorithm): if your code does not complete all test case within the timeout limit then that would count as your code failing all the test cases. However, if you want to run your code on fewer than all test cases you will have that option on Autolab.
4. Autolab will automatically grade all the programming assignments using the rubric above.
5. We will release $3$ test cases along with the HW ($2$ easy and $1$ medium test case(s)). All the other $7$ test cases will be not given to you before your final submission.

Grading guidelines for non-programming questions

There will be two questions that will not be programming based and will be graded manually by TAs as follows:

1. For each question, the student’s submission will be graded at one of the following levels:
   • Level 0: This mean the student get $0\%$ of the points. This is for submissions where the student shows zero comprehension: either in understanding the problem or of its algorithmic solution.
   • Level 1: This means the student gets $25\%$ of the points. This is for submissions where the student does show some comprehension of the problem and/or the required algorithm/solution but there is at least one flaw that cannot be repaired.
   • Level 2: This means the student gets $50\%$ of the points. This is for submissions where the student gets the main idea but there are still flaws that can be repaired but only with a lot of extra work.
   • Level 3: This means the student gets $80\%$ of the points. This is for submissions where the student has got the main idea but the execution is a bit faulty. However, these faults could be fixed without too much extra work.
   • Level 4: This means the student gets 95% of the points. The solution is almost perfect but the student forgot to handle a weird corner case.
   • Level 5: This means the student gets 100% of the points. Absolutely flawless submission.
2. A level will be assigned to each part, e.g. algorithm idea, algorithm details, proof idea and proof details.
3. Failing to write a proof idea or algorithm idea will automatically make it level 0.
4. In some cases, we might skip level 4 all together.

Point distribution

Each homework will be graded out of 100 points, which will be distributed as follows:

1. The first question (which will be the easier proof-based question) be worth 50 points and will have two parts:
   • Part (a) will be an easy warmup to the actual problem and will be worth 10 points,
   • Part (b) will be the actual problem and will be worth 40 points.
2. The second question (which will be the harder proof-based question) will be worth 25 points and will have two parts:
   • Part (a) will be an easy warmup to the actual problem and will be worth 10 points,
   • Part (b) will be the actual problem and will be worth 15 points.
3. The third question (i.e. the programming question) will be worth 25 points.

Of course, our judgment on the easiness of the second and third questions is subjective. So here is what we will do for you:

Grading consistency and conflict of interest

Multiple TAs will be grading the same non-programming question (for different students), which if not handled correctly can lead to grading inconsistencies. One of the main reasons we use the level system for grading above is to avoid these potential grading consistencies. Also, the TAs will be coordinating among themselves so that the grading is consistent and fair (possibly in that order).

Another potential issue is that some of you might know some of the TAs. To avoid conflict of interest, we have instituted two policies:

1. TAs have declared conflict of interest for specific student enrolled in CSE 331. A TA will never be assigned to grade the submission of a student with whom they have a conflict of interest.
2. We will add another layer of randomization to make things even fairer: every submission will be assigned a random TA (with whom the student does not have a conflict) for grading. In other words, you will not know upfront who will be grading any of your given submissions till after they have been graded.

Other helpful tips

Here are some suggestions for you. Following these are not mandatory but we strongly encourage you to do so. (Interspersed are some general comments related to homeworks.)

1. Start early! The homeworks will be challenging, so start thinking about the homework problems early. Just reading a problem and letting it "marinate" in your head helps a lot. In particular, please do not start working on the homework the night before it is due.
2. Working with algorithms is an art and the only way you can get better (and hence, do well in the exams) is to practice. Homework problems are the minimal practice you should do. We encourage you to work on other exercises from the book. If you do work on a problem and have a question, come and talk to us.
3. Typically, the homework will have three problems: the third one being the easiest (and a programming assignment), the first being medium hard and the second one being the hardest problem. However, note that this is just our guideline and what is easy for us might be hard for you and vice versa. Also the homeworks in general will get harder as the semester goes on (as the material will become more involved). Hence, the easy problem on HW 10 might be harder than the hard problem in HW 1. Finally, since the third question will be a programming question and the other two will be proof-based questions, it can be hard to do a fair comparison on "hardness" of these problems.
4. We will assume that you will collaborate in your homeworks (when permitted). Thus, when we think of a question as being hard, it is assumed that it will need a fair bit of work even as a group to solve that problem. Typically, the easy/programming problem should be solvable if you understand the lecture. Note that there will be no "plug and chug" kind of questions in the homework (e.g. run the algorithm on this specific input), so you might have to spend some time outside of the lecture to really understand the material covered in class.
5. In a homework or exam if you do not follow why you lost some points, go and talk to the grader and try to figure out where you went wrong. We do not really like it when someone comes and is only interested in getting more points but we like it when someone comes by and wants to understand what went wrong and improve.
6. Another plug for working on the material outside the lectures: the exams will not test what was taught in the lectures verbatim. One of the goals of this course is to get you to think abstractly and algorithmically about problems. This cannot be force-fed but only comes about when you do the algorithmic thinking on your own. Understanding what I say in a lecture is a start but it is by no means a sure-fire way of really understanding the material (One way to find out if you understand the material-- teach it to someone else!) Working on problems is one way to build your algorithmic thinking.
7. Many of the problem statements will be pretty verbose and will not have crisp mathematical description. As we will see in the lectures, this is unavoidable in real life and we want you to have practice in looking at a problem statement in English and then converting it into a precise mathematical problem. In real-life there are red herrings: information in the "problem statement" that have nothing to the real mathematical problem. So in some homework problems, we will slip in some red herrings!
8. One of the coolest things about algorithms is that they are applicable pretty much everywhere. A goal of the homeworks is to give you practice in using algorithms in different situations. In particular, the questions will ask you to apply the material covered in class outside of the context they were used in class. For some questions this might not be apparent from the question itself: in most such cases after the homeworks are turned in I will put a post on piazza connecting the question to the real-life application.
9. We will focus heavily on proofs. If your proof skills are rusty, please work on them ASAP. You could go through your CSE 191 book to do so. If you want another source, this book is solely focused on how to prove things:

   Daniel J. Velleman, "How to Prove It: A Structured Approach (2nd Ed)." Cambridge University Press, 2006.

10. To help in the transition, till the mid-term exams I will do the following two things:
    • Each homework will have a solved question so that you see a model solution when you are writing up your own.
    • The CSE 331 support page also might have some helpful resources.