Design and Analysis of Algorithms (Spring 2017)

Date Categories Topics References
Feb. 27

Basics

Introduction [CLRS]1, 2
Mar. 6 Asymptotic Notations and Recurrences [CLRS]3, 4.3, 4.4, 4.5; [DPV]2.2
Mar. 8

Divide and Conquer Algorithms

Maximum Contiguous Subarray Problem and Integer Multiplication Problem [CLRS]4.1; [DPV]2.2; [KT]5.5
Mar. 13 Polynomial Multiplication Problem and Counting Inversions Problem [CLRS]4.2; [KT]5.3
Mar. 20

Sorting and Searching

Quicksort and Heapsort [CLRS]6, 7
Mar. 22 Sorting in Linear Time [CLRS]8.1, 8.2, 8.3
Mar. 27 Selection Problem [CLRS]9
Apr. 5 AVL Trees [CLRS]13
Apr. 10

Graph Algorithms

Introduction to Graphs and Breadth-First Search [CLRS]22.1, 22.2
Apr. 17 Depth-First Search, Topological Sort and Strongly Connected Components [CLRS]22.3, 22.4, 22.5
Apr. 19 Minimum Spanning Trees and Prim's Algorithm [CLRS]23.1, 23.2
Apr. 24 Kruskal’s Algorithm and Disjoint Set Data Structure [CLRS]23.2; [DPV]5.1
May 3 Single Source Shortest Paths [CLRS]24.1, 24.2, 24.3
May 8 Maximum Flow and Maximum Bipartite Matching [CLRS]26.1, 26.2, 26.3
May 15 Invited Talk Experiences from ACM-ICPC Champions
May 17

Greedy Algorithms

Huffman Coding [CLRS]16.3
May 22 The Activity Selection Problem and The Fractional Knapsack Problem [CLRS]16.1, 16.2
May 31

Dynamic Programming Algorithms

The 0-1 Knapsack Problem and The Rod-Cutting Problem [CLRS]15.1
Jun. 5 Longest Common Subsequences and All-Pairs Shortest Paths [CLRS]15.2, 15.3, 15.4
Jun. 12

Dealing with Hard Problems

Problem Classes: P, NP, and NP-Completeness [CLRS]34
Jun. 14 Approximation Algorithms and Review [CLRS]35.1, 35.2
Announcements

• [CLRS] refers to the textbook, ''Introduction to Algorithms, 3rd'', by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.
• [DPV] refers to the reference book, ''Algorithms'', by S. Dasgupta, C. Papadimitriou, and U. Vazirani.
• [KT] refers to the reference book, ''Algorithm Design'', by J. Kleinberg and É. Tardos.

Maintained by Dr. Yongxin Tong.
Last updated: Feb. 2017.