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 |
|
|
17 |
10/28 |
|
|
18 |
10/30 |
|
|
19 |
11/4 |
|
|
Graph Algorithms |
20 |
11/6 |
|
|
21 |
11/11 |
|
|
22 |
11/13 |
|
|
23 |
11/18 |
|
|
24 |
11/20 |
|
|
Advanced Topics |
25 |
11/25 |
|
|
26 |
12/2 |
|
|
27 |
12/4 |
|
|
28 |
12/9 |
|
|
|
12/13 |
Final Exam |
|