Design and Analysis of Algorithms

This is an introductory course on algorithms for B.Sc. second year students.

Reference books

  1. [CLRS]: Introduction to Algorithms (4th edition) by Cormen, Leiserson, Rivest, and Stein
  2. [JE]: Algorithms by Jeff Erickson
  3. [KT]: Algorithm Design by Kleinberg and Tardos
  4. [DPV]: Algorithms by Dasgupta, Papadimitriou, Vazirani online copy
Teaching assistants: Sayan Bose, Ankan Kar, Utsab Ghosal, Shruti Sharad Patil

Practice problems


The problem set is available here
Starting from week 2 i.e. August 12, you are required to make one submission each week. The requirement is to submit at least one problem a week for 10 weeks, and 20 problem in all. This carries 20% weightage (thus 2 per week or 1 per problem, whichever is smaller in the end).

Lectures

Topics covered so far:

  1. Aug 5: Introduction, sorting: insertion sort, counting sort, \Omega(nlog n) lower bound on comparison based sorting, asymptotic notation (Chapters 2,3, Section 8.1 of CLRS)
  2. Aug 7: Radix sort, concept of stable sort, quick sort, analysis (best case, worst case, balanced case), use of recursion tree for balanced case (0.9 vs 0.1 split) (Sections 7.1,7.2,8.2,8.3 of CLRS)
  3. Aug 12: Recurrence solving (Sections 4.3,4.4,4.5 of CLRS)
  4. Aug 14: Divide-and-conquer: integer multiplication (Section 2.1 of DPV), dynamic programming: matrix-chain multiplication (Section 6.5 of DPV or Section 15.2 of CLRS)
  5. Aug 19: Dynamic programming continued: Rod cutting, optimal binary search trees (Sections 15.1 and 15.5 of CLRS)
  6. Aug 21: Dynamic programming continued: 0/1 knapsack problem, introduction to greedy algorithms and fractional knapsack (Section 6.4 of [DPV], also take a look at these notes and slides)
  7. Aug 26: Fractional knapsack continued, Huffman codes (Ref for fractional knapsack, [DPV] Section 5.2 or [CLRS] Section 15.3 for Huffman codes)
  8. Aug 28: Quiz 1
  9. Sep 2: Huffman codes continued, breadth-first search (Sections 20.1, 20.2 of [CLRS])
  10. Sep 4: BFS continued, DFS (Sections 20.2, 20.3 of [CLRS])
  11. Sep 9: Topological sort, introduction to strongly connected components (Sections 20.4, 20.5 of [CLRS])
  12. Sep 11: Strongly connected components, Dijkstra's algorithm for single-source shortest paths (Sections 22.1, 22.3 of [CLRS])
  13. Sep 16: Quiz 1 discussion
  14. Sep 18: Correctness of Dijkstra's algorithm, Bellman-Ford algorithm (Sections 22.3, 22.2 of [CLRS])
  15. Sep 20 (Extra class 1.5 hours): Minimum spanning trees: Prim's and Kruskal's algorithms, union-find data structure (Chapter 21 of [CLRS])

    16. Midsem week, faculty talks week
  16. Oct 10: All-pairs shortest paths (Sections 23.2, 23.2 from [CLRS])
  17. Oct 14: Network flows: Ford-Fulkerson method, and its complexity (Section 24.1, 24.2 of [CLRS])
  18. Oct 16: Correctness of Ford-Fulkerson method: Max-flow min-cut theorem (same ref), application to bipartite matchings
  19. Oct 21: Edmonds-Karp algorithm (Section 24.2 of [CLRS])
  20. Oct 23: Introduction to Linear Programming: Writing problems as linear programs e.g. maximum matching, max-flow, constructing dual LP (Sections 7.1-7.4 of [DPV])
    21. strong duality without proof, Konig's theorem via strong duality
  21. Oct 28: Max-flow min-cut theorem via strong duality, divide-and-conquer: FFT algorithm for polynomial multiplication (Section 2.6 of [DPV])
  22. Oct 30: NP-completeness: Decision problems, definitions of P and NP, NP-hard and NP-complete problems, simple reductions: Clique, vertex cover, independent set (relevant parts of Chapter 8 of [DPV])
  23. Nov 4: Quiz 2
  24. Nov 6: 3-SAT to clique reduction (Section 34.5.1 of [CLRS])
  25. Nov 11: Tutorial on reductions: k-SAT to 3-SAT, subset-sum to partition (Ref: Chapter 34 of [CLRS])
  26. Nov 13: Decision problems as languages, Proof sketch of Cook-Levin theorem, SAT to 3-SAT reduction (Sections 34.3,34.4 of [CLRS])
  27. Nov 18: 3-SAT to Subset-sum reduction (Section 34.5.5 of [CLRS), 3-SAT to Hamiltonian cycle reduction (Section 8.5 of Kleinberg-Tardos book)
  28. Nov 20: What next: introduction to approximation and randomized algorithms through 1/2-approximation and 7/8-approximation for 3-SAT, derandomization by conditional expectation