CS 381: Material Covered 

---

Thursday, April 16
Network flow applications
Reading:  

Tuesday, April 14
Introduction to network flow and min cut
Reading: 

---

Thursday, April 9
Finding the strongly connected components; Quiz 2
Reading:  

Tuesday, April 7
An application of DFS: finding biconnected components; DFS in directed graphs 
Reading: 22.3

---

Thursday,  April 2
Fibonacci Heaps; Bellman Ford algorithm
Reading:  19.1-19.3

Tuesday, March 31
Amortized analysis
Reading: 17

---

Thursday, March 26
Greedy graph algorithms:  Kruskal, Prim, Dijkstra
Reading: 23, 24.3

Tuesday, March 24
Reductions to prove lower bounds; review of graphs and minimum spanning trees
Reading: B.4, B.5, 22

---

Thursday, March 12
Lower bounds and problem reduction
Reading: 8.1

Tuesday, March 10
Algorithms that don't fit the strategies discussed
Reading: Slides, 17

---

Thursday, March 5
Augmenting balanced search trees; fractional Knapsack
Reading: 14

Tuesday, March 3
Operations on Red Black Trees
Reading: 13

---

Thursday, February 26
Activity Selection and Activity Scheduling. Review of data structures used in greedy algorithms.
Reading: 16.1, 16.2, 12, 6.1-6.3

Tuesday, February 24
no class

---

Thursday, February 19
Finish dynamic programming.Introduction to greedy algorithms
Reading: 16.1, 16.2

Tuesday, February 17
More dynamic programming: rod cutting, longest common subsequence; Knapsack problem
Reading:  15.1, 15.4

---

Thursday, February 12
Sequence alignment; Quiz 1 (in class)
Reading: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/ ; see  http://people.cs.clemson.edu/~bcdean/dp_practice/  for more DP examples

Tuesday, February 10
Introduction to dynamic programming; matrix chain multiplication
Reading:  15.2, 15.3

---

Thursday, February 5
Linear time selection, randomized and probabilistic algorithms
Reading:  9, 5

Tuesday, February 3
Divide and Conquer:  counting inversions, linear time selection
Reading: 7.3, 9

---

Thursday, January 29
Divide and conquer algorithms: Skyline problem; maximum subsequence, inversions
Reading: 4.1, see also selected slides in http://www.cs.princeton.edu/~wayne/kleinberg-tardos/

Tuesday, January 27
Master Theorem; derivation, uses and examples.
Reading: 4.5

---

Thursday, January 23
Introduction to Supplemental Instruction; review and examples

Tuesday, January 20
Asymptotic analysis. Common recurrence relations in divide and conquer stategies. recursion tree methods
Reading: Chapter 4.3, 4.4

---

Thursday, January 15
Review of proofs by induction. Mergsort as an example of divide and conquer. Asymptotic notations.
Reading: Chapter2.3, Appendix A and  B

Tuesday, January 13
Course organization and expectations; what is analysis of algorithms?
Reading: Chapters 1, 2.1, 2.2.

---