The assessment in this course will be based on homeworks (25%), one midterm (35%) a final (35%) and class participation (5%).
The midterm and the final will be held in class. The midterm will be held in class on Tuesday Feb 3 and the final will be held in class on Thursday March 12. Class participation will evaluated by (a) participation in the in-class problem sessions and (b) Piazza participation -- the top 10 question answerers on Piazza will automatically get the 5% participation credit. The calibration quiz does not count towards your grade in this class.
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 or three. Each group should submit a single homework. 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 by Thursday January 22. If you need a group member, please post on the Piazza group for this 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.
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
- 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
- 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. 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.
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
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.