CSE 331
Introduction to Algorithm Analysis and Design
Summer 2013

syllabus
homework policy

Office Hours: Monday 1-2pm, Wednesday 1-3pm 203 Davis

Schedule

Date Topic Reading Section(s) Notes
1: Tuesday, May 21 Introduction (Slides1) 1.1
2: Thursday, May 23 Stable Marriage Problem (Slides2, notes2) 1.1 cont' (HW0 out)
3: Tuesday, May 28 Gale-Shapley Algorithm, Asymptotic Analysis (Slides3, notes3) 1.2, 2.1-2.4
4: Thursday, May 30 Asymptotic Analysis (Slides4, notes4) 2.1-2.4 (HW1 out )
(HW0 due)
5: Tuesday, June 4 Graph Basics (Slides5, notes5) 2.3, 3.1 Guest Lecture: Swapnoneel Roy
6: Thursday, June 6 BFS and DFS (Slides6, notes6) 3.2 (HW2 out)
(HW1 due)
Guest Lecture: Jimmy Dobler
7: Tuesday, June 11 Runtime of BFS and DFS (Slides7, notes7) 3.3 and 3.6
8: Thursday, June 13 Topological Ordering / Greedy Algorithm Intro (Slides8, notes8) 3.6 and 4.1 (HW3 out)
(HW2 due)
9: Tuesday, June 18 Greedy Algo's: Interval Scheduling (Slides9, notes9) 4.1 and 4.2
10: Thursday, June 20 Greedy Algo's: Shortest Path/Dijkstra (Slides10, notes10) 4.4 (HW4 out)
(HW3 due)
11: Tuesday, June 25 Greedy Algo's: Minimum Spanning Tree (Slides11, notes11) 4.5 and 4.6 (Sample Midterm)
12: Thursday, June 27 Greedy Algo's Wrapup and Midterm Review (notes12) (HW5 out)
(HW4 due)
13: Tuesday, July 2 Midterm
Thursday, July 4 No Class
14: Tuesday, July 9 Midterm Review / Merge Sort (slides14) 5.1
15: Thursday, July 11 Merge Sort (notes15) 5.1 (HW6 out)
(HW5 due)
16: Tuesday, July 16 Counting Inversions (slides16, notes16) 5.3
17: Thursday, July 18 Closest Pair of Points (slides17, notes17) 5.4 (HW7 out)
(HW6 due)
18: Tuesday, July 23 Weighted Interval Scheduling (slides18, notes18) 6.1 and 6.2
19: Thursday, July 25 Bellman-Ford Algorithm (slides19, notes19) 6.8 (HW8 out)
(HW7 due)
20: Tuesday, July 30 P vs NP (slides20) 8.1 (Sample Final)
21: Thursday, August 1 Final Exam Review (review slides) CH 1-6 (HW8 due)
Tuesday, August 6 No Class: Study for final exam
22: Thursday, August 8 Final Exam