|
|
|
|
Notes |
|
| Week 1 |
January
31 |
Motivation Insertion Sort |
Read chapters 1 and 2 |
|
| February 2 |
Divide and Conquer Merge Sort |
|||
| February 4 |
Continuing previous lecture |
Sorting | ||
| Week 2 |
February 7 | Efficiency of Divide and Conquer Algorithms |
Read chapter 3 |
|
| February 9 | Heapsort |
Read chapter 6 |
||
| February 11 | Continuing Hepasort Priority Queues |
Disk Scheduling |
||
| Week 3 |
February 14 | Quicksort |
Read chapter 7 |
|
| February 16 | Containers & Iterators Continuing quicksort |
Sort Benchmark |
||
| February 18 | Linear Sorting |
|||
| Week
4 |
February 21 | Continued lecture from Friday Review |
Read chapter 8 |
|
| February 23 | MIDTERM 1 | Includes chapters 1, 2, 3, 6, 7, 8 |
||
| February 25 | Order Statistics |
Read chapter 9 |
||
| Week 5 |
February 28 | Linear order statistics (cont.) |
Sorting Large Files |
|
| March 2 |
Red-Black Trees |
Read chapter 13 Math Colloquium at 3:30pm in Price 203 On a Base Exchange Game on Graphs |
||
| March 4 | Continuing Red-Black Trees |
Insert the following into a red-black tree: 2-15-12-4-8-10- 25-35-55-11-9-5-7 |
||
| Week
6 |
March 7 | Augmenting Red-Black Trees - Dynamic order statistics |
Read chapter 14 |
|
| March 9 | Continued augmenting red-black trees - Interval Trees |
|||
| March 11 | Class Cancelled - Sick |
|||
| Week 7 |
March 14 | Dynamic Programming - Rod Cutting |
Read chapter 15 | |
| March 16 | Review |
|||
| March 18 | MIDTERM 2 | |||
| Week
8 |
March 21 | SPRING BREAK |
||
| March 23 | SPRING BREAK |
|||
| March 25 | SPRING BREAK |
|||
| Week 9 |
March 28 | Dynamic Programming - Matrix-Chain Multiplication |
DUE on 4/4 Use the matrix multiplication algorithm to find the optimal way to multiply A1,A2,A3,A4,A5 where the dimensions are: A1: 3x5 A2: 5x4 A3: 4x2 A4: 2x6 A5: 6x3 Compute the minimal number of multiplications, show the optimal paren- thization, and show the tables you constructed to solve the problem. |
Read chapter 15 |
| March 30 | Matrix-Chain Multiplication Worksheet |
|||
| April 1 |
Elementary Graph Algorithms - Breadth-first search - Depth-first search |
Read chapter 22 |
||
| Week 10 | April 4 | Elementary Graph Algorithms - Topological sort - Strongly connected components |
||
| April 6 | Minimum Spanning Trees |
Read chapter 23 |
||
| April 8 | Single-Source Shortest Path |
Read chapter 24 |
||
| Week 11 | April 11 | Quiz - Assignment |
||
| April 13 | Meet in lab, work on assignment |
|||
| April 15 | Programming Challenge |
|||
| Week 12 | April 18 | Programming Challenge |
||
| April 20 | Class Cancelled - Chomsky Lecture |
|||
| April 22 | MIDTERM 3 | |||
| Week 13 | April 25 | Strassen's Algorithm |
Read chapter 4 |
|
| April 27 | SENIOR PROJECTS DAY |
|||
| April 29 | Longest Common Subsequence |
Pathfinding Assignment is DUE |
Read chapter 15 |
|
| Week 14 | May 2 |
Optimal Binary Search Trees |
Read chapter 15 |
|
| May 4 | Group Work on Dynamic Programming Problems |
Homework DUE (Tuesday, May 10 @ 5pm):
|
||
| May 6 | Greedy Algorithms |
Read chapter 16 |
||
| Week 15 | May 9 |
|||
| May 11 | READING DAY |
|||
| May 14 (SAT) | FINAL EXAM 8:30-11AM |
