University of California, San Diego

La Jolla, CA 92093-0114

**Office:** 4111 Applied Physics and Mathematics Building (APM)

**Phone:** (858) 534-1332;` ` **Fax:** (858) 534-7029;` `

**Email: ** russell@cs.ucsd.edu

Jeff Edmonds textbook, covered chapters (postscript) . Jeff Edmonds textbook, covered chapters (PDF) . This is a work in progress by Prof. Jeff Edmonds of York University. Please send comments to jeff@cs.yorku.ca. He appreciates feedback.

- Huayong: Thursday, 1-3, EBU-1 6307 C
- Jia: Wednesday, 1-3, EBU-1 6307 B
- Sean: Tuesday, 8:45-10:45, EBU-1 6307

Huanyong Hu will have a special exam week office hours, Tuesday 4-6 in EBU1 6307. Russell will have Monday office hours as usual, 12-2, and Sean will have office hours as usual Tuesday morning.

- Class Description (Revised, Postscript)
- Class Description (Revised, PDF)
- Calibration homework, due April 15 (ps)
- Calibration homework, due April 15 (pdf)
- Homework 1, due April 29. Some problems clarified or corrected, April 25 (ps)
- Homework 1,, due April 29 . Some problems clarified or corrected. (pdf)
- Homework 2, due May 11. (ps)
- Homework 2, due May 11. (pdf)
- Homework 3, due May 25. (ps)
- Homework 3, due May 25. (pdf)
- Homework 4, due June 3. (ps)
- Homework 4, due June 3. (pdf)
- Sample midterm (ps)
- Sample midterm (pdf)
- Sample midterm answers (ps)
- Sample midterm answers (pdf)
- Sample final (ps)
- Sample final (pdf)
- Sample final answers (ps)
- Sample final answers (pdf)

- April 1: Euclid's GCD algorithm (PS)
- April 1: Euclid's GCD algorithm (PDF)
- April 6: Time analysis of Euclid's GCD algorithm (PS)
- April 6: Time analysis of Euclid's GCD algorithm (PDF)
- April 8: Restrucuring and data structures: the view problem and sorting (PS)
- April 8: Restrucuring and data structures: the view problem and sorting (PDF)
- April 13: Using and modifying data structures: sorting and skylines (PS)
- April 13: Using and modifying data structures: sorting and skylines (PDF)
- More detailed presentation of skyline problem from past years. (PS)
- More detailed presentation of skyline problem from past years. (PDF)
- April 15: Graph algorithms: Forest detection (PS)
- April 15: Graph algorithms: Forest detection (PDF)
- April 20: Graph search, analyzing recursive algorithms (PS)
- April 20: Graph search, analyzing recursive algorithms (PDF)
- April 22: Divide and conquer: mergesort and tree distances (PS)
- April 22: Divide and conquer: mergesort and tree distances (PDF)
- April 27: Divide and conquer:integer multiplication, main recursion theorem (PS)
- April 27: Divide and conquer:integer multiplication, main recursion theorem
- April 29: Divide and conquer:uneven divide-and-conquer, the guess-and-verify method of analysis. (PS)
- April 29: Divide and conquer:uneven divide-and-conquer, the guess-and-verify method of analysis. (PDF)
- May 4: Backtracking: the independent set problem (ps)
- May 4: Backtracking: the independent set problem (PDF)
- May 6: Backtracking: the Hamiltonian path problem (ps)
- May 6: Backtracking: the Hamiltonian path problem (PDF)
- May 11: Backtracking without self-similarity: 3-coloring, Why greedy algorithms are dangerous (ps)
- May 11: Backtracking without self-similarity: 3-coloring, Why greedy algorithms are dangerous (PDF)
- May 13: Proving greedy algorithms are correct: the modify-the solution method(ps)
- May 13: Proving greedy algorithms are correct: the modify-the solution method(pdf)
- May 18: Greedy algorithms continued: the assignment problem (ps)
- May 18: Greedy algorithms continued: the assignment problem (pdf)
- May 20: Greedy algorithms: Kruskal's algorithm for minimum spanning tree (ps)
- May 20: Greedy algorithms: Kruskal's algorithm for minimum spanning tree (pdf)
- May 25: Data structures for disjoint sets in Kruskal's algorithm; intro to DP (ps)
- May 25: Data structures for disjoint sets in Kruskal's algorithm; intro to DP (pdf)
- May 27: Dynammic programming steps (ps)
- May 27: Dynammic programming steps (pdf)
- June 1: Shortest paths (ps)
- June 1: Shortest paths (pdf)

- Leeann Bent's Order Notation Summary Sheet (ps)
- Leeann Bent's Order Notation Summary Sheet (PDF)
- Using Data Structures Summary Sheet (postscript)
- Using Data Structures Summary Sheet (PDF)
- Divide-and-conquer Summary Sheet (postscript)
- Divide-and-conquer Summary Sheet (pdf)
- Backtracking Summary Sheet (postscript)
- Backtracking Summary Sheet (pdf)
- Greedy Algorithms Summary Sheet (postscript)
- Greedy Algorithms Summary Sheet (pdf)
- Dynammic Programming Summary Sheet (postscript)
- Dynammic Programming Summary Sheet (pdf)