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



Lectures

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

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

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

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

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