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: Sayan Bose, Ankan Kar, Utsab Ghosal, Shruti Sharad Patil

Practice problems


The problem set is available here
Starting from week 2 i.e. August 12, you are required to make one submission each week. The requirement is to submit at least one problem a week for 10 weeks, and 20 problem in all. This carries 20% weightage (thus 2 per week or 1 per problem, whichever is smaller in the end).

Lectures

Topics covered so far:

  1. Aug 5: Introduction, sorting: insertion sort, counting sort, \Omega(nlog n) lower bound on comparison based sorting, asymptotic notation (Chapters 2,3, Section 8.1 of CLRS)
  2. Aug 7: Radix sort, concept of stable sort, quick sort, analysis (best case, worst case, balanced case), use of recursion tree for balanced case (0.9 vs 0.1 split) (Sections 7.1,7.2,8.2,8.3 of CLRS)
  3. Aug 12: Recurrence solving (Sections 4.3,4.4,4.5 of CLRS)
  4. Aug 14: Divide-and-conquer: integer multiplication (Section 2.1 of DPV), dynamic programming: matrix-chain multiplication (Section 6.5 of DPV or Section 15.2 of CLRS)
  5. Aug 19: Dynamic programming continued: Rod cutting, optimal binary search trees (Sections 15.1 and 15.5 of CLRS)
  6. Aug 21: Dynamic programming continued: 0/1 knapsack problem, introduction to greedy algorithms and fractional knapsack (Section 6.4 of [DPV], also take a look at these notes and slides)
  7. Aug 26: Fractional knapsack continued, Huffman codes (Ref for fractional knapsack, [DPV] Section 5.2 or [CLRS] Section 15.3 for Huffman codes)
  8. Aug 28: Quiz 1
  9. Sep 2: Huffman codes continued, breadth-first search (Sections 20.1, 20.2 of [CLRS])