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.
You are allowed to collaborate in small groups on homework assignments; however, each member of the group should write the solution in their own words, and turn it in separately. If you do collaborate, then, the names of all your group members must appear on the assignment.
Due to the heavy load on our TA, only two problems from each homework will be graded.
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.
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.
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.