**1. Divide and conquer (and solving recurrences)**

- Sorting (Jan 9)
- Solving recurrences, lowerbound on sorting (Jan 12)
- Integer multiplication, Master theorem (Jan 14)
- k-Selection algorithm (Jan 16)
- multiplying polynomials (Jan 21)

**EXAM I — Jan 23.**

- Graphs, connected components (Jan 26)
- BFS and DFS (Jan 28)
- Strong connectivity in directed graphs (Jan 30)
- Strong connectivity continued (Feb 2)

**3. Greedy**

- Minimum Spanning Tree (Feb 2)
- Kruskal’s and Prim’s algorithms for MST (Feb 4)
- Greedy algorithms, Matroids (Feb 6)
- Huffman Encoding (Feb 9)

**4. Dynamic Programming**

- Dijkstra, All-pairs shortest path (Feb 11)
- Edit distance, Longest increasing subsequence (Feb 13)
- Matrix Chain Multiplication (Feb 18)

**EXAM II — Feb 16**

**5. P, NP, co-NP, NP ∩ co-NP **(Feb 20)

**6. ****Graph/Network algorithms:**

- Matchings in bipartite graphs (Feb 23)
- Matchings in bipartite graphs II (Feb 27)
- Matchings in general graphs (Mar 02)
- Max-flow min cut theorem I (Mar 4)
- Max-flow min cut theorem II (Mar 6)
- Max-flow min cut theorem III (Mar 9)

**EXAM III — Mar 13.**

**7. Linear Programming **

**8. NP-completeness **(Mar 30, Apr 1, 3)

**9. ****Numbers and Polynomials **(Apr 6, 8, 10)

- RSA (Apr 6)
- Primality Testing (Apr 8)

**10. Gaussian elimination **(Apr 13)

**EXAM IV — Apr 15.**

Christos Papadimitriou Lecture (ARC7, April 17th).

**Projects — Apr 20,22,24.**

Advertisements

Will Dynamic Programming be tested on Test 3?

4. Dynamic Programming

Dijkstra, All-pairs shortest path (Feb 11)

Edit distance, Longest increasing subsequence (Feb 13)

Matrix Chain Multiplication (Feb 18)

5. P, NP, co-NP, NP ∩ co-NP (Feb 20)

6. Graph/Network algorithms:

Matchings in bipartite graphs (Feb 23)

Matchings (Feb 25)

k-connectivity (Feb 27)

Max-flow min cut theorem, flow algorithms (Mar 2,4,6)

Is this the summary of every lecture that will be on Exam 3?