### Assessment

The assessment in this course will be based on homeworks (30%), one midterm (30%) and a final (40%). The midterm will be held in class. The final will be a take-home final. The calibration quiz does not count towards your grade in this class.

### Homework Policy

Homeworks should be handed in class before the lecture starts at the specified due dates. No late homeworks will be accepted.

Homeworks should be done and submitted in groups of two. Please write the name of your group members clearly on your homework submission. Collaboration with anyone inside or outside the class except for your group member is not allowed. Please email me the name of your group member by Thursday January 19th. If I do not hear from you by January 19, I will randomly assign you a group member from the remaining students in the class.

### Standards for Evaluation

Most problems in this course will be of a theoretical nature. In particular, many questions will be of the form "Design an algorithm for the following problem." Your answers to such questions will be graded based on the following criteria:
• Your algorithm must be clearly and unambiguously described. This can be in well-documented and clear pseudo-code, or in precise, mathematical English. There should be no room for interpretation about the steps carried out by your algorithm.
• A proof of correctness of your algorithm must be provided. If a proof of correctness is missing, I will assume that your algorithm is incorrect and grade accordingly. I will use this rule in grading even if I know your algorithm is correct. In some cases, correctness is easy or trivial; in this case, your correctness argument can be a short English explanation. Other times, correctness is highly non-trivial and requires a medium-sized mathematical argument. It is your job to distinguish these two cases.
• Your algorithm must be efficient. Again, your answer should include a well-reasoned time analysis, otherwise, I will assume that it is not efficient. At the very least, a time analysis requires an explanation of where the calculations come from. If the analysis is easy(e.g., with a simple nested loop algorithm), these explanations can be brief (e.g., "The outside loop goes from 1 to n, and each iteration, the inside loop iterates m times, so the overall time is O(nm)." ). For some algorithms, time analysis is a tricky, mathematical proof. If you give just calculations or just a short explanation, and I think the time bound is not easy and clear from what you wrote, you will lose points even if you give the correct time.
• Your algorithm must be relatively efficient. This means that, even if your algorithm is correct and reasonably fast, you may lose some points if there is a faster algorithm.