CS 580: Material Covered and Reading Assignments

---

Thursday, April 29
Review, discussion of selected assignments, Q&A

Tuesday, April 27
Finish approximation algorithms and NP-completeness (vertex cover, TSP)

Thursday, April 22
Approximation algorithms (makespan, vertex cover)
Reading: 35

Tuesday, April 20
NP-completeness reductions (3-SAT, clique, vertex cover, Hamiltonian Cycle, scheduling)
Reading: 34.2-5

Thursday, April 15
Introduction to NP-completeness and reductions
Reading: paper on BB, 34.1-2

Tuesday, April 13
All pairs shortest paths algorithms; classes P and NP
Reading: 25

Thursday April 8
Shortest paths algorithms
Reading: 24, 25

Tuesday, April  6
Applications of DFS:  biconnectivity, stronlgy connected components
Reading: 22

Thursday,  April 1
Range queries on 2-dimensional data;  review of graph traversals 
Reading: 22

---

Tuesday, March 30
Examples of other balanced tree queries; range queries
Reading: 14

Thursday, March 25
Computational geeometry: convex hull and closest pair algorithms
Reading: 33.3, 33.4

Tuesday, March 23
Red-Black trees: basic and augmenting operations
Reading: 13, 14

Thursday, March 18
no class  - Spring break

Tuesday, March 16
no class  
no class - Spring break

Thursday, March 11
no class  

Tuesday,  March 9
Finish any remaining material, review for midterm

Thursday,  March 4
Lower bounds: decision tree arguments,  reductions, adversary arguments
Reading: 8.1

Tuesday,  March 2
Dynamic Programming
Reading: 15

---

Tuesday, February 25
Introduction to Dynamic Programming  
Reading: 15

Tuesday, February 23
no class

Thursday, February 18
Fibonacchi heaps  
Reading: 19 + slides on BB

Tuesday, February 16
Amortized analysis: examples and methods 
Reading: 17

Thursday, February 11
Kruskal's Algorithm. Implementations of Union-Find operatios. 
Reading: 23.2, 21.1-3

Tuesday, February 9
Prim's algorithm for finding a minimum spanning tree
Reading: 23

Thursday, February 4 
Fractional Knapsack, greedy minimum spannging tree algorithms
Reading:  23

Tuesday, February 2 
Greedy algorithms: activity selection, 0/1 Knapsack,
Reading: 16.1-3

---

Thursday, January 28
Review of heaps as a priority queue; introduction to greedy algorithms
Reading:  6, 10, 11, 12

Tuesday, January 26
Randomized selection, linear time selection
Reading: 9.2, BB material

Thursday, January 21
Master theorem. Brief introduction to randomized algorithms
Reading: 4.4-4.6, 5.1-5.2  

Tuesday, January 19
Divide-and-conquer: two solution for the maximum subarray problem; solving recurrences.
Reading: 4.1-4.4

Thursday, January 14
Asymptotic notation, divide and conquer
Reading: 2.3, 4.1

Tuesday, January 12
Course organiuzation and overview; getting started on analyzung algorithms
Reading: 1-3

All reading assignments refer to the 3rd Edition of the text book.

---