SYLLABUS
Fundamentals.
- Divide and conquer/ Recursion paradigm- Sorting, Median
- Closest pair, Convex Hull, non-Dominated points
- Polynomial, Matrix multiplication (Fast Fourier Transform)
- 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, graph matching, matrix rounding
- Amortization paradigm-- Heaps-- Fibonacci
- Pattern matching (Knuth-Morris-Pratt's)
- Stable marriage problem
Extra.
- Reduction paradigm, Intractability: NP-completeness, reduction, approximation- Amortization paradigm-- Dynamic table, Online list search, Binomial Heap
- Randomized algorithms
- Approximation algorithms
- Machine learning based on gradient descent paradigm
Schedule.
[13Nov-2019] [pdf] Stable Marriage.
[08,11Nov-2019] [pdf] Pattern matching.
[01,04,06,08Nov-2019] [pdf] Amortization. Fibonacci heap.
[21,23,25,28,30Oct-2019] [pdf] Max-flow.
[14,16Oct-2019] [pdf] Negative weight shortest-paths. All-pairs shortest paths.
[27,30Sep,04Oct-2019] [pdf] Dynamic programming. LCS. Bitonic Tour.
[13,23,25,27Sep-2019] [pdf] DFS.
[09,11,13Sep-2019] [pdf] DAGs.
[02,04,06,09Sep-2019] [pdf] Minimum spanning tree. Shortest paths.
[28,30Aug,02Sep-2019] [pdf] Job scheduling. Greedy paradigm. Binary encoding.
[21,23,26Aug-2019] [pdf] Orthogonal Range Search. Interval tree. Rectangle Overlap.
[16,19,21Aug-2019] [pdf] Trees & their Operations. Augmented tree.
[14Aug-2019] [pdf] Matrix multiplication.
[07,09Aug-2019] [pdf] Polynomial multiplication.
[05,07Aug-2019] [pdf] Convex hull, Non-dominated points.
[31Jul,02,05Aug-2019] [pdf] Merge sort, Median, Closest pair.
[29,31Jul-2019] [pdf] Introduction & outline to algorithms.