| Syllabus |
| Lecture 1 and
2 (by Arup Guha on 23/08 and 25/08)
|
| Lecture 3 (01/09)
| Adjacency matrix, adjacency list |
Depth-first search in undirected graphs
- Procedures explore(G,v) and dfs(G)
- DFS search tree/forest
- Types of edges (tree and back edges)
- Connected components in undirected graphs
- Previsit and postvisit orderings
|
|
| Lecture 4 (06/09)
Depth-first search in directed graphs
- Types of edges (tree, forward, back, and cross edges)
|
| Topological sorting |
| Strongly connected components |
|
| Lecture 5 (08/09)
| Algorithm for finding strongly connected components
(variant in DPV book) |
| Breadth first search |
|
| Lecture 6 (13/09)
| Algorithm for finding strongly connected components
(variant in CLRS book) |
| Dijkstra's algorithm |
|
| Lecture 7 (15/09)
| Analysis of Dijkstra's algorithm (array and heap
implementations of priority queue) |
| Bellman-Ford algorithm |
|
| Lecture 8 (20/09)
| Finding shortest paths in DAGs with negative edge
weights |
| Kruskal' algorithm, cut property |
|
| Lectrure 9 (22/09)
| Data structure for disjoint sets, union by rank |
| Overview of path compression |
|
| Lecture 10 (27/09)
| Prim's algorithm |
| Approximation algorithm for set cover |
|
| Lecture 11 (29/09)
| Randomized algorithm for min-cut based on Kruskal's algorithm
|
| Randomized algorithm for min-cut based on edge contraction |
|
| Lecture 12 (04/10)
|
| Lecture 13 (11/10)
| Reading assignment: Huffman encoding and Horn formulas |
| Shortest paths in DAGs |
| Longest increasing subsequences |
| Knapsack with repetition |
|
| Lecture 14 (13/10)
| Reading assignment: edit distance, chain matrix
multiplication and independent sets in trees |
| Knapsack without repetition |
| Shortest reliable paths |
| All-pairs shortest paths, Floyd-Warshall algorithm |
|
| Lecture 15 (18/10)
| Reading assignment: sections 7.1 and 7.2 in DPV book |
| Dynamic programming algorithm for traveling salesman problem |
| Flow networks (section 26.1 in CLRS book) |
|
| Lecture 16 (20/10)
| Ford-Fulkerson method |
| Residual networks |
| Augmenting paths |
| Cuts of flow networks |
|
| Lecture 17 (25/10)
| Max-flow min-cut theorem |
| Analysis of Ford-Fulkerson method |
|
| Lecture 18 (27/10)
| Analysis of Edmonds-Karp algorithm |
|
| Lecture 19 (01/11)
| Introduction to linear programming |
|
| Lecture 20 (01/11)
| Reduction of max-flow to linear programming |
| Bipartite matching |
| Duality |
|
| Lecture 21 (08/11)
| Overview of the simplex method |
|
| Lecture 22 (10/11)
|
| Lecture 23 (15/11)
| Solution of the DP problems on the second exam |
| Dealing with NP-completeness, backtracking |
|
| Lecture 24 (17/11)
| Branch-and-bound |
| Approximation algorithm, approximation ratio |
| Approximation algorithm for vertex cover |
| Lecture 24 (22/11)
| Approximation algorithm for clustering |
| Approximation algorithm for metric TSP |
| Lecture 24 (24/11)
| Solution to LP problem on second exam |
| Approximation for knapsack without repetition |
|
| |
