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

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

Office: 4248 Computer Science Building
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu

Russell's Office Hours: W: 4-6, Th 10-11, CSE 4248 or see notice.


TAs: Wan-Yen Lo, walo@ucsd.edu (Use Subject: CSE 101)

TA office hours: M, F: 10-11, CSE B240a

Discussion section: Wed., 11-11:50, Solis 104

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:

Announcements:

Reminder: The final exam is Monday, June 8, 3-6 PM in Center 109. The exam is open book and open notes. It will cover the same material as the sample final below.

Course handouts and assignments

  1. Class Description (Postscript)
  2. Class Description (PDF)
  3. Calibration homework, due Thursday April 9, (PS)
  4. Calibration homework, due Thursday April 9 (pdf)
  5. Calibration homework, answer key (ps)
  6. Calibration homework, answer key (pdf)
  7. homework 1, due Thursday April 23 (PS) New version, with typos fixed
  8. homework 1, due Thursday April 23 (PDF) New version, with typos fixed
  9. homework 1, answer key (PS)
  10. homework 1, answer key (Pdf)
  11. homework 1, implementation question answer (PS)
  12. homework 1, implementation question answer (PDF)
  13. homework 2, due Tuesday May 5(PS)
  14. homework 2, due Tuesday May 5(PDF)
  15. homework 2, answer key (PS)
  16. homework 2, answer key (PDF)
  17. Sample midterm (ps)
  18. Sample midterm (pdf)
  19. Practice midterm answer key (ps)
  20. Practice midterm answer key (pdf)
  21. Sample midterm answer key (ps)
  22. Sample midterm answer key (pdf)
  23. homework 3, due Tuesday May 26(PS)
  24. homework 3, due Tuesday May 26(PDF)
  25. homework 4, due Thursday June 4(PS)
  26. homework 4, due Thursday June 4(PDF)
  27. Sample final (ps)
  28. Sample final (pdf)
  29. Sample final answer key (ps)
  30. Sample final answer key (pdf)
  31. homework 3, answer key (PS)
  32. homework 3, answer key (PDF)
  33. homework 4, answer key (PS)
  34. homework 4, answer key (PDF)
Lecture notes: Most of these are from Spring, 2004, written up by Sean O'Rourke They will be posted as we cover the topics in class. Currently Available:
  1. Graph search (ps)
  2. Graph search (pdf)
  3. Using data structures (ps)
  4. Using data structures (pdf)
  5. Greedy algorithms and the transformation method: event scheduling (ps)
  6. Greedy algorithms and the transformation method: event scheduling (pdf)
  7. Kruskal's Minimum Spanning Tree Algorithm (PS)
  8. Kruskal's Minimum Spanning Tree Algorithm (PDF)
  9. Recursive algorithms (not covered diretly this year (PS)
  10. Recursive algorithms (not covered diretly this year (Pdf)
  11. Divide and conquer 1: Mergesort (PS)
  12. Divide and conquer 1: Mergesort (PDF)
  13. Divide and conquer 2: Multiplication (PS)
  14. Divide and conquer 2: Multiplication (PDF)
  15. Divide and conquer 3: The Master Theorem (PS)
  16. Divide and conquer 3: The Master Theorem (PDF)
  17. Backtracking 1: Maximum Independent Set (PS)
  18. Backtracking 1: Maximum Independent Set (PDF)
  19. Maximum Independent Set for Trees: A greedy example(PS)
  20. Maximum Independent Set for Trees: A greedy example(PDF)
  21. Backtracking 2: 3 coloring (PS)
  22. Backtracking 2: 3 coloring (PDF)
  23. Simple dynamic programming example (ps)
  24. Simple dynamic programming example (pdf)
  25. Another DP algorithm (ps)
  26. Another DP algorithm (pdf)
  27. Bellman-Ford DP shortest paths (ps)
  28. Bellman-Ford DP shortest paths (pdf)
  29. Dijkstra's shortest paths (pdf only)

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. Greedy Algorithms Summary Sheet (ps)
  6. Greedy Algorithms Summary Sheet (PDF)
  7. Divide and Conquer Summary Sheet (postscript)
  8. Divide and Conquer Summary Sheet (PDF)
  9. Backtracking Summary Sheet (ps)
  10. Backtracking Summary Sheet (PDF)
  11. Dynamic Programming Summary Sheet (ps)
  12. Dynamic Programming Summary Sheet (pdf)