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

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

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