Design and Analysis of Algorithms

This is an introductory course on algorithms for B.Sc. second year students. Students from M.Sc. first year are also welcome to take the course.

Teaching assistants: Sushant Agarwal, Apoorva Vijay Tamaskar


Practice problems



Lectures

Topics covered so far:

  1. Aug 3: Introduction, insertion sort, merge sort
  2. Aug 5: Asymptotic notation, recurrences, binary heaps
  3. Aug 10: Heapsort, Quicksort, O(nlog n) lower bound for comparison sort, counting sort, radix sort (Ref. CLRS) Applications of divide-and-conquer: integer multiplication, Strassen's matrix multiplication (Ref: Dasgupta, Papadimitriou, Vazirani)
  4. Aug 12: Selection in worst-case linear time (Ref: CLRS) Greedy and dynamic programming techniques: fractional knapsack, 0/1 knapsack problems
  5. Aug 17: 0/1 knapsack continued, interval scheduling (unweighted and weighted) (Ref: Kleinberg, Tardos), the traveling salesman problem (Ref: Dasgupta, Papadimitriou, Vazirani)
  6. Aug 19: Huffman codes, Independent sets in trees (Dasgupta et al.), Graph algorithms: DFS in undirected and directed graphs (Ref: CLRS, Dasgupta et al.)
  7. Aug 24: BFS, topological sort, strongly connected components, Shortest path: Dijskstra's algorithm (Ref: CLRS)
  8. Aug 26: Dijkstra's algorithm continued, Bellman-Ford, All-pairs shortest paths (Ref: CLRS)
  9. Aug 31: Quiz 1
  10. Sep 2: All-pairs shortest paths: Floyd-Warshall algorithm, transitive closure, spanning trees (Ref: CLRS)
  11. Sep 7: Minimum spanning trees: Prim's and Kruskal's algorithms (Ref: CLRS, Dasgupta, Papadimitriou, Vazirani)
  12. Sep 9: Disjoint-set data structure (union-find) (Ref: Dasgupta et al., wikipedia)
  13. Sep 14: Network flows: Ford-Fulkerson method, max-flow min-cut theorem, applications: bipartite matchings (Ref: CLRS), edge-disjoint paths in graphs (Ref: KT)
  14. Sep 16: Network flows: Edmonds-Karp algorithm (Ref. CLRS)
  15. Sep 28: Linear programming, duality, max-flow min-cut theorem by LP duality (Ref: Dasgupta et al.)
  16. Sep 30: Fast Fourier Transform (Ref: Dasgupta et al.)
  17. Oct 5: Binomial heaps (Ref: Kozen)
  18. Oct 7: Fibonacci heaps (Ref: Kozen)
  19. Oct 12: Stable matchings (Ref: Kleinberg-Tardos)
  20. Oct 14: Hashing (Ref. Sections 11.1-11.3 of CLRS)
  21. Oct 17: NP-completeness: Introduction, decision and optimization problems, reductions among minimum vertex cover, maximum independent set, and max-clique problems (Ref: Kleinberg-Tardos), NP-completeness of Integer linear programming by reduction from minimum vertex cover problem
  22. Oct 19: Circuit-SAT problem, Cook-Levin theorem (a.k.a. Cook's theorem) (Ref: Kleinberg-Tardos)
  23. Oct 21: NP-completeness of 3SAT from Circuit-SAT, reduction from 3SAT to independent set (Ref: Kleinberg-Tardos)
  24. Oct 24: Reduction to Hamiltonian cycle from 3SAT and to Traveling Salesman Problem from Hamiltonian cycle problem (Ref: Kleinberg-Tardos)
  25. Oct 26: Midsem discussion
  26. Nov 4: NP-completeness of subset-sum and 0-1 knapsack (Ref: CLRS), Introduction to approximation algorithms, 2-approximation for vertex cover problem (Ref: CLRS)
  27. Nov 14: 2-approximation for TSP with triangle inequality, inapproximability of general TSP, randomized 8/7-approximation for Max-3-SAT (Ref: CLRS), derandomization using conditional expectation (Ref: this)
  28. Nov 16: Randomized algorithms: success probability amplification, Miller-Rabin primality test (Ref:this)
  29. Nov 18: Miller-Rabin test continued, 2-approximation for Max-Cut by conditional expectation (Ref: Section 1.1 and 1.1.1 of this)