| Date |
Topics |
Readings |
Due Dates |
| 8-28 |
Introduction,Course Overview,
and C++ Basics |
|
|
| 9-2 |
Crash course in C++ (including
I/O, memory issues, class basics, header files, make) |
|
|
| 9-4 |
DPS (No Professor, No class) |
|
|
| 9-9 |
Arrays/vectors, Stacks, Queues,
Linked Lists (C++ inheritance and virtual methods, references vs. pointers) |
CLR pp. 197-220 |
|
| 9-11 |
Fun with Lists (Template classes) |
|
|
| 9-16 |
Static Linking and Direct Access
Files |
|
Assn 1 |
| 9-18 |
Hashing (Operator overloading) |
CLR pp. 221-252 |
Quiz #1 (Answers) |
| 9-23 |
More hashing (Template functions) |
|
|
| 9-25 |
More hashing |
|
|
| 9-30 |
Binary Trees |
CLR pp. 253-272 |
Quiz #2 (Answers) |
| 10-2 |
Right Threaded and Static
Linking of Trees |
|
|
| 10-7 |
AVL Trees |
|
|
| 10-9 |
Red-Black Trees |
CLR pp. 273-301 |
Quiz #3 (Answers) |
| 10-14 |
More Red-Black Trees |
|
Assn 2 |
| 10-16 |
Test 1 (Review
Sheet) (Answers) |
|
|
| 10-21 |
Augmenting Data Structures |
CLR pp. 302-318 |
|
| 10-23 |
Multiway trees |
|
|
|
10-28
|
KD-trees |
|
Assn 3 |
| 10-30 |
B-trees |
CLR pp. 430-454 |
Quiz #4 (Answers) |
| 11-4 |
Conclude B-Trees and Trees |
|
|
| 11-6 |
Graphs - Elementary Algorithms |
CLR pp. 524-560 |
|
| 11-11 |
Minimum Spanning Trees |
CLR pp. 561-579 |
Assn 4 |
| 11-13 |
Single-Source Shortest Paths |
CLR pp. 580-619 |
|
| 11-18 |
All-Pair Shortest Paths |
CLR pp. 620-642 |
Quiz #5 (Answers) |
| 11-20 |
Maximum Flow |
CLR pp. 643-700 |
|
| 11-25 |
Dynamic Programming |
CLR pp. 320-369 |
Assn 5 |
| 11-27 |
Thanksgiving Holiday |
|
|
| 12-2 |
Dynamic Programming |
CLR pp. 370-404 |
Quiz #6 (Answers) |
| 12-4 |
Greedy Algorithms |
|
|
| 12-9 |
Course Conclusions |
|
Assn 6 |
