CSE 421: Introduction to Algorithms, Spring 2024

Grading Guidelines

We're sure you're aware of all of the following, and some of it is repetitious. but just to be sure we're all on the same page with respect to what homework solutions should look like:

Collaboration

• You are allowed to collaborate on the homework to the extent of formulating your ideas as a group.
• You must write up the solutions to each problem set completely on your own and once your assignment is written up, you must not let others see your solutions.
• You cannot take pictures in the from the Office hours or copy any hints given.
• You must also list the names of everyone whom you discussed the problem set with.

Academic Integrity

• You are not allowed to search for solutions to problems on the internet or other sources outside of those given in class, the textbook, and the course website, or share your solutions through such means.
• You are not allowed to use ChatGPT or LLL
• You are not allowed to post HW problems in Stack Overflow or MathOverflow.
• You are not allowed to use any theorems or results not proved in class.

Always prove that your algorithm works and upper bound its runtime. Whether the problem specifically asks for it or not, you should always prove that your algorithm works. This will generally consist of two parts:

• Prove that your algoritm ends in a number of step (not larger than the value) asked in the problem statement.

• Prove that it outputs the correct answer.

You may lose points for style. Your proofs and explanations should be clear, well-organized and as concise as possible. It is better to err on the side of including too many details, however, you should not belabor things that are completely obvious. Unfortunately, a lot of this is subjective. Often, students think of proofs as merely either "right" or "wrong". This would be true if they were expressed in every last detail in a formal logic but not at the level that you will need to write them here. Writing a proof is more like writing an essay. Along these lines, if you are not able to find a complete answer to a problem, you are better off explaining clearly what you've done rather than faking a proof.

Sanity Check: A sanity check to test the correctness of your proof and your algorithm is to make sure that you use all assumptions given in the problem statement. Clearly mark every place in the proof that you use a spefici assumption. If an assumption is not necessary for your proof make that clear as well. If you are writing an inductive proof, clearly mark where you use the induction hypothesis.

Pictures and short pieces of pseudocode can be helpful, but they are not sufficient. Make sure to label everything. Define all the variables you use. Make sure you've explained everything clearly in English.

Try rewriting your proofs. Writing out your answer fully on a piece of scratch paper before writing up the version to hand in really does make a difference. You are more likely to catch mistakes or exceptions, and your proof will be better organized.

Set up good notation. Many of the exercises in the book are phrased almost entirely in English. It will be your job to rephrase them mathematically when necessary. The first few lines of many of your proofs will look something like, "Let S be the set of students taking cse421." Make sure that you've clearly defined any variable you use. Choosing good names for your variables is also important. For this class, it probably won't matter too much, but for complicated proofs, it can make a big difference.