CSE 101, Design and Analysis of Algorithms , Fall, 2006

Prof. Russell Impagliazzo

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

Russell's Office Hours: Monday, 3-5, Wed, 10-12. Room CSE 3217 (if attendance is small, I may go to my actual office instead.)

TAs: Brian McFee, Scott Yilek

TA office hours: Scott, Tuesday 6-7, Thursday 11-12, CSE 240 (basement), Brian: Tuesday 10-12, CSE B225

Discussion section: Wed., 2-2:50, 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:

• Murali, mgudipat@ucsd.edu
• Sunil Kamadolli: skamadol@ucsd.edu
• Matthew Kan Yaun : kyuan@ucsd.edu
• Jesus Buenros: jbuenros@ucsd.edu

Announcements: The final is open book and open notes. You can bring anything printed, but nothing with a wireless connection or modem.
A typo on problem 4 of the current homework was pointed out: the objective function was missing. A revised assignment is below.
I will have my usual office hours this week, plus a special last minute office hours Thursday, 1-3.

Course handouts and assignments

1. Class Description (Postscript)
2. Class Description (PDF)
3. Calibration homework, due Monday, Oct. 2 NOTE CHANGE(ps)
4. Calibration homework, due Monday Oct. 2 NOTE CHANGE (pdf)
5. Calibration homework answer key (ps)
6. Calibration homework answer key (pdf)
7. Homework 1, due Friday , Oct. 13 (Change from description) (ps)
8. Homework 1, due Friday Oct. 13 (CHANGE from description) (pdf)
9. Homework 1, answer key (ps)
10. Homework 1, answer key (pdf)
11. Homework 1, implementation problem answer (ps)
12. Homework 1, implementation answer key (pdf)
13. Homework 2, due Monday , Oct. 30 (ps)
14. Homework 2, due Monday, Oct. 30 (pdf)
15. Homework 2 Answer Key (ps)
16. Homework 2, answer key (pdf)
17. Homework 3, due Friday, Nov. 17 REVISED(ps)
18. Homework 3, due Friday, Nov. 17 REVISED (pdf)
19. Homework 3 Answer Key (ps)
20. Homework 3, answer key (pdf)
21. Homework 4, CORRECTED due Friday, Dec. 1 (ps)
22. Homework 4, CORRECTED due Friday, Dec. 1 (pdf)
23. Homework 4 Answer Key (ps)
24. Homework 4, answer key (pdf)
25. Sample Midterm (ps)
26. Sample Midterm (pdf)
27. Sample Midterm answer key (ps)
28. Sample Midterm answer key (pdf)
29. Practice Midterm answer key (ps)
30. Practice Midterm answer key (pdf)
31. Another Sample Midterm (ps)
32. Another Sample Midterm (pdf)
33. Sample Final (ps)
34. Sample Final (pdf)
35. Sample Final Answer key (ps)
36. 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.
Here's a link to the slides for the guest lecture by Pavel Pevzner: Lecture notes for Bioinformatics Algorithms (See Chapter 4, Motif Searching) Currently Available:
1. First discussion section summary (ps)
2. First discussion section summary (pdf)
3. Graph Search algorithms (ps)
4. Graph Search algorithms (pdf)
5. Using Preprocessing and data structures: Heap sort and skylines (ps)
6. Using Preprocessing and data structures: Heap sort and skylines (pdf)
7. Recursion vs. Iteration (ps)
8. Recursion vs. Iteration (pdf)
9. Euclud's GCD algorithm (ps)
10. Euclud's GCD algorithm (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 (ps)
14. Divide and Conquer: Mergesort and All pairs binary tree distances (pdf)
15. Divide and Conquer: Integer Multiplication, the Master Theorem (aka Main Recurrence Theorem) (ps)
16. Divide and Conquer: Integer Multiplication, the Master Theorem (aka Main Recurrence 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 (ps)
22. Backtracking: Graph coloring (pdf)
23. Backtracking: Graph coloring Alternate method, notes by Neil Jones (ps)
24. Backtracking: Graph coloring Alternate method, notes by Neil Jones (pdf)
25. Greedy algorithms: Event Scheduling (ps)
26. Greedy algorithms: Event Scheduling (pdf)
27. Greedy algorithms: Assignment Scheduling (ps)
28. Greedy algorithms: Assignment Scheduling (pdf)
29. Kruskals Minimum Spanning Tree Algorithm (ps)
30. Kruskals Minimum Spanning Tree Algorithm (pdf)
31. A simple case of dynamic programming (ps)
32. A simple case of dynamic programming (pdf)
33. Dynamic programming cont.(From Scott's discussion section) (ps)
34. Dynamic programming cont (from Scott's discussion section) (pdf)
35. The Bellman Ford shortest path algorithm (ps)
36. The Bellman Ford shortest path algorithm (pdf)
37. Neil Jones's notes on Dijkstra's algorithm and achieves-the-bound proofs (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. 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)