CSE 101, Design and Analysis of Algorithms , Spring, 2004

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
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

Russell's 101 Office Hours: NOTE CHANGE!!!! This supercedes the class description. M 2-4, Wed. 3-5, 4111 AP&M or 4882 AP&M. (If more than 3 students attend, I will move office hours to 4882 AP&M, at the far end of the annex, across the breezeway.)

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.

TAs: Huayong Hu, Jia Mao, Sean O'Rourke

TA office hours:

Discussion section: Fri, 3-4, Solis 104

Discussion section is mandatory. Please keep that time free. Midterm exams are during discussion section.
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.

Course handouts and assignments

  1. Class Description (Revised, Postscript)
  2. Class Description (Revised, PDF)
  3. Calibration homework, due April 15 (ps)
  4. Calibration homework, due April 15 (pdf)
  5. Homework 1, due April 29. Some problems clarified or corrected, April 25 (ps)
  6. Homework 1,, due April 29 . Some problems clarified or corrected. (pdf)
  7. Homework 2, due May 11. (ps)
  8. Homework 2, due May 11. (pdf)
  9. Homework 3, due May 25. (ps)
  10. Homework 3, due May 25. (pdf)
  11. Homework 4, due June 3. (ps)
  12. Homework 4, due June 3. (pdf)
  13. Sample midterm (ps)
  14. Sample midterm (pdf)
  15. Sample midterm answers (ps)
  16. Sample midterm answers (pdf)
  17. Sample final (ps)
  18. Sample final (pdf)
  19. Sample final answers (ps)
  20. Sample final answers (pdf)

Lecture notes

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

Course Topics Study Guides

  1. Leeann Bent's Order Notation Summary Sheet (ps)
  2. Leeann Bent's Order Notation Summary Sheet (PDF)
  3. Using Data Structures Summary Sheet (postscript)
  4. Using Data Structures Summary Sheet (PDF)
  5. Divide-and-conquer Summary Sheet (postscript)
  6. Divide-and-conquer Summary Sheet (pdf)
  7. Backtracking Summary Sheet (postscript)
  8. Backtracking Summary Sheet (pdf)
  9. Greedy Algorithms Summary Sheet (postscript)
  10. Greedy Algorithms Summary Sheet (pdf)
  11. Dynammic Programming Summary Sheet (postscript)
  12. Dynammic Programming Summary Sheet (pdf)