Section ID: 434291
Instructor: Daniele Micciancio (email: daniele@cs.ucsd.edu)
Final week Office hour: Monday at 11:00a-12:00p and Thursdays 11:00-12:00p in AP&M 5230
Lectures: Tuesday & Thursday at 9:35-10:55a in Solis 109
TA: Sashka Davis (email: sdavis@cs.ucsd.edu)
Introduction to Algorithms. (2nd ed.) Cormen, Leiserson, Rivest, Stein. MIT Press/McGraw-Hill.
The first edition of the book should be fine too, but you will need to find the corresponding page numbers for reading assignments and problems.
There will be 3 homeworks assignments, 1 project and a take-home final exam. Homeworks will account for 30% of the grade, the project 20% and the final will account for the remaining 50%. Each homework assignment will have 3 or 4 theoretical problems and one implementation problem. You should budget 10-20 hours for each homework assignment, including time spent in office hours, and 20-40 hours for the project. Homeworks should be solved individually. For the project, you are allowed to team up in group of up to 3..
The tentative schedule for the assignments is the following:
Answer Key (Postscript) (PDF) Statistics: Average=65, Std.Dev.=13, Highest score = 88.
Answer Key (Postscript) (PDF) Statistics: Average=68, Std.Dev.=24, Highest score = 96.
Answer Key (Postscript) (PDF) available soon.
Below are pointers to chapters in the book covering the material presented in class, and pointers to additional reading assignments.
For a general solution to the closest pair of points in n-dimensions see Divide-and-conquer in multidimensional space, Proceedings of the eighth annual ACM symposium on Theory of computing , STOC 76
Optional: If you want to know more about the latest developments for quicksort and randomized select, read Optimal Sampling Strategies in Quicksort and Quickselect from SIAM Journal on Computing vol 31, n. 3, 2001.
We assume some undergraduate exposure to discrete mathematics (including discrete probability), and to algorithms and their analysis, and the ability to read, recognize and write valid proofs. If your background in these areas is weak, you may need to do some extra work to catch up. Part of these prerequisites are covered in the textbook in Chapters 1,2,3,4,5 and 10, and the appendices.
You are allowed to talk with other students about the assignments, but any such collaboration should be clearly acknowledged on the front page of the homeworks. In any case, solutions to the homeworks should be written individually. You should absolutely not share written solutions with other students.
You may consult references other than the textbook (including whatever information you might be able to find on the web), but if you do so, you should give proper credit when writing your solutions, giving references (urls in case of information found on the web).
Homeworks solutions will not be accepted after keys are posted on the class web page. Typically solutions will be ready before homeworks are due and will be posted right after the submission deadline specified on the assignments.
The project for the class is to find a well-specified algorithmic problem that is important for some computer science area, preferably in your future research area or some other area you are interested in and knowledgable about. You should 1.
Your project should have at least one non-trivial mathematical proof in it (correctness proof, approximation ratio, non-trivial time analysis), and at least a page of non-mathematical discussion of the application. If you have trouble thinking of a topic, talk to me (and we can have trouble thinking of a topic together.) You may work in teams of up to three, but a team project should be somewhat longer, and all group members must write up part of the project. Individual projects should be 5 (word-processed) pages or so. Due date: May 28.