CS1.301 Algorithm Analysis and Design (Monsoon 2022)


  • Teaching assistants: Posted on Moodle
  • Schedule: Lectures: Wednesday and Saturday, 10:00 – 11:25, Tutorial: Wednesday, 14:00 - 15:00
  • Classroom: H-105


  1. Introduction to Algorithm Analysis

    • Class notes (Includes the list of tentative topics)
    • References: Chapter 2 of [1]
  2. Basic Graph Algorithms: BFS and DFS

  3. Basic Graph Algorithms: DFS (contd), and Testing bipartiteness

  4. Basic Graph Algorithms: Testing bipartiteness, Search algorithms on Directed graphs

  5. Basic Graph Algorithms: Directed Acyclic Graphs, and Topological sort

  6. Greedy Algorithms: Shortest paths

  7. Greedy Algorithms: Minimum spanning trees

  8. Greedy Algorithms: Huffman coding

  9. Greedy Algorithms: Huffman coding (contd.), and Interval scheduling

  10. Divide and Conquer: Merge sort, Karatsuba’s integer multiplication, Strassen’s matrix multiplication

    • Class notes
    • References: Sections 5.1, 5.2 and 5.5 of [1]
  11. Divide and Conquer: Discrete Fourier Transform

  12. Divide and Conquer: Closest pair of points

  13. Review

  14. Dynamic Programming: Fibonacci, Longest Increasing Subsequence

  15. Dynamic Programming: Interval scheduling

  16. Dynamic Programming: Subset problem, 0-1 Knapsack, Matrix Chain Multiplication

    • Class notes
    • References: Section 6.4 of [1], and section 2.8 of [5]
  17. Dynamic Programming: All pairs shortest paths

  18. Network Flows I

  19. Network Flows II

  20. Network Flows III

  21. Network Flows IV

  22. Computational Efficiency, and Intractability I

  23. Computational Efficiency, and Intractability II

  24. Computational Efficiency, and Intractability III

  25. Computational Efficiency, and Intractability IV


  1. J. Kleinberg, and E. Tardos (2005), Algorithm Design, Pearson (Addison Wesley).
  2. T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms (third edition, 2009), MIT press and McGraw Hill.
  3. S. Dasgupta, C. Papadimitrou, and U. Vazirani, Algorithms (first edition, 2006), McGraw Hill Education.
  4. J. Erickson, Algorithms (first edition, 2019).
  5. A. Aho, J. Hopcraft, and J. Ullman, Design and Analysis of Algorithms (1974), Addison Wesley.