Time: Mon and Wed, 0955 hrs to 1210 hrs
Location: Auditorium, ISI Bangalore
Instructor: Jaikumar Radhakrishnan
Homepage:
https://www.tifr.res.in/~jaikumar/Courses/ISIBangalore/2023-DAA/
| 7 Aug | 1. Introduction: computational tasks, algorithms, correctness, efficiency Computation with numbers: binary representation, arithmetic, Euclid's gcd algorithm Read: [JE] Chapter 0, [DPV] Chapters 0, 1 Notes: Other material: |
| 9 Aug | 2. Extended Euclid's algorithm, Gaussian elimination; Randomization: verification of matrix products Read: [DPV] Pages 38--45 Notes: Other material: |
| 14 Aug | 3. Verification of matrix products, primality testing Read: [DPV] Pages 38--45 Notes: Primality Testing Notes Other material: |
| 16 Aug | 4. Hashing Read: [DPV] Pages 38--45 Notes: Other material: Randomized Algorithms by Mitzenmacher and Upfal (see Section 15.3, starting at page 399) |
| 21 Aug | 5. Divide and conquer: Karatsuba's algorithm for multiplying numbers, recurrences, mergesort Read: [DPV] Chapter 2, pages 51--56 Notes: Other material: |
| 23 Aug | 6. Randomized Selection, randomized Quicksort, Strassen's fast matrix multiplication Read: [DPV] Chapter 2, pages 60--63 Notes: See Notes for randomized quicksort Other material: See Kevin Wayne's slides listed under [KT] |
| 28 Aug | 7. Fast Fourier transform Read: [DPV] Section 2.6 (pages 64--78) Notes: Other material: Watch this video on FFT. Integer multiplication using FFT: Notes |
| 30 Aug | 8. Basic graph algorithms, graph representation, depth-first search Read: [DPV] (pages 87--92) Notes: Other material: Watch this video on graph representations and this video on DFS. Evasiveness: see the Wiki page |
| 04 Sep | 9. Connectivity in undirected graphs, articulation points Read: [DPV] (pages 92--95) Notes: This python program identifies the cut vertices and also partitions the set of edges into biconnected components. |
| 06 Sep | 10. Biconnected components, DFS in directed graphs Read: [DPV] (pages 95--97) Notes: DFS and biconnected components from Sara Baase's book Computer Algorithms (Second Edition); note that the algorithm presented here computes low numbers (it uses back instead of low number) using the DFS number of the node, not the DFS level; both approaches are valid. |
| 11 Sep | 11. Strongly connected components, Breadth-first search Read: [DPV] (pages 97--100, 109--112) Notes: Correctness of Kosaraju's algorithm The Python program we wrote in class |
| 13 Sep | 12. Dijkstra's algorithm Read: [DPV] (pages 112--118 ) Notes: |
| 20 Sep | 13. Midt-semester Examination Details: The exam will held between 10:00 am and 12:30 pm. All the topics above are part of the syllabus for the midterm exam. Notes: Sample exam, Spring 2023 paper Question paper: |
| 25 Sep | 14. Balanced heaps, the A* algorithm Read: [DPV] (pages 119--123) Notes: Python program (Dijkstra+Balanced Heap) See loop invariant in the comment at bottom of the file. |
| 27 Sep | 15. The Bellman-Ford algorithm, Correctness proof of the Bellman-Ford algorithm, Video: On A* |
| 04 Oct | 16. Greedy algorithms: Kruskal's algorithm for MST, the union-find data
structure, Huffman Coding Notes: Jeremy Kun's blog post Notes from the class Kevin Wayne's slides on path compression |
| 09 Oct | 17. The union-find data structure, the greedy algorithm for matroids, Kraft's inequality, Shannon's source coding theorem, Huffman coding Greedy algorithm for intervals: See Kevin Wayne's slides on interval scheduling based on Chapter 4 of the Kleinberg-Tardos book (see [KT] above). |
| 11 Oct | 18.Entropy and prefix-free codes, Kraft's inequality, Huffman coding Dynamic programming: Longest s-t path in graphs, Longest increasing subsequence in time O(n^2). Notes: Read Chapter 6 of [DPV] (there are many examples there that we did not cover in class) and Chapter 3 of Jeff Erickson's beautiful book: Algorithms book. |
| 16 Oct | 19. Longest increasing sequence in O(n log n) time, the Erdos-Szekeres theorem. Edit distance. Floyd-Warshall all pairs shortest paths, Johnson's algoritm for all pairs shortest-paths in sparse graphs.
Code: The python code we discussed in class: NewLIS.py
|
| 18 Oct | 20. Dynamic programming: the Knuth-Morris-Pratt matching algorithm, Chemical words Code: python code for Knuth-Morris-Pratt algorithm (we did not discuss this in detail: KMP.py, python code for chemicals words: Chem.py. |
| 25 Oct | 21. Matching in bipartite graphs, maximal matching, vertex cover,
the Konig-Egervary theorem, augmenting paths, Berge's theorem on
maximum mathching and existence of alternating paths, bipartite
maximum matching by repeated augmentation. Weighted bipartite matching.
Notes:
Read about the unweighted matching algorithm here. See Chapters 19, 20 of Dexter Kozen's book. |
| 30 Oct | 22. The Hungarian tree, fractional matching and fractional vertex cover, Birkhoff-Von Neumann theorem, Dulmage-Mendelsohn theorem, flows in networks, residual graph, augmenting paths, the Ford-Fulkerson algorithm. Source: see Chapters 16, 17 of Dexter Kozen's book. |
| 1 Nov | 23. Network flows: Examples requiring many
augmentations, decomposing flows using path flows, augmenting by
maximum bottleneck paths and efficient algorithms for networks with integer weights, the Edmons-Karp shortest augmenting path heuristic, the max-flow min-cut theorem. Applications of the integrality theorem, Konig-Egervary theorem from max-flow min-cut, simultaneous rounding of tables,
Source: See Slides by Kevin Wayne |
| 6 Nov | 24.
Computation and verification: the classes P and NP, reductions
The class of NP-complete problems, Primes is in NP, IndependentSet in NP-complete, search reduces to decision |
| 8 Nov | 25. Cook-Levin theorem (SAT is NP-complete), NP-completeness of
Clique, Vertex cover, Dominating set, 3-Coloring Review |
| 17 Nov | End-semseter exam Details: Syllabus From 10:00 am to 12:30 pm |