This schedule will be updated periodically throughout the term. Last update: May 12.
Readings and, in some cases, web-links are given for each of the topics listed below. Reading are taken from several sources. The abbreviations used for these sources are:
The first text listed is the official course text for CS409. The other two texts are both on reserve in the Engineering Library.
| Tuesdays | Thursdays | |||||
|---|---|---|---|---|---|---|
| Date | Topics | Reading | Date | Topics | Reading | |
| Jan 25 | General Course Information Asymptotic Notation (big-O) |
Sk 1 Sk 1.4, 1.5 |
Jan 27 | Real RAM Model Worst-Case vs. Expected Times Abstract Data Types (ADTs) ADT Stack |
Sk 1.3.1 Sk 1.3.2 Sk 2.1.1 |
|
| Feb 1 | ADT Queue ADT Dictionary Direct Address Table Hashing with Chaining Application: Spell-Checking |
Sk 2.1.1 Sk 2.1.2, 8.1.1 CLR 12.1 CLR 12.2 |
Feb 3 | Analysis of Hashing with Chaining | CLR 12.2 | |
| Feb 8 | Application: Geometric Hashing | Web, RS | Feb 10 | Binary Search Trees (BSTs) | Web, RS CLR 13.1-3 Se 12.5 |
|
| Feb 15 | 234-Trees | Web, RS CLR 19 Se 13.3 |
Feb 17 | Tree Rotations Red-Black Trees Other Balanced Tree Schemes |
CLR 14; Se 13.4 | |
| Feb 22 | Selecting a Dictionary Scheme ADT Priority Queue (PQ) Simple PQ Implementations Introduction to Heaps |
Sk 8.1.1 Sk 8.1.2 Sk 8.1.2 CLR 7.1; Se 9.2 |
Feb 24 | More on Heaps Bounded Height PQ Selecting a PQ Scheme Application: Segment Intersection |
CLR 7.2; Se 9.3 Sk 8.1.2 Sk 8.1.2 |
|
| Feb 29 | Segment Intersection using a Sweepline Data Structures for Sets - BitSet - Using a Dictionary as a Set |
Web,
RS Sk 8.1.5 |
Mar 2 | Set Partition (Union/Find) | Sk 8.1.5 CLR 22.1-3 Se 1.2-3 |
|
| Mar 7 |
Midterm Exam |
Mar 9 | Divide & Conquer Application: Multiplying Integers |
Sk 3.6 Web, RS |
||
| Mar 14 |
Application: Closest Pair of Points Application: Gravitational Simulation |
see previous | Mar 16 | Dynamic Programming Application: Matrix-Chain Multiplication Application: Protein Alignment |
Sk 3.1-5, 8.7.4 Web, RS |
|
| Mar 21 | BREAK | Mar 23 | BREAK | |||
| Mar 28 |
Greedy Method Application: Min Spanning Tree |
Sk 4.7, 8.4.3 CLR 17.1-3 |
Mar 30 | Greedy Method Application: DNA Sequencing |
Sk 8.7.9 | |
| Apr 4 |
Finish DNA Sequencing Greedy Method vs. Dynamic Programming |
CLR 17.2 | Apr 6 | Amortization: Accounting Method | CLR 18.1-2 Web, RS |
|
| Apr 11 | Amortization: Union/Find | see previous | Apr 13 | Reductions Lower Bounds for Sorting |
Web, RS |
|
| Apr 18 | Reductions (for lower bounds) | Web, RS | Apr 20 | Suffix Trees | Sk 8.1.3 | |
| Apr 25 |
Network Flow Max-Flow Reductions Bipartite Matching Application: Airline Scheduling |
Sk 8.4.9 Sk 8.4.6 CLR 27.1,3 |
Apr 27 | Max-Flow Reductions Application: Inverse Protein Folding |
see previous | |
| May 2 | NP-Completeness | Sk 6.1-7 CLR 36 |
May 4 | Finish NP-Completeness Quick Overview What I Do |
Sk 8.5.1-5 |
|
Tuesday, May 16: Final Exam, 3pm in Olin Hall 245 |
||||||