Homeworks should be done and submitted either individually or 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 17. If you would like to do the homework individually, please also send me an email about this by January 17. If you need a group member, please post on the Piazza group for this class.

- Your arguments should be
**clear**and**mathematically precise**: there should be no room for interpretation about what you are writing. If your arguments are unclear, I will assume that they are wrong, and grade accordingly. - If you cannot solve a problem completely, you will get more partial credit if you present a correct and clear partial solution than if you try to cover up the gaps in your argument.

- 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. This is not a programming class, so**please do not provide detailed code**. Points will be taken off for providing detailed code. -
*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.

In particular, ** students should not look for answers to homework problems in
other texts or on the internet**. You may use other texts as a general study
tool, and may accidentally see solutions to homework problems. In this case,
write up the final solution without consulting the text, and acknowledge the
text on the first page of your solutions. Such a solution may be given partial
or no credit if it follows the text too closely. This policy applies to all
material on the web (except on this year's class webpage), discussions with
others who are either students or not (except the instructor or TA, or other
students as part of office hours), or written notes from others, whether
students or not, (except class notes).
** You should acknowledge all supplementary texts or other sources that had
solutions to homework problems, and anyone who helped with assignments, except
the instructor and the TA.**

Finally, do not discuss the final exam with anyone except the instructor and TA.

Incidents which violate the University's rules on integrity of scholarship will be taken seriously. In addition to receiving a zero (0) on the assignment/exam in question, students may also face other penalties, up to and including, expulsion from the University. If you have any doubts about the moral and/or ethical implications of an activity regarding the course, please see the instructors.