-
Introduction
[CLRS]: 5-14, 23-29, 43-49; [note]
-
Euclid's GCD
[CLRS]: 930, 934-936
-
Prune and Search
-
Binary search
[CLRS]: 39 exer 2.3-5, 2.3-6
-
Blum et al.'s selection
[CLRS]: 220-222
-
Divide and conquer
-
Introduction
[CLRS]: 65-67, 88-96
-
Finding a maximum subarray
[CLRS]: 68-74
-
Stressen's matrix multiplication
[CLRS]: 75-82
-
Integer multiplication
[intro]; [KT]: 231-234
-
Counting inversions
[KT]: 221-225
-
Closest pair of points
[KT]: 225-231
-
Polynomial multiplication with FFT
[KT]: 234-242
-
Greedy
-
Three job scheduling problems
[KT]: 116-131
-
Huffman's optimal prefix code
[KT]: 161-175
-
Vertex cover apprx
[CLRS]: 1108-1111
-
Two characteristics
[CLRS]: 423-425
-
Some more preliminaries
[note]; [note]
-
Repeated squaring
-
Modular exponentiation
[CLRS]: 956-958
-
Computing fn
[CLRS]: 982 exer 31-3 c, d; [note]
-
Intro to primality testing
[note]
-
Local search
-
Vertex cover
[KT]: 664-666
-
Finding a stable configuration
[KT]: 671-675
-
Max cut apprx
[KT]: 676-678
-
Dynamic Programming
-
Job scheduling with positive profits
[KT]: 252-258
-
Parenthesizing matrix chain multiplication
[CLRS]: 370-377
-
Optimal BST
[CLRS]: 397-403
-
Sequence alignment
[KT]: 278-282
-
Knapsack
[CLRS]: 425-427; [KT]: 266-272
-
Two fingerprinting techniques
[note]: 1-2
-
Boolean product witness matrix
[note]
-
String matching
-
Rabin-Karp's
[CLRS]: 985, 988-994
-
Rabin-Karp's Monte Carlo
[note]: 3
-
Using DFA
[CLRS]: 995-1002
-
Knuth-Morris-Pratt (proofs omitted)
[CLRS]: 1002-1006
-
Gale-Shapley's stable matching
[KT]: 4-12, 45-47
-
Components in graphs
-
A quick review of DFT properties
[CLRS]: 603-610 --- AR
-
Connected components
[KT]: 86-87, 94
-
Topological ordering
[KT]: 99-104; [CLRS]: 612-614
-
Tarjan's SCC finding
[note]
-
SCC finding by Kosaraju
[CLRS]: 615-620
-
An appl of SCCs: 2-SAT
[note]
-
Biconnected components
[CLRS]: 621-622 exer 22-2 --- AR
-
Minimum spanning trees
-
A few properties
[CLRS]: 624-626; [KT]: 142-143, 145, 147-148
-
Kruskal's, Prim's
[KT]: 143-151, 157
-
Boruvka's
[note]: 1-2
-
An appl: max-min clustering
[KT]: 157-161
-
Edmonds' min-cost arborescence
[KT]: 177-183
-
Shortest paths
-
Elementary properties
[CLRS]: 643-650, 671
-
A quick review of BFT properties
[CLRS]: 594-601 --- AR
-
SSSP: Lawler's
[CLRS]: 655-657
-
SSSP: Dijkstra's
[KT]: 137-142
-
SSSP: Bellman-Ford's
[KT]: 291-297, 302-304
-
APD via distance product
[CLRS]: 686-691
-
APSP: Floyd-Warshall's
[CLRS]: 693-697
-
Transitive closure: Warshall's
[CLRS]: 697-699
-
APSP: Johnson's reweighting
[CLRS]: 700-704
-
LP formulation examples
[CLRS]: 859-863; [more]
-
Network flow
-
Flow networks and cuts
[CLRS]: 708-712, 720-723
-
Ford-Fulkerson's max-flow
[CLRS]: 714-720, 723-727
-
Augmenting paths for bipartite Mmax
[note]
-
Bipartite: Mmax, Konig's, Hall's
[KT]: 367-373; [wiki]
-
Menger's: s-t edge-disjoint versions
[KT]: 373-378
-
Two more applications of s-t min-cut
[KT]: 391-399
-
Karger's global min-cut
[KT]: 714-719
-
Circulations
[KT]: 378-384
-
Two applications of circulations
[KT]: 384-391 --- AR
-
More graph algorithms --- covered for grad students earlier
-
Edmonds-Karp's max-flow
[CLRS]: 727-730
-
Preflow-push max-flow
[KT]: 357-367
-
Edmonds maximum cardinality matching
[ScN]: 40-41, 45, 81-84
-
Shortest paths in weighted undirected graphs
[ChekN]
-
Auslander & Parter's planarity testing algorithm
[Batti]: 74-81
-
Lipton & Trajan's planar separator theorem
[Koz]: 77-83
-
[CLRS]: Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Riverst, and C. Stein, Third Edition.
-
[KT]: Algorithm Design by Jon Kleinberg and E. Tardos.
-
Additional resources are provided where necessary.
-
AR stands for additional reading (no lecture delivered but included in syllabus).