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. The course will be offered online due to the COVID-19 pandemic.

Reference books

  1. Algorithm Design by Kleinberg and Tardos
  2. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
  3. Algorithms by Dasgupta, Papadimitriou, Vazirani online copy
Instructors: G. Philip, Prajakta Nimbhorkar
Teaching assistants: Archit Chauhan, Adwitee Roy, Ashwani Anand, Satyaprakash Nayak, A. R. Sricharan

Practice problems


Topics covered so far:

  1. Aug 17 [GP]: Introduction, Euclid's GCD algorithm
  2. Aug 24 [GP]: Analysis of Euclid's GCD algorithm, Sorting: Insertion sort
  3. Sept 1 [GP]: Asymptotic notation (Section 3.1 of CLRS)
  4. Sept 1 [PN]: Heapsort (Sections 6.1-6.4 of CLRS)
  5. Sept 5 [PN]: Quicksort (Sections 7.1,7.2,7.4 of CLRS)
  6. Sept 8 [PN]: Analysis of quicksort, Omega(n log n) lower bound on sorting using comparisons, counting sort (Sections 8.1, 8.2 of CLRS)
  7. Sept 11 [PN]: Radix sort (Section 8.3 CLRS)
  8. Sept 15 [GP]: Divide-and-conquer: Merge sort, integer multiplication
  9. Sept 19 [PN]: Median and order statistics: Selection in linear time (Sections 9.1, 9.3 CLRS)
  10. Sept 22 [PN]: Dynamic programming: The rod cutting problem (Section 15.1 CLRS)
  11. Sept 25 [PN]: Dynamic programming continued: Longest common subsequence
  12. Sept 29 [PN]: Dynamic programming continued: 0/1 knapsack problem (Section 6.4 of DPV), Introduction to greedy algorithms: fractional knapsack (Section 3.1 of these notes)
  13. Oct 1 [GP]: Recurrence solving methods
  14. Oct 6 [PN]: Greedy algorithms continued: Activity selection

  15. Oct 9 [PN]: Doubts clearing session for Quiz 1 preparation

  16. Oct 13 [PN]: Graph algorithms: Breadth-first search
  17. Oct 16 [PN]: Depth-first search, types of edges, properties
  18. Oct 20 [PN]: Single source shortest paths: Dijkstra's algorithm
  19. Oct 23 [PN]: Applications of DFS: Topological sort, strongly connected components
  20. Oct 27 [PN]: Bellman-Ford algorithm, all-pairs-shortest-paths: Floyd-Warshall algorithm
  21. Oct 30 [PN]: Spanning trees: generic greedy method, Prim's and Kruskal's algorithms
  22. Nov 4 [PN]: Analysis of Kruskal's algorithm: union-find
  23. Nov 6 [PN]: Union-find with path compression O(log*n) amortized bound
  24. Nov 11 [PN]: Network flows: Ford-Fulkerson method, max-flow min-cut theorem
  25. Nov 13 [PN]: Network flows: Edmonds-Karp algorithm, application to bipartite matching

  26. Nov 20 [PN]: Doubts clearing session for Quiz 2 preparation

  27. Nov 25 [PN]: Fast Fourier transform
  28. Nov 27 [PN]: Introduction to P,NP, NP-completeness, reductions
  29. Dec 2 [PN]: NP-completeness continued: reduction from 3SAT to clique, brief sketch of Cook-Levin theorem
  30. Dec 4 [PN]: NP-completeness of subset-sum by a reduction from 3SAT, introduction to approximation algorithms: 2-approximation to vertex cover
  31. Dec 5 [PN]: Introduction to randomized algorithms and derandomization by conditional expectations: max-3SAT and max-cut

  32. Dec 18 [PN]: Doubts clearing session for Quiz 3 preparation