SYLLABUS
Fundamentals.
- Divide and conquer/ Recursion paradigm- Closest pair among points in a plane
- Polynomial, Matrix multiplication
- Binary search tree (BST), height-balanced
- Augmented BST, Orthogonal range search
- Interval tree, Line Sweep.
- Greedy paradigm-- Job scheduling, Huffman codes, Minimum spanning tree (Prim's)
- Shortest path in a graph (Dijkstra's)
- Directed acyclic graphs, topological order
- DFS and applications
- Dynamic programming paradigm-- LCS, bitonic tour
- Shortest path with negative weights (Bellman-Ford's)
- All-pairs shortest path (Floyd-Warshal's)
- Network Max-flow (Ford-Fulkerson's)
- Max-flow applications
- Amortization paradigm-- Heaps-- Fibonacci
Extra.
- Optimal triangulation of a polygon- Stable marriage problem
- Amortization paradigm-- Dynamic table, Online list search, Binomial Heap
- Pattern matching (Knuth-Morris-Pratt's)
- Reduction paradigm-- NP-hardness
- Approximation algorithms
Schedule.
[17,19-Apr-2018] [pdf] Fibonacci heap.
[05,10,12,17-Apr-2018] [pdf] Max-flow.
[31-Mar, 03,05-Apr] [pdf] Negative weight shortest-paths. All-pairs shortest paths.
[27,31-Mar-2018] [pdf] Dynamic programming. Longest common subsequence. Bitonic tour.
[15,20,22-Mar-2018] [pdf] DFS.
[13-Mar-2018] [pdf] DAGs.
[10,13,15-Feb-2018] [pdf] Minimum spanning tree. Shortest paths.
[08,10-Feb-2018] [pdf] Huffman codes.
[06,08-Feb-2018] [pdf] Job scheduling. Greedy paradigm.
[01,06-Feb-2018] [pdf] Interval tree. Rectangle Overlap.
[30-Jan-2018] [pdf] Orthogonal Range Search.
[25,27,30-Jan-2018] [pdf] Trees & their Operations. Augmented tree.
[23-Jan-2018] [pdf] Matrix Multiplication.
[16,18-Jan-2018] [pdf] Polynomial Multiplication.
[16-Jan-2018] [pdf] Non-dominated points.
[09,11-Jan-2018] [pdf] Merge sort, Median, Closest pair, Convex hull.
[04-Jan-2018] [pdf] Introduction & outline to algorithms.