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: Harish Chandramouleeswaran, Chinmaya Praveen, Rohan Roy

Practice problems



Lectures

Topics covered so far:

  1. Aug 7: Introduction, insertion sort, asymptotic notation (Chapters 2,3 of [CLRS])
  2. Aug 10: Quicksort, use of recursion tree (Sections 7.1,7.2 of [CLRS])
  3. Aug 12: Recurrence solving, nlogn lower bound on comparison sorting (Sections 4.3,4.4,4.5 of [CLRS], Section 2.2 of [DPV] for the statement of Master method, Section 2.3 for the lower bound)
  4. Aug 14: Heapsort, counting sort (Sections 6.1-6.4, Section 8.2 of [CLRS])

    5. August 19,21: No class, instructor traveling
  5. Aug 26: Integer multiplication, radix sort, selection in linear time (Section 2.1 of [DPV], Sections 8.3,9.3 of [CLRS])

    6. Aug 28: Quiz 1
  6. Sep 2: Introduction to dynamic programming: Matrix chain multiplication (CLRS Section 14.2), 0/1 knapsack (Section 6.4 of [DPV])
  7. Sep 4: 0/1 knapsack continued, Greedy algorithms: fractional knapsack Ref)
  8. Sep 9: More on dynamic programming: optimal binary search trees, independent sets in trees (Section 14.5 of [CLRS], Section 6.7 of [DPV])
  9. Sep 11: Connectivity in graphs: DFS, BFS (Sections 20.1-20.3 of [CLRS], Sections 3.2,3.3,4.2 of [DPV])
  10. Sep 16: Topological sort, strongly connected components (Sections 20.4,20.5 of [CLRS], Section 3.4 of [DPV])
  11. Sep 18: Strongly connected components continued, doubt clearing for mid-semester exam.

    12. Midsem exam week
  12. Sep 30: Single-source shortest paths: Dijkstra's algorithm (Sections 4.3,4.4 of [DPV], Section 22.3 of [CLRS]
  13. Oct 7: Shortest paths with negative weights: Bellman-Ford algorithm (Section 22.1 of [CLRS], Section 4.6 of [DPV])
  14. Oct 9: All-pairs shortest paths, transitive closure, introduction to minimum spanning trees: greedy approach (Sections 23.1,23.2,21.1 of [CLRS])
  15. Oct 14: Prim's and Kruskal's algorithms (Section 21.2 of [CLRS])
  16. Oct 16: Analysis of disjoint set data structure: O(mlog*n) bound (Section 5.1.4 of [DPV], also see this proof)