CSE 101, Design and Analysis of Algorithms , Winter, 2005

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: Russell will have a last minute office hours in 4111 AP&M from 9:30-10:30 Monday morning.


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, which can be used as a supplementary textbook. Please send comments to jeff@cs.yorku.ca. He appreciates feedback.

TAs: Huayong Hu, Mikhail Afanasyev, Max Alekseyev, Qian Peng

TA office hours:

Discussion section: Fri, 1-2, HSS 1330

Discussion section is mandatory. Please keep that time free. Midterm exams are during discussion section.

Students looking for study groups or who want additional members for their groups:

Course handouts and assignments

  1. Class Description (Postscript)
  2. Class Description (PDF)
  3. Calibration homework, due January 13(ps)
  4. Calibration homework, due January 13 (pdf)
  5. Calibration homework, answer key (ps)
  6. Calibration homework, answer key (pdf)
  7. Calibration homework, implementation answer key (ps)
  8. Calibration homework, implementation answer key (pdf)
  9. Homework 1, due January 27(ps)
  10. Homework 1, due January 27(pdf)
  11. Homework 1, answer key (ps)
  12. Homework 1, answer key(pdf)
  13. homework 1, implementation answer key by Ari Frank (ps)
  14. homework 1, implementation answer key by Ari Frank (pdf)
  15. Sample Midterm-- use to study for Practice Midterm (2/4) and Midterm (2/18) (ps)
  16. Sample Midterm-- use to study for Practice Midterm (2/4) and Midterm (2/18) (pdf)
  17. Sample Midterm answer key-- use to study for Practice Midterm (2/4) and Midterm (2/18) (ps)
  18. Sample Midterm answer key-- use to study for Practice Midterm (2/4) and Midterm (2/18) (pdf)
  19. Practice Midterm answer key-- use to study for Midterm (2/18) (ps)
  20. Practice Midterm answer key-- use to study for Midterm (2/18) (pdf)
  21. Homework 2, due Feb. 15(ps)
  22. Homework 2, due Feb. 15 (pdf)
  23. Homework 2, answer key (ps)
  24. Homework 2, answer key(pdf)
  25. Homework 3, due March 3(ps)
  26. Homework 3, due March 3 (pdf)
  27. Homework 3, answer key(ps)
  28. Homework 3, answer key(pdf)
  29. Homework 4, due March 10(ps)
  30. Homework 4, due March 10(pdf)
  31. Homework 4, answer key(ps)
  32. Homework 4, answer key(pdf)
  33. Sample Final -- use to study for final Monday, March 14. (ps)
  34. Sample Final -- use to study for final Monday, March 14. (pdf)
  35. Sample Final Answer Key -- use to study for final Monday, March 14. (ps)
  36. Sample Final Answer Key -- use to study for final Monday, March 14. (pdf)
Lecture notes: Most of these are from Spring, 2004, written up by Sean O'Rourke
  1. Euclid's GCD algorithm (ps)
  2. Euclid's GCD algorithm (pdf)
  3. Using Preprocessing and data structures: Heap sort and skylines (ps)
  4. Using Preprocessing and data structures: Heap sort and skylines (pdf)
  5. Using Preprocessing and data structures: Views (ps)
  6. Using Preprocessing and data structures: views (pdf)
  7. Data structures for graph representations: is a graph a forest? (ps)
  8. Data structures for graph representations: is a graph a forest? (pdf)
  9. Data structures for graph representations: searching a graph (ps)
  10. Data structures for graph representations: searching a graph (pdf)
  11. Including costs for arithmetic and amortized analysis: Euclid's GCD algorithm revisited (ps)
  12. Including costs for arithmetic and amortized analysis: Euclid's GCD algorithm revisited (ps)
  13. Divide and Conquer: Mergesort and All pairs binary tree distances (which we didn't cover in class this year) (ps)
  14. Divide and Conquer: Mergesort and All pairs binary tree distances (which we didn't cover in class this year) (pdf)
  15. Divide and Conquer: Integer Multiplication, the Master Theorem (ps)
  16. Divide and Conquer: Integer Multiplication, the Master Theorem (pdf)
  17. Divide and Conquer: When (not) to use the Main Recurrence Theorem (ps)
  18. Divide and Conquer: When (not) to use the Main Recurrence Theorem (pdf)
  19. Backtracking: Introduction and Maximum Independent Set (ps)
  20. Backtracking: Introduction and Maximum Independent Set (pdf)
  21. Backtracking: Graph coloring: generalizing problems to allow recursive solutions; Why greedy algorithms are dangerous (ps)
  22. Backtracking: Graph coloring: generalizing problems to allow recursive solutions; Why greedy algorithms are dangerous (pdf)
  23. Greedy algorithms compared to back-tracking: The Modify-the-solution method, event scheduling (ps)
  24. Greedy algorithms compared to back-tracking: The Modify-the-solution method, event scheduling (pdf)
  25. Greedy algorithms : The Modify-the-solution method, Kruskal's minimum spanning tree algorithm (ps)
  26. Greedy algorithms : The Modify-the-solution method, Kruskal's minimum spanning tree algorithm (pdf)
  27. Data structures for disjoint sets and Kruskal's minimum spanning tree algorithm Intro to dynamic programming (ps)
  28. Data structures for disjoint sets and Kruskal's minimum spanning tree algorithm Intro to dynamic programming (pdf)
  29. Dynamic programming: the minimum cost benches problem (ps)
  30. Dynamic programming: the minimum cost benches problem (pdf)
  31. Dynamic programming: the shortest path problem (ps)
  32. Dynamic programming: the shortest path problem (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 (ps)
  8. Backtracking Summary Sheet (PDF)
  9. Greedy Algorithms Summary Sheet (ps)
  10. Greedy Algorithms Summary Sheet (PDF)
  11. Dynamic Programming Summary Sheet (ps)
  12. Dynamic Programming Summary Sheet (pdf)