CS577 Introduction to Algorithms Course Syllabus and Schedule

Lectures: TR 1-2:15pm in 1313 Sterling Hall.
Discussions: F 1:20-2:10pm in B2550 Morgridge Hall.
Schedule will be updated and refined throughout the semester.
Week 1:
9/4: Intro (course overview, logistics, stable marriage)
Week 2:
9/9: Review of prerequisites (algorithm correctness, abstract data types, graph basics)
9/11: Divide & Conquer (merge sort, sorting lower bound, counting inversions)
Week 3:
9/16: Divide & Conquer (closest pair of points, polynomial multiplication)
9/18: Divide & Conquer (integer multiplication, selection)
Week 4:
9/23: Dynamic Programming (Fibonacci, weighted interval scheduling)
9/25: Dynamic Programming (knapsack, longest increasing subsequence)
Week 5: 
9/30: Dynamic Programming (edit distance, RNA secondary structure)
10/2: Dynamic Programming (shortest paths)
Week 6: 
10/7: Greed (staying ahead: unweighed interval scheduling, knapsack with uniform values)
10/9: Greed (staying ahead: shortest paths)
Week 7:
10/14: 1st Midterm Exam
10/16: Midterm discussion & catch-up
Week 8:
10/21: Greed (exchange: unweighted interval scheduling, minimizing maximum lateness, optimal binary codes)
10/23: Greed (exchange: minimum spanning trees)
Week 9: 
10/28: Network Flow (network, flow, cut, max-flow vs. min-cut, path augmentation)
10/30: Network Flow (scaling, blocking shortest paths, push relabel)
Week 10:
11/4: Network Flow (edge-disjoint paths, bipartite matching)
11/6: Network Flow (survey design, image segmentation, project selection)
Week 11:
11/11: Reductions (optimization vs. search vs. decision)
11/13: Reductions (independent set vs. CNF-SAT)
Week 12:
11/18: 2nd Midterm Exam
11/20: Computational Intractability (P vs NP, NP-completeness)
Week 13:
11/25: Computational Intractability (NP-completeness: circuit-SAT, 3-SAT; 2-SAT)
11/27: No class (Thanksgiving)
Week 14:
12/2: Computational Intractability (NP-completeness: clique, vertex cover, graph coloring, subset sum)
12/4: Computational Intractability (how to handle)
Week 15:
12/9: Randomness (selection, sorting, hashing, polynomial identity testing)
12/13, 7:25-9:25pm, 6203 Social Sciences: Final Exam