Schedule

1. Divide and conquer (and solving recurrences)

EXAM I — Jan 23.

2. DFS, connected components 

3. Greedy

4. Dynamic Programming

EXAM II — Feb 16

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

6. Graph/Network algorithms:

EXAM III — Mar 13.

7. Linear Programming 

 

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

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

10. Gaussian elimination (Apr 13)

EXAM IV — Apr 15.

Christos Papadimitriou Lecture (ARC7, April 17th).

Projects — Apr 20,22,24.

Advertisements

2 Comments

  1. 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?

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s