Homeworks 30 %
Midterm 30 %
Final 35 %
Class Participation 5 %

The midterm will be held in class on Wed May 11 and the final on Jun 9. We will not be able to give extra midterms or finals except for medical emergencies; if you cannot make it to class on these dates, then please do not take the class. There will be four homeworks. The calibration quiz does not count towards your grade in this class.

We will have short problem-sessions in some lectures. Your class participation grade will be based on your performance in these problem-sessions. While we will be happy to discuss the solutions to the problem sessions in lecture and office hours, we will not be providing written solutions for these problems. The top ten question answerers in Piazza will get the participation grades for free.

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 one or two or three. A single homework should be submitted per group. 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(s) is not allowed.

Please email me the name of your group member(s) by Fri Apr 8. This helps us reduce recording mistakes. If you are working alone, please also let me know by this date. If you need a group partner, please post on the Piazza discussion group for the class.

Standards for Evaluation

Most problems in this course will be of a theoretical nature, and the solutions will involve proofs. Your solutions to these problems will be graded based on both correctness and clarity. It is not sufficient in this class to get the correct answer; you should also be able to explain the solution to others clearly and precisely.

  • 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.

Many questions in this class 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. This is not a programming class, so please do not provide detailed code. Points will be taken off for providing detailed code. For an example of how to describe an algorithm, see the sample HW and its solutions.

  • 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. Again, for an example, see the sample HW and its solutions.

  • 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.

Regrade Policy

For homeworks and the midterm, you have a window of 7 days (from when we return your homework or exam) to ask for a regrade. If the homework or exam is returned in lecture on a Friday, you have until before lecture next Friday to ask for a regrade. We will not consider any regrade requests outside this window. A regrade request for the midterm should be accompanied by a one-page written report on why we should consider a regrade of your midterm. A regrade request will not be considered without the written report. Finally, while I am happy to discuss the technical and intellectual content of the homeworks/exams in office hours, I will not discuss grading.

Academic Honesty

University rules on integrity of scholarship will be strictly enforced. By taking this course, you agree to abide by the UCSD Policy on Integrity of Scholarship described on this Web Site. In particular, “all academic work will be done by the student to whom it is assigned, without unauthorized aid of any kind.” 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.

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