**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:

- April 23, first homework due.
- May 7, second homework due
- May 28, project due
- June 6, third homework due
- June 13, final due.

- Homework 1. (Postscript) (PDF). Due Tuesday April 23 at the beginning of class.
Answer Key (Postscript) (PDF) Statistics: Average=65, Std.Dev.=13, Highest score = 88.

- Homework 2. (Postscript) (PDF). Due Tuesday May 7 at the beginning of class.
Answer Key (Postscript) (PDF) Statistics: Average=68, Std.Dev.=24, Highest score = 96.

- Homework 3. (Postscript) (PDF). Due Thursday June 6 at the beginning of class.
Answer Key (Postscript) (PDF) available soon.

- Final exam: (Postscript) (PDF)

Below are pointers to chapters in the book covering the material presented in class, and pointers to additional reading assignments.

- Chapters 1-5, and the appendix. This is all backgorund material you should already know. Quickly read all these chapters to make sure you have the necesary background. If you encouter any difficulty, come and talk to me immediately
- Chapter 10. This is also backgorund material about elementary data structures, pointers, etc.
- Chapter 7. Quicksort.
- Chapter 33.4. Closest pair of points. Read also Section 33.1. (Optional
reading: 33.2, 33.3. Notice: section 2 uses red black trees from Chapter
13.)
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

- Chapter 28.1, 28.2: Matrices and Strassen Algorithm. (Optional reading: 28.3, 28.4, 28.5. These are all classical numerical algorithms and only uses elementary algorithmic techniques.)
- Chapter 9. Medians and order statistics.
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.

- Chapter 30. Polynomials and Fast Fourier Transform
- Chapter 15.1, 15.2, 15.3. Dynamic Programming. Read also 15.4, 15.5 for more examples of dynamic programming algorithms.
- Chapter 16.1, 16.2. Greedy Algorithms. Read also 16.3 for an additional example.
- Chapter 35.3: Greedy algorithm for (log n)-approximate set cover. You can read also 35.1 for the greedy 2-approximation algorithm mentioned in class.
- Chapter 22: Graph algorithms, bredth first search, depth first search, topological sort, strongly connected components
- Chapter 23: Minimum Spanning Trees. For a research article about MST algorithms (as well as many pointers to other recent work on the subject) see An optimal minimum spanning tree algorithm, Journal of ACM, vol 49, issue 1, January 2002.
- Chapter 24: Single source shortest paths.
- Chapter 25: All sources shortest paths, sections 1,2. Optional: section 3.
- Chapter 26: Flow networks (Sections 1,2,3). Optional: sections 4,5.
- Chapter 34: NP-completeness

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.

- define the problem rigorously,
- present and analyze algorithms in the literature to solve the problem, and
- discuss how well the theoretical analysis captures the real-life performance of these algorithms.

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.