## 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

### 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

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