CS
381: Material Covered and Reading Assignments
Friday, December 11 Review
Reading:
Wednesday, December 9Dealing with NP-completeness
Reading:
Monday, December 7NP-completeness reductions
Reading:
Friday, December 4 NP-completeness reductions
Reading:
Wednesday, December 2Introduction to NP-completeness, Quiz 3
Reading:
Monday, November 30Classes P and NP
Reading:
Friday, November 27 no class
Wednesday, November 25no class
Monday, November 23Network flow applicatiions; discission of completed homework problems
Friday, November 20 Network flow applications: bipartite matching
Reading:
Wednesday, November 18Network flow: Ford Fulkerson algorithm
Reading: slides, Kleinber-Tardos
Monday, November 16Introduction to network flow
Reading: 26.1
Friday, November 13 Application of DFS: strongly connected components
Reading:
Wednesday, November 11Review reductions. Application of DFS: biconnected components
Reading: 22.3
Monday, November 9 Lower bounds and reductions
Reading: 8.1, slides
Friday, November 6 Topological sort; longest s path in dags
Reading: 22.4
Wednesday, November 4Shortest Paths (all pairs)
Reading: 25
Monday, November 2 Shortest Paths (single source)
Reading: 24
Friday, October 30 KMP algorithm
Reading: slides
Wednesday, October 28Celebrity, Majority; Quiz 2
Reading: slides
Monday, October 26Augmenting Balanced Search Trees
Reading: 14
Friday, October 23 Fibonacchi Heaps
Reading: 19.1-19.3
Wednesday, October 21Fibonacchi Heaps
Reading: 19.1-19.3
Monday, October 19Amortized analysis
Reading: 17
Friday, October 16 Kruskal's algorithm; Union-Find implementations
Reading: 23.2, 21
Wednesday, October 14Introduction to minimum spanning trees; Prim's algorithm
Reading: 23.1, 23.2
Monday, October 12no class (October break)
Friday, October 9 no class
Wednesday, October 7Balanced search trees: review
Reading:
Monday, October 5Knapsack Problem
Reading:
Friday, October 2 Return to Dynamic Programming: Longest common subsequence
Reading:
Wednesday, September 30More on activity selection and greedy algoriuthms
Reading:
Monday, September 28Introduction to greedy algorithms; Activity selection
Reading: 16.2, 16.2
Friday, September 25 Dynamic Programming: Sequence Alignment
Reading:
Wednesday, September 23Dynamic Programming: Rod Cutting
Reading: 15.1, 15.4
Monday, September 21Introductuin to Dynamic Programming. Matric Chain product
Reading: 15.2, 15.3
Friday, September 18 Randomized algorithms. Reading: 9.3, 5.1, 5.3
Wednesday, September 16Median Finding and Selection (linear time).
Quiz 1
Reading: 9.3
Monday, September 14Median Finding and Selection (probablistic)
Reading: 9.1, 9.2
Friday, September 11Divide and Conquer algorithms: Counting inversionsReading: Kleinberg-Tardos slides
Wednesday, September 9Divide and Conquer algorithms: Skyline, Maximum Subarray
Reading: 4.1
Monday, September 7No class. Labor Day
Friday, September 4Master theorem: uses and limitations
Reading: 4.5, 4.6 (optional)
Wednesday, September 2Using the recursion tree to solve recurrences; Master Theorem
Reading: 4.4, 4.5
Monday, August 31Common time complexities. Common recurrence relations in divide and conquer stategies.
Reading: 3.1, 3.2, 4.3
Friday, August 28Mergsort as an example of divide and conquer. Asymptotic analysis.
Reading: Appendix A and B, 3.1
Wednesday, August 26Review of proofs by induction and asymptotic notations.
Reading: Chapter 2.3, 3.1
Monday, August 24
Course organization and expectations; what is analysis of algorithms?
Reading: Chapters 1, 2.1, 2.2.