CS1.301 Algorithm Analysis and Design (Monsoon 2022)

---

Announcements

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

Lectures

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

   • Class notes
   • References: Section 3.2 of [1]

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

   • Class notes
   • References: Sections 3.3 and 3.4 of [1]

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

   • Class notes
   • References: Sections 3.4 and 3.5 of [1]

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

   • Class notes
   • References: Sections 3.5 and 3.6 of [1]

6. Greedy Algorithms: Shortest paths

   • Class notes
   • References: Section 4.4 of [1]

7. Greedy Algorithms: Minimum spanning trees

   • Class notes
   • References: Sections 4.5 and 4.6 of [1]

8. Greedy Algorithms: Huffman coding

   • Class notes
   • References: Section 4.8 of [1]

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

   • Class notes
   • References: Sections 4.8 and 4.1 of [1]

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

    • Class notes
    • References: Section 5.5 of [1]

12. Divide and Conquer: Closest pair of points

    • Class notes
    • References: Section 5.4 of [1]

13. Review

    • Class notes

14. Dynamic Programming: Fibonacci, Longest Increasing Subsequence

    • Class notes
    • References: Sections 3.2 and 3.6 of [4]

15. Dynamic Programming: Interval scheduling

    • Class notes
    • References: Sections 6.1 and 6.2 of [1]

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

    • Class notes
    • References: Section 6.8 of [1]

18. Network Flows I

    • Class notes
    • References: Section 7.1 of [1]

19. Network Flows II

    • Class notes
    • References: Sections 7.1 and 7.2 of [1]

20. Network Flows III

    • Class notes
    • References: Section 7.1 of [1]

21. Network Flows IV

    • Class notes
    • References: Section 7.1 of [1]

22. Computational Efficiency, and Intractability I

    • Class notes
    • References: Chapter 12 of [4]

23. Computational Efficiency, and Intractability II

    • Class notes
    • References: Chapter 12 of [4]

24. Computational Efficiency, and Intractability III

    • Class notes
    • References: Chapter 12 of [4]

25. Computational Efficiency, and Intractability IV

    • Class notes
    • References: Chapter 12 of [4]

References

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.