| Number |
Date |
Topic |
Source |
Text |
| 1 |
1/16 |
Introduction, administration, time and space complexity |
|
-- |
| 2 |
1/18 |
Basics: asymptotic notation |
PPT |
3.1-3.2 |
| 3 |
1/21 |
Basics: recurrences (mergesort) |
PPT |
4.1 |
| 4 |
1/23 |
Basics: recurrences
continued, master theorem |
PPT |
4.3, 6.1-6.2 |
| 5 |
1/25 |
Sorting: intro to heapsort |
PPT |
6, 7.1-7.3 |
| 6 |
1/28 |
Sorting: heapsort, priority
queues |
PPT |
7.4 |
| 7 |
1/30 |
Sorting: quicksort |
PPT |
5.1-5.3 |
| 8 |
2/1 |
Sorting: quicksort average
case analysis |
PPT |
5.4 last section |
| 9 |
2/4 |
Sorting: linear time sorting algorithms |
PPT |
8.1-8.2 |
| 10 |
2/6 |
Sorting: linear time algorithms continued;
Order statistics: selection in expected linear time |
PPT |
8.3-8.4
9.1-9.2 |
| 11 |
2/8 |
Order statistics: selection in worst-case linear time |
PPT |
9.3 |
| 12 |
2/11 |
Review for exam |
PPT |
|
| EXAM |
2/13 |
EXAM 1: Basics, Sorting, Order Statistics |
|
-- |
| 13 |
2/15 |
Structures: binary search trees |
PPT |
12.1-12.3 |
| 14 |
2/18 |
Structures: red-black trees |
PPT |
13.1-13.2 |
| 15 |
2/20 |
Structures: red-black trees
(insertion) |
PPT |
13.3-13.4 |
| 16 |
2/22 |
Structures: skip lists |
PPT |
-- |
| 17 |
2/25 |
Structures: skip lists, hash tables |
PPT |
11.1-11.2 |
| 18 |
2/27 |
Structures: hash tables
(hash functions) |
PPT |
11.3-11.4 |
| 19 |
3/1 |
Structures: hash tables (universal hashing) |
PPT |
11.3-11.4 |
| 20 |
3/4 |
Augmenting structures: dynamic order statistics |
PPT |
14.1-14.2 |
| 21 |
3/6 |
Augmenting structures:
interval trees |
PPT |
14.3 |
| 22 |
3/8 |
Graph algorithms: the basics |
PPT |
22.1-22.3 |
| -- |
-- |
SPRING BREAK |
|
-- |
| 23 |
3/18 |
Graph algorithms: BFS |
PPT |
22.3 |
| 24 |
3/20 |
Graph algorithms: DFS |
PPT |
23.1 |
| EXAM |
3/22 |
EXAM 2: Data structures |
|
-- |
| -- |
3/25 |
Go over exam |
|
-- |
| 25 |
3/27 |
Minimum spanning trees |
PPT |
23.2 |
| 26 |
3/29 |
Shortest paths: Bellman-Ford |
PPT |
24.1-24.3 |
| 27 |
4/1 |
Shortest paths: DAG,
Dijkstra's algorithm |
PPT |
|
| 28 |
4/3 |
Finish Dijkstra's. Kruskals
algorithm; disjoint sets |
PPT |
21.1-21.3, 23.2 |
| 29 |
4/5 |
Disjoint sets; amortized analysis |
PPT |
17.1-17.2 |
| 30 |
4/8 |
Amortized analysis continued |
PPT |
17.3-17.4 |
| 31 |
4/10 |
Dynamic programming |
PPT |
15.1, 15.3 |
| 32 |
4/12 |
Dynamic programming (longest common subsequence) |
PPT |
15.4 |
| 33 |
4/15 |
Dynamic programming (knapsack problem) |
PPT |
|
| 34 |
4/17 |
Greedy algorithms |
PPT |
16.1-16.2 |
| 35 |
4/19 |
NP-Completeness |
PPT |
34.1-34.2 |
| 36 |
4/22 |
NP-Completeness continued |
PPT |
34.1-34.2 |
| 37 |
4/24 |
NP-Completeness: reductions |
PPT |
34.3-4 |
| 38 |
4/26 |
NP-Completeness: reductions |
PPT |
34.3-4 |
No comments:
Post a Comment