Algorithmic Thinking |
1 |
8/28 |
One-pass Algorithms. |
Slides. Missing Elements: [Mut05, Sec 1.1];
Majority: [wiki], [KP, Sec 7.4].
|
2 |
9/3 |
Asymptotic notation. |
Slides. [CLRS, Sec 3.1], [DPV, Sec 0.2--0.3], [KT, Sec. 2.1--2.2], [KP, Sec 2.2--2.3]. |
Divide and Conquer |
3 |
9/4 |
Binary Search, SelectionSort and MergeSort, Lower Bound. |
[CLRS, Sec 2.2--2.3, 8.1], [DPV, Sec 2.3], [KT, Sec 5.1], [KP, Sec 7.1, 3.5]. |
4 |
9/9 |
Counting Sort, QuickSort. |
[CLRS, Sec 8.2, 7], [DPV, Ex 2.20, Ex 2.24 ], [KP, Sec 3.6, 7.5], [KT, Sec 13.5]. |
5 |
9/11 |
Maximum Subarray Problem, Investment Problem. |
[CLRS 3rd Ed, Sec 4.1], [Wys24, Sec 1--3], [KT, Chapter 5 Solved Ex 2], [KP, Sec 7.17]. |
6 |
9/16 |
Karatsuba Algorithm, Master Theorem. |
[Eri, Sec 1.9] and [CLRS, Sec 4.5]; or [KP, Sec 7.1]. |
7 |
9/18 |
Local Maximum, Red-Blue Pair, Fixed Point, Duplicates, Anagrams. |
|
Homework 1 |
Greedy Algorithms |
8 |
9/23 |
Largest Number, Car Charging, Money Change, Fractional Knapsack. |
[CLRS, Sec 15.1--15.2], [KP, Sec 6.1--6.4]. |
9 |
9/25 |
Maximum Inner Product, Activity Selection, Hitting Intervals. |
[CLRS, Sec 15.1--15.2], [Eri 4.2--4.3], [KT Sec 4.1], [KP Sec 6.5--6.6, 3.2]. |
10 |
9/30 |
Huffman Codes. |
[CLRS, Sec 15.3], [DPV Sec 5.2], [Eri Sec 4.4], [KT Sec 4.8], [KP Sec 6.14]. |
11 |
10/2 |
Stable Matchings. |
[Eri, Sec 4.5], [KT Sec 1.1]. |
12 |
10/7 |
Distinct Summands, Bulb Switching, Minimum Unchangeable Amount. |
|
Homework 2 |
Dynamic Programming |
13 |
10/9 |
Money Change, Rod Cutting, Nim. |
[CLRS, Sec 14.1], [DPV Sec 6.1], [Eri Sec 3.1], [KP Sec 8.1--8.2, 3.3], [KT Sec 6.2]. |
14 |
10/16 |
Midterm Review. |
|
15 |
10/21 |
Midterm Exam. |
|
16 |
10/23 |
Longest Common Subsequence. |
[CLRS, Sec 14.3]. |
17 |
10/28 |
Edit Distance. |
[Eri, Sec 3.7], [DPV, Sec 6.3]. |
18 |
10/30 |
Subset Sum, Knapsack. |
[Eri, Sec 3.8], [DPV, Sec 6.4], [KT, Sec 6.4], [KP, Sec 8.7]. |
Homework 3 |
19 |
11/4 |
MinCost Stairs Climbing, Longest Palindromic Subsequence, Longest Repeating Subsequence, Splitting Loot, Coins Game. |
|
Graph Algorithms |
20 |
11/6 |
Graph Representations, Depth-first Search. |
[CLRS, Sec 20.1, 20.3], [Eri, Chap 5]. |
21 |
11/11 |
Depth-first Search. |
[CLRS, 20.3], [DPV, Sec 3.3], [Eri, Sec 6.1--6.2]. |
22 |
11/13 |
Topological Sort. |
[CLRS, Sec 20.4], [DPV, Sec 3.3], [Eri, Sec 6.3], [KT Sec 3.6]. |
23 |
11/18 |
Breadth-first Search and Dijkstra. |
[CLRS, Sec 20.2, 22.3], [DPV, Sec 4.2--4.2], [Eri, Sec 8.4, 8.6], [KT, Sec 3.2, 4.4]. |
24 |
11/20 |
Bellman-Ford and Floyd-Warshall. |
[CLRS, Sec 22.1, 23.2], [DPV, Sec 4.6, 6.6], [Eri, Sec 8.7, 9.8]. |
25 |
11/25 |
Floyd-Warshall, Number of Islands, Rotting Tomatoes. |
|
Homework 4 |
Advanced Topics |
26 |
12/2 |
Streaming Algorithms. |
Missing Elements: [Mut05, Sec 1.1];
Majority: [wiki];
Distinct Elements: [And17, Sec 3] or [Nel20, Sec 2.2]. |
27 |
12/4 |
Approximation Algorithms. |
k-center [WS10, Sec 2.2]; TSP [WS10, Sec 2.4]. |
28 |
12/9 |
Final Review |
|
|
12/14 |
Final Exam |
|