Algorithms

Algorithms
CS207 at IITG by R. Inkulu

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 f_n [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 M_max [note]
- Bipartite: M_max, 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

This is a core course for second-year undergrads. It introduces various algorithm design paradigms and commonly occurring combinatorial problems. The specifc topics planned to be covered include the following -

Design techniques: divide and conquer, greedy, local search, dynamic programming, prune and search, reductions for upper bounding, repeated squaring, fingerprinting, graph traversal, preprocess-query, output-sensitive; Analysis techniques: worst-case, amortized, average-case, expected, bounding error probability.

Graphs: components, minimum spanning trees, shortest paths, network flow, cuts, covers, matchings; Geometry: convex hull, closest pair of points, metric max-min clustering; Numerics: greatest common divisor, fast-fourier transform, integer multiplication, polynomial multiplication, matrix multiplication, boolean-matrix multiplication, primality testing; Strings: pattern matching, common subsequences, sequence alignment; Miscellaneous: job scheduling, knapsack, bin packing, data compression, etc.

Texts:
Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Riverst, and C. Stein, Third Edition. [CLRS]
Algorithm Design by Jon Kleinberg and E. Tardos. [KT]
[Additional resources are provided where necessary.]

Prereqs: CS101, CS201, CS203.

Lectures are held in 5G4, in Slot B: Mon 10-10:55, Th 9-9:55, Fri 9-9:55 am.
The academic calendar is here.

Teaching Assistants: k.abhik@, k.adwaith@, d.animesh@, c.himanshu@.
The set of guidelines for TAs is here.

The grading is relative, and it is based on the total marks obtained in the following:

exam1	14 points	10 am to 11:30 am on 28th Jan (Sat) in L3
mid-sem	18	2 hours; refer to institute time table
exam3	15	10 am to 12 pm on 8th Apr (Sat) in L3
end-sem	25	3 hours; refer to institute time table
surprise (4 to 6)	3*(≥4)	15 minutes each; not scheduled beforehand
homework	0	a couple of problems after every lecture
class participation	4	-

Attendance at each lecture, out of 126 registrants, is here.

Guidelines Spring '23