Algorithms
R. Inkulu at cse.iitg in Spring 2018
Home        Lectures        Exams

Overview      [CLRS]: 5-14, 23-29, 43-49; [note]
Euclid's GCD algo      [CLRS]: 930, 934-936
Divide-Conquer-Combine
• Outline      [CLRS]: 64-67, 88-96
• Finding a maximum subarray      [CLRS]: 68-74
• Counting inversions      [KT]: 221-225
• Integer multiplication: Karastuba's algo      [recursive]; [KT]: 231-234
• Matrix multiplication: Stressen's algo      [CLRS]: 75-82
• Closest pair of points      [KT]: 225-231
• Polynomial multiplication: FFT      [KT]: 234-242
Prune and Search
• Binary search      --- prereq
• Blum et al.'s selection algo      [CLRS]: 220-222
Incremental
• Insertion sort      --- prereq
• Computing the convex hull      [CLRS]: 1039 exer 33.3-5, 33.3-6
Repeated squaring
• Modular exponentiation      [CLRS]: 956-958
• Computing nth Fibonacci number in o(n2) time      [CLRS]: 982 exer 31-3 c, d
Greedy
• Job scheduling      [KT]: 116-131
• Huffman codes      [KT]: 161-175
• Characterizing greedy      [CLRS]: 423-425
Local Search
• Vertex cover      [KT]: 664-666
• Stable configuration      [KT]: 671-675
• Characterizing local search      [KT]: 663-664, 679-680
Dynamic Programming
• Computing nth Fibonacci number in O(n2) time      [CLRS]: 981 exer 31-3 a, b
• Scheduling jobs with profits      [KT]: 252-258
• Parenthesizing matrix-chain multiplication      [CLRS]: 370-377
• Optimal BST      [CLRS]: 397-403
• Sequence alignment      [KT]: 278-282
• Longest common subsequence/substring      [CLRS]: 392-393 --- AR
• Knapsack      [CLRS]: 425-427; [KT]: 266-272
• Characterizing DP      [KT]: 258-260
String matching
• Naive algo       [CLRS]: 985, 988-989
• Rabin-Karp algo       [CLRS]: 990-994
• Pattern fixed: using finite automata       [CLRS]: 995-1002
• Pattern fixed: KMP algo       [CLRS]: 1002-1006
Gale-Shapley's stable matching algo      [KT]: 4-12
Graph traversal
• Connected components       [KT]: 86-87, 94
• SCC: Kosaraju's algo       [CLRS]: 615-620
• SCC: Tarjan's algo       [from AHU]
• Topological ordering      [KT]: 99-104; [CLRS]: 612-614
• 2-CNF satisfiability      [note]
Minimum spanning trees
• Few properties       [CLRS]: 624-626; [KT]: 142-143, 145, 147-148
• Kruskal's, Prim's, Reverse-delete       [KT]: 143-151, 157
• An application: metric max-min clustering       [KT]: 157-161
Shortest paths in weighted digraphs
• Elementary properties       [CLRS]: 643-650, 671
• SSSP: Lawler's, Dijkstra's, Bellman-Ford       [CLRS]: 655-657; [KT]: 137-142, 291-296, 302-304
• APSP: Floyd-Warshall, Johnson's       [CLRS]: 693-697, 700-704
• APD: via distance product       [CLRS]: 686-691
• Transitive closure: Warshall's       [CLRS]: 697-699
Network flows
• Introduction       [CLRS]: 708-712, 720-721
• Ford-Fulkerson algo for max-flow      [CLRS]: 714-727
• Maximum matching in unweighted bipartite graphs       [KT]: 367-370
• A maximum set of edge disjoint s-t paths       [KT]: 373-376, 377-378
• Two applications of s-t min-cut       [KT]: 391-399
• Circulations       [KT]: 378-382, 382-384
• Two applications of circulations       [KT]: 384-391 --- AR
Reductions for lower bounding
• Introduction       [CLRS]: 1051-1052, 1067-1068; [note]
• SAT → 3-SAT → CLIQUE → VC       [CLRS]: 1082-1091
• 3-SAT → HAMCYCLE       [CLRS]: 1091-1096
• 3-SAT → SUBSETSUM       [CLRS]: 1097-1100
• P, NP, NP-hard, NP-complete classes       [CLRS]: 1049-1051, 1061-1066, 1078-1079

* [CLRS]: Introduction to Algorithms by Cormen, Leiserson, Riverst, and Stein, Third Edition.
* [KT]: Algorithm Design by Jon Kleinberg and Eva Tardos.

* AR stands for additional reading (no lecture delivered but included in syllabus).