CPSC 411 Design and Analysis of Algorithms

Teaching Assistant: Wen Li
Office: Reed McDonald 229A
Office Hours: M 1:30pm-3:30pm, T 3:50pm-5:50pm.
e-mail: emmalwen at gmail.com

Announcments

• Culture assignment 1 is due on Sep 15 (alternatively, you can review John Hopcroft's Turing award lecture)
• Culture assignment 2 is due on Sep 29 (alternatively, you can review Don Knuth's Turing award lecture)
• Culture assignment 3 is now due on Oct 20 (alternatively, you can review Edsger Dijkstra's Turing award lecture)
• Culture assignment 4 is now due on Nov 03 (alternatively, you can review Nicklaus Wirth's Turing award lecture)
• Culture assignment 5 is now due on Nov 19 (alternatively, you can review Richard Karp's Turing award lecture)
• Here is a sample midterm.

Homework

• Problem Set 1 due Sep 10.
• Problem Set 2 due Sep 17.
• Problem Set 3 due Sep 24.
• Problem Set 4 due Oct 01.
• Problem Set 5 due Oct 13.
• Problem Set 6 due Oct 29.
• Problem Set 7 due Nov 05.
• Problem Set 8 due Nov 17.

Schedule

T	Sep 1	Introduction
R	Sep 3	Asymptotic Notations
T	Sep 8	Greedy Algorithms, Matroids
R	Sep 10	Greedy Algorithms, Accessible Set Systems, Dynamic Programming, Quiz 1, Pretest
T	Sep 15	Dynamic Programming, Amortized Analysis
R	Sep 17	Divide-and-Conquer, Quiz 2
T	Sep 22	Disjoint Sets
R	Sep 24	Algorithm Design, Longest Common Subsequence, Quiz 3
T	Sep 29	Graphs, Breadth First Search, Depth First Search
R	Oct 01	Topological Sorting, Strongly Connected Components, Quiz 4
T	Oct 06	Dijkstra's Single-Source Shortest Path Algorithms, Giving Change
R	Oct 08	Bellman Ford Algorithm, Floyd-Warshall Algorithm, Quiz 5
T	Oct 13	Review
R	Oct 15	Midterm exam
T	Oct 20	Basic Notions of Probability Theory
R	Oct 22	Randomized Mincut Algorithm
T	Oct 27	Random Variables, Probabilistic Method
R	Oct 29	Randomized Quicksort, Expected Running Time, Quiz 6
T	Nov 03	Monte Carlo Method; Markov, Chebychev, and Chernoff inequalities
R	Nov 05	Skip Lists, Quiz 7
T	Nov 10	P vs. NP
R	Nov 12	NP Completeness, Quiz 8
T	Nov 17	Vertex Cover, more NP complete problems, Quiz 9
T	Nov 19	3D Matching, Approximation Algorithms

Lecture Notes and Slides

• Slides Set 1: Introduction
• Slides Set 2: Asymptotic Notations
• Slides Set 3: Greedy Algorithms for Matroids
• Slides Set 4: Greedy Algorithms for Accessible Set Systems
• Slides Set 5: Dynamic Programming
• Slides Set 5b: Dynamic Programming
• Slides Set 6: Amortized Analysis
• Slides Set 6b: Divide and Conquer
• Slides Set 7: Disjoint Sets
• Slides on Algorithm Design
• Slides Set 8: Graph Algorithms
• Slides Set 9: Single-Source Shortest Path Algorithms
• Slides Set 9b: The Floyd-Warshall Algorithm
• Review of Midterm Exam
• Lecture Notes Set 10: Probability Theory
• Lecture Notes Set 11: Minimum Cut
• Slides Set 12: NP Completeness
• Slides Set 12b: 3D Matching, ZOE, ILP
• Slides Set 13: Undecidability