| Date | Topic | Reading or Title | What's due (announcements) |
|---|---|---|---|
| Week 1 | |||
| Jan 4 | Intro, Binomial Queues. | Chapter 9. | . |
| Jan 6 | Huffman's algorithm. | Chapter 9. |
ppt handout. |
| Week 2 | |||
| Jan 10 |
Finish Huffman's Algorithm. Review Depth-First-Search. | Chapter 8, 6. |
Graphs (
ppt,
pdf,
handout).
DFS ( ppt, pdf, handout). Digraphs, topological sort ( ppt, pdf, handout). |
| Jan 11 |
Red-Black Trees, Splay Trees. | Chapter 3. |
24 Trees
(ppt,
pdf,
handout).
Red-Black Trees (ppt, pdf, handout). |
| Jan 13 | See Jan 11. | Chapter 3. | . |
| Week 3 | |||
| Jan 17 | Red-black trees, splay trees. | . |
Red-black tree song,
mp3.
Splay Trees (ppt, pdf, handout). Skip Lists (ppt, pdf, handout). |
| Jan 18 | . | . | Homework #1 due. |
| Jan 20 | . | . | Frank Away, lecture by Mark Weston. |
| Week 4 | |||
| Jan 24 | Text Processing. | Chapter 9. |
Frank Away. Lecture by Mark Weston. Pattern Matching (ppt, pdf, handout). Tries (ppt, pdf, handout). |
| Jan 25 | Text Processing. | Chapter 9. |
Frank Away. Lecture by Stirling Chow. Suffix Trees |
| Jan 27 | Text Processing. | Chapter 9. |
Frank Away. Lecture by Stirling Chow. Lempel-Ziv Compression |
| Week 5 | |||
| Jan 31 | Backtracking. | . | Notes. |
| Feb 1 | . | . | . |
| Feb 3 | . | . | Imbolc (Wiccan) - No Exam / No Work. |
| Week 6 | |||
| Feb 7 | Network Flows. | . |
Max Flow (ppt, pdf, handout). |
| Feb 8 | . | . | Homework #2 due. |
| Feb 10 | . | . | . |
| Week 7 | |||
| Feb 14 | Min-cost Flows. | . | . |
| Feb 15 | Shortest Path Algorithms. | Chapter 7. | Shortest Path (ppt, pdf, handout). |
| Feb 17 | Midterm. | Midterm. | Midterm. |
| Week 8 | |||
| Feb 21 |
READING BREAK |
READING BREAK |
READING BREAK |
| Feb 22 |
READING BREAK |
READING BREAK |
READING BREAK |
| Feb 24 |
READING BREAK |
READING BREAK |
READING BREAK |
| Week 9 | |||
| Feb 28 | Midterm solutions, all-pairs shortest paths. | . | . |
| Mar 1 | Number theory algorithms. | Chapter 10. |
Homework #3 due. Numerical Algorithms (ppt, pdf, handout). Fast Fourier Transform (ppt, pdf, handout). RSA Encryption (ppt, pdf, handout). RSA Challenge Numbers |
| Mar 3 | . | Chapter 10. | . |
| Week 10 | |||
| Mar 7 | . | Chapter 10. |
Crypto (ppt, pdf, handout). Information Security (ppt, pdf, handout). |
| Mar 8 | RSA encryption. | . |
best factoring alg. Mersenne primes. |
| Mar 10 | . | . | Primes in P (link). |
| Week 11 | |||
| Mar 14 | . | . | . |
| Mar 15 | . | . | . |
| Mar 17 | . | . | . |
| Week 12 | |||
| Mar 21 | Computational Geometry. | . | Navroz (Ismaili, Muslim), New Year's Day (Baha'i) - No Exam / No Work. |
| Mar 22 | Computational Geometry. | . | Homework #4 due. |
| Mar 24 | Computational Geometry. | . |
Convex Hull (ppt,
pdf,
handout).
Incremental Hull (ppt, pdf, handout). |
| Week 13 | |||
| Mar 28 |
Computational Geometry. Voronoi Diagrams. | . |
A
nice Voronoi applet. Voroglide! divide & conquer |
| Mar 29 |
Computational Geometry. Voronoi Diagrams. | . | . |
| Mar 31 | Computational Geometry. | . | . |
| Week 14 | |||
| Apr 4 | Parallel Algorithms. | Chapter 14. | Frank away, lecture by Scott Craig |
| Apr 5 | Distributed Algorithms. | Chapter 11. |
Frank away, lecture by Aaron Williams. Homework #5 due. |
| Apr 7 | . | . | Course Evaluation. |
| Week 15-16 | |||
| Apr 10 | EXAMS BEGIN | GOOD LUCK | GOOD LUCK |
| Apr 29 | EXAMS END | HAVE GREAT SUMMER! | HAVE GREAT SUMMER! |