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

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, F 2:30-4, CSE 4248 or see notice.


TAs: Qian Peng

TA office hours: Thursday, 5-7, CSE B250A

Discussion section: W, 1-2, Center 105

Tutors: Leilani Gilpin, David Lorant

Tutor office hours : Monday, 1-2 PM, Tuesday 1-2pm in CSE B275.

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:

Russell will have a special office hours Monday June 6, 2:30-4 for pre-final questions. Tutor office hours are still 1-2. Reminder: The final exam is Tuesday, June 7. The exam is open book and open notes. It will cover the same material as the sample final, which will be on this page well before the final .

Course handouts and assignments

  1. Class Description (Postscript)
  2. Class Description (PDF)
  3. Calibration homework, due Thursday, April 7, (PS)
  4. Calibration homework, due Thursday, April 7 (pdf)
  5. Calibration homework Answer Key (PDF)
  6. Homework 1, due Tuesday, April 19 (pdf)
  7. Homework 1, answer key (pdf)
  8. Homework 2, due Tuesday, May 3 (pdf)
  9. Homework 2, answer key (pdf)
  10. Homework 3, due Thursday, May 19 (pdf)
  11. Homework 3, answer key (pdf)
  12. Homework 4, due Thursday, June 2 (pdf)
  13. Homework 4, answer key (pdf)
  14. Sample Midterm (pdf)
  15. Second Sample Midterm (pdf)
  16. Second Sample Midterm Answer Key (pdf)
  17. Sample Final (pdf)
  18. Sample Final 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. A powerpoint on greedy algorithms by Jeff Edmonds
  8. Kruskal's Minimum Spanning Tree Algorithm (PS)
  9. Kruskal's Minimum Spanning Tree Algorithm (PDF)
  10. Recursive algorithms (PS)
  11. Recursive algorithms Pdf)
  12. Divide and conquer 1: Mergesort (PS)
  13. Divide and conquer 1: Mergesort (PDF)
  14. Divide and conquer 2: Multiplication (PS)
  15. Divide and conquer 2: Multiplication (PDF)
  16. Divide and conquer 3: The Master Theorem (PS)
  17. Divide and conquer 3: The Master Theorem (PDF)
  18. Backtracking 1: Maximum Independent Set (PS)
  19. Backtracking 1: Maximum Independent Set (PDF)
  20. Maximum Independent Set for Trees: A greedy example(PS)
  21. Maximum Independent Set for Trees: A greedy example(PDF)
  22. Backtracking 2: 3 coloring (PS)
  23. Backtracking 2: 3 coloring (PDF)
  24. Simple dynamic programming example (ps)
  25. Simple dynamic programming example (pdf)
  26. Another DP algorithm (ps)
  27. Another DP algorithm (pdf)
  28. Bellman-Ford DP shortest paths (ps)
  29. Bellman-Ford DP shortest paths (pdf)
  30. 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)