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: H105
Lectures

Introduction to Algorithm Analysis
 Class notes (Includes the list of tentative topics)
 References: Chapter 2 of [1]

Basic Graph Algorithms: BFS and DFS
 Class notes
 References: Section 3.2 of [1]

Basic Graph Algorithms: DFS (contd), and Testing bipartiteness
 Class notes
 References: Sections 3.3 and 3.4 of [1]

Basic Graph Algorithms: Testing bipartiteness, Search algorithms on Directed graphs
 Class notes
 References: Sections 3.4 and 3.5 of [1]

Basic Graph Algorithms: Directed Acyclic Graphs, and Topological sort
 Class notes
 References: Sections 3.5 and 3.6 of [1]

Greedy Algorithms: Shortest paths
 Class notes
 References: Section 4.4 of [1]

Greedy Algorithms: Minimum spanning trees
 Class notes
 References: Sections 4.5 and 4.6 of [1]

Greedy Algorithms: Huffman coding
 Class notes
 References: Section 4.8 of [1]

Greedy Algorithms: Huffman coding (contd.), and Interval scheduling
 Class notes
 References: Sections 4.8 and 4.1 of [1]

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]

Divide and Conquer: Discrete Fourier Transform
 Class notes
 References: Section 5.5 of [1]

Divide and Conquer: Closest pair of points
 Class notes
 References: Section 5.4 of [1]

Review

Dynamic Programming: Fibonacci, Longest Increasing Subsequence
 Class notes
 References: Sections 3.2 and 3.6 of [4]

Dynamic Programming: Interval scheduling
 Class notes
 References: Sections 6.1 and 6.2 of [1]

Dynamic Programming: Subset problem, 01 Knapsack, Matrix Chain Multiplication
 Class notes
 References: Section 6.4 of [1], and section 2.8 of [5]

Dynamic Programming: All pairs shortest paths
 Class notes
 References: Section 6.8 of [1]

Network Flows I
 Class notes
 References: Section 7.1 of [1]

Network Flows II
 Class notes
 References: Sections 7.1 and 7.2 of [1]

Network Flows III
 Class notes
 References: Section 7.1 of [1]

Network Flows IV
 Class notes
 References: Section 7.1 of [1]

Computational Efficiency, and Intractability I
 Class notes
 References: Chapter 12 of [4]

Computational Efficiency, and Intractability II
 Class notes
 References: Chapter 12 of [4]

Computational Efficiency, and Intractability III
 Class notes
 References: Chapter 12 of [4]

Computational Efficiency, and Intractability IV
 Class notes
 References: Chapter 12 of [4]
References
 J. Kleinberg, and E. Tardos (2005), Algorithm Design, Pearson (Addison Wesley).
 T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms (third edition, 2009), MIT press and McGraw Hill.
 S. Dasgupta, C. Papadimitrou, and U. Vazirani, Algorithms (first edition, 2006), McGraw Hill Education.
 J. Erickson, Algorithms (first edition, 2019).
 A. Aho, J. Hopcraft, and J. Ullman, Design and Analysis of Algorithms (1974), Addison Wesley.