aa CSE 101, Design and Analysis of Algorithms ,Spring, 2003

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

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: WF, 2-4, 4111 AP\&M. This is now official. There won't be a change to office hours.


Second Textbook, Thinking about algorithms Full version. Covered Chapters (postscript) . Covered Chapters (PDF) . You should print out Chapters 3-5 (pp.58-94), 8 (109-123), 11(162-177), and 15(205-222). Chapters 3-5 are needed right away; others will be later in course. Chapters 1,2,6,10,12, and 18 are recommended, but not required. They cover material also found in the primary text. 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: Jun Lu, Ari Frank, Barath Raghavan

TA office hours: Jun Lu, M 1-3, AP&M 3337A, W1-2, AP&M, 3337D; Ari Frank: Tu, 4:30-6:30 AP&M, 3337D, W, 12-1, AP&M 3337D; Barath Raghavan, Tu: 3:30-4:30 ,AP &M 3349A, Th, 3:30-5:30 AP&M 3349D. Subject to change.

Discussion section: Friday, 11-11:50 in Solis, 104.

Announcements: Discussion section is mandatory. Please keep that time free. Midterm exams are during discussion section.
Jun Lu will have her usual Monday office hours exam week. Barath and Ari will have their usual Tuesday office hours. Russell will have office hours Wed., 12:30-2:30.
I am having some trouble with word-processing programs. Answer keys for the sample final and homework 4 will be available when these are sorted out.

Course handouts and assignments

  1. Class Description (Postscript)
  2. Class Description (PDF)
  3. Calibration homework, due April 15 (ps)
  4. Calibration homework, due April 15 (pdf)
  5. Calibration homework, Answer Key(ps)
  6. Calibration homework, Answer Key(pdf)
  7. Calibration homework implementation problem, Ari's time-size graph (ps)
  8. Calibration homework implementation problem, Ari's time-size graph (pdf)
  9. First homework, due April 24 (ps)
  10. First homework, due April 24 (pdf)
  11. First homework, Answer Key(ps)
  12. First homework, Answer Key(pdf)
  13. First homework implementation problem, Ari's time-size graph (Strange bugs--pdf is more complete) (ps)
  14. First homework implementation problem, Ari's time-size graph with some general comments (pdf)
  15. Second homework, due May 13(ps)
  16. Second homework, due May 13 (pdf)
  17. Second homework, Answer Key(ps)
  18. Second homework, Answer Key(pdf)
  19. Third homework, due May 29(ps)
  20. Third homework, due May 29 (pdf)
  21. Third homework, Answer Key(ps)
  22. Third homework, Answer Key(pdf)
  23. Data structures for the skyline problem (to refresh your memory)(ps)
  24. Data structures for the skyline problem (to refresh your memory)(pdf)
  25. Fourth homework, due June 5 (ps)
  26. Fourth homework, due June 5 (pdf)
  27. Fourth homework, Answer Key(ps)
  28. Fourth homework, Answer Key(pdf)
  29. Sample Midterm (ran a little long)(ps)
  30. Sample Midterm (ran a little long)(pdf)
  31. Sample Midterm Answer Key(ps)
  32. Sample Midterm Answer Key(pdf)
  33. Practice Midterm Answer Key(ps)
  34. Practice Midterm Answer Key(pdf)
  35. Sample Final (ps)
  36. Sample Final (pdf)
  37. Sample Final Answers From Last Year -- It's almost the same, and I'm experiencing computer difficulties (ps)
  38. Sample Final Answers From Last Year -- It's almost the same, and I'm experiencing computer difficulties (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 (ps)
  6. Divide-and-Conquer Summary Sheet (PDF)
  7. Back-tracking Algorithms Summary Sheet (ps)
  8. Back-tracking Algorithms Summary Sheet (PDF)
  9. Greedy Algorithms Summary Sheet (ps)
  10. Greedy Algorithms Summary Sheet (PDF)
  11. Dynamic Programming Summary Sheet (postscript)
  12. Dynamic Programming Summary Sheet (PDF)