CS 381: Material Covered and Reading Assignments


Friday,  December 11
Review
Reading: 

Wednesday,  December 9
Dealing with NP-completeness
Reading:  

Monday,  December  7
NP-completeness reductions
Reading:  



Friday,  December 4
NP-completeness reductions
Reading: 

Wednesday,  December 2
Introduction to NP-completeness, Quiz 3
Reading:  

Monday,  November 30
Classes P and  NP
Reading:  



Friday,  November  27
no class

Wednesday, November  25
no class

Monday,  November 23
Network flow applicatiions; discission of completed homework problems
 


Friday,  November 20
Network flow applications: bipartite matching
Reading: 

Wednesday, November 18
Network flow: Ford Fulkerson algorithm
Reading:  slides, Kleinber-Tardos

Monday, November 16
Introduction to network flow
Reading:  26.1



Friday,  November 13
Application of DFS: strongly connected components 
Reading: 

Wednesday, November 11
Review 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 4
Shortest Paths  (all pairs)
Reading:  25

Monday, November 2
Shortest Paths  (single source)
Reading: 24



Friday, October 30
KMP algorithm
Reading: slides

Wednesday, October 28
Celebrity, Majority; Quiz 2
Reading:  slides

Monday,  October  26
Augmenting Balanced Search Trees
Reading: 14



Friday,  October 23
Fibonacchi Heaps
Reading: 19.1-19.3

Wednesday, October 21
Fibonacchi Heaps
Reading:  19.1-19.3

Monday,  October  19
Amortized analysis
Reading: 17



Friday,  October 16
Kruskal's algorithm; Union-Find implementations
Reading: 23.2, 21

Wednesday, October 14
Introduction to minimum spanning trees; Prim's algorithm
Reading:  23.1, 23.2

Monday,  October 12
no class (October break)


Friday,  October 9
no class

Wednesday, October 7
Balanced search trees: review
Reading:  

Monday,  October 5
Knapsack Problem
Reading:


Friday,  October 2
Return to Dynamic Programming: Longest common subsequence
Reading: 

Wednesday, September 30
More on activity selection and greedy algoriuthms
Reading:  

Monday,  September 28
Introduction to greedy algorithms; Activity selection
Reading:  16.2, 16.2


Friday, September 25
Dynamic Programming: Sequence Alignment
Reading: 

Wednesday, September 23
Dynamic Programming: Rod Cutting
Reading:  15.1, 15.4

Monday,  September 21
Introductuin 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 16
Median Finding and Selection (linear time).  Quiz 1
Reading:  9.3

Monday,  September 14
Median Finding and Selection (probablistic)
Reading: 9.1, 9.2


Friday, September 11
Divide and Conquer algorithms: Counting inversions
Reading: Kleinberg-Tardos slides

Wednesday, September 9
Divide and Conquer algorithms: Skyline, Maximum Subarray
Reading: 4.1

Monday,  September 7
No class. Labor Day


Friday, September 4
Master theorem: uses and limitations
Reading: 4.5, 4.6 (optional)

Wednesday, September 2
Using the recursion tree to solve recurrences; Master Theorem
Reading: 4.4, 4.5

Monday, August 31
Common time complexities. Common recurrence relations in divide and conquer stategies. 
Reading: 3.1, 3.2, 4.3


Friday, August 28
Mergsort as an example of divide and conquer. Asymptotic analysis.
Reading: Appendix A and  B, 3.1

Wednesday, August 26
Review 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.