This schedule will be updated periodically throughout the term. Last update: April 27.
The text is Sedgewick, Algorithms in C, third editon, Addison-Wesley (1998). Chapters labeled CP refer to the Course Packet. The Course Packet material is from Sedgewick, Algorithms in C, Addison-Wesley (1990).
| Tuesdays | Thursdays | |||||
|---|---|---|---|---|---|---|
| Date | Topics | Text | Date | Topics | Text | |
| Jan 20 | Connectivity | 1 | Jan 22 | Asymptotic Notation (big-O) | 2.1-4 | |
| Jan 27 | Abstract Data Types (ADTs) ADT Stack, ADT Queue |
4.1-7 | Jan 29 | ADT Dictionary List and array implementations Sentinels |
||
| Feb 3 | ADT SymbolTable List and array implementations |
12.1-3 | Feb 5 | Binary Search Trees (BSTs) Tree traversals |
12.4-6 5.6 |
|
| Feb 10 | Random BSTs Splay Trees |
13.1 13.2 |
Feb 12 | 234 Trees | 13.3 | |
| Feb 17 | Red-Black Trees | 13.4 | Feb 19 | Skip Lists Performance Other balanced tree schemes |
13.5 13.6 |
|
| Feb 24 | Hashing | 14 | Feb 26 | Hashing | 14 | |
| Mar 3 | Hashing (table doubling) Review |
14 |
Mar 5 | *EXAM* given in class | ||
| Mar 10 | Radix Search (DSTs, Tries) | 15.1-2 | Mar 12 | Patricia Tries Ternary Search Tries |
15.3 15.4 |
|
| Mar 17 | ***SPRING*BREAK*** | Mar 19 | ***SPRING*BREAK*** | |||
| Mar 24 | Selection Sort Insertion Sort Merge Sort Recurrence Relations |
6.1-2 6.3 8 5.2 |
Mar 26 | Quick Sort | 7.1-7 | |
| Mar 31 | ADT Priority Queue Heaps, Heapsort |
9.1-4 | Apr 2 | Lower Bounds on Sorting Counting Sort |
6.10 |
|
| Apr 7 | Radix Sorting Practical Sorting (Summary) Selection |
10 7.8 |
Apr 9 | Intro to Graphs Depth First Search (DFS) |
CP29 | |
| Apr 14 | Breadth First Search (BFS) Biconnected Components |
CP29 CP30 |
Apr 16 | Weighted Graphs Minimum Spanning Trees (MSTs) |
CP31 | |
| Apr 21 | Dijkstra's Alg (Shortest Paths) | CP31 | Apr 23 | Digraphs All Pairs Shortest Paths DFS on digraphs |
CP32 | |
| Apr 28 | DFS applications Topological Sort, dags Strongly Connected Components |
CP32 | Apr 30 | Course Evaluation What I do for Research Review |
||
| Monday May 11 |
*FINAL*EXAM* Olin 155, noon |
|||||