Homework in Computer Algorithms

**Homework Submission, Late Homeworks:**

Homework should be handed in at the beginning of lecture on the day it is due. Any homework turned in after this point will result in a 50% grade reduction, and no homework will be accepted more than one day late, except in the case of a genuine emergency.

**Writing Proofs and Algorithms:**

- You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness. You should try to make your algorithms as efficient as possible.
- Many of the questions from the textbook consist of mostly English description, without much mathematical notation. This requires you to take a problem described in free text, and formalize it before solving it. Look at the "Solved Problems" in the textbook to see examples of this process.
- The best way to explain an algorithm is usually in English, with some mathematical notation. Some pseudo-code together with an English explanation is also fine. Solutions that simply give a long piece of pseudo-code without an explanation, however, tend to contain mistakes, and be very hard to understand. We reserve the right to deduct points for such solutions, even if they turn out to be correct.
- You should write up both your algorithms and your proofs clearly and neatly, as this will make your solution easier to understand, and will earn you more partial credit.
- You are allowed to use any result that is proved in class or in the textbook in your solutions, without having to re-prove this result (in other words, you can just cite the textbook in your solution).

**Working Together:**

You are allowed to work with a partner; each pair of students can submit just one copy of a homework together, as long as each of the pair writes up one of the homework problems. In addition to your partner, you are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. There is no penalty for working in groups. However, every pair must write up their assignments separately, and
include the list of "collaborators" that you discussed the assignment with. Make sure that you spend a lot of time thinking about the problems yourself and writing up the solutions; students who only follow their partner's lead will find the exams much more difficult.

You may not copy (or near-copy) a solution from another. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and may result in the final grade being reduced by a letter and a 0-grade for the homework for both parties. No collaboration is allowed during exams. It should go without saying that collaborating with people not taking this class, or using any resource other than the class textbook or notes, is a serious breach of academic integrity and will be punished severely.

**Grading:**

- The lowest homework grade will be dropped.
- Any request to re-evaluate a grade must be made within one week of the return date of the homework or exam in question. You must explain why you think your grade should be changed
*in writing*, and submit your request to me or a TA. The second grade will remain. Furthermore, we generally will not accept regrade requests that dispute the amount of partial credit awarded; we are only interested in instances where an actual mistake has been made. Do not be surprised if your regrade takes a long time, as we will only process them periodically.

**Returning Homework:**

Homeworks will be returned in self-service stacks at the end of class. If you prefer more privacy, clearly write "HOLD" at the top of the solution to every problem you hand in. These problems, as well as any homework not picked up in class, can be picked up from me during office hours.