In the schedule below, the exam dates are definite; the readings are approximate. Any changes will be announced in class and on the class homepage. It is your responsibility to be aware of any changes made to this schedule.
NOTE: the way this schedule works is that you are expected to have read the stuff listed for each day before you show up in class on that day.
| Date | Topic and Reading |
|
|---|---|---|
| January | 16 |
Introduction to the course; course requirements and procedures.
|
| 18 |
Fundamentals; Problem types.
Levitin, sections 1.1-1.3
(Homework 0 due)
|
|
| 23 |
Analysis framework; O, Θ, Ω notations.
Levitin, sections 2.1-2.2
|
|
| 25 |
O, Θ, Ω, continued.
|
|
| 30 |
Mathematical analysis of nonrecursive algorithms.
Levitin, section 2.3
|
|
| February | 1 |
Recursive algorithms; implementation of recursive procedures.
|
| 6 |
Mathematical analysis of recursive algorithms.
Levitin, section 2.4
|
|
| 8 |
Mathematical analysis of recursive algorithms, continued;
Review for exam.
|
|
| 13 |
exam due at the beginning of class Brute-force algorithms; Exhaustive search. Levitin, sections 3.1, 3.2, 3.3 |
|
| 15 |
Divide-and-conquer algorithms; Mergesort.
Levitin, section 4.1
|
|
| 20 |
Quicksort.
Levitin, section 4.2
|
|
| 22 |
Convex hull problem.
Levitin, section 4.2
|
|
| 27 |
Decrease-and-conquer algorithms; Insertion sort; Binary search.
Levitin, sections 5.1 and 4.3 (yes, that's four-point-three)
|
|
| March | 1 |
Decrease-by-a-constant-factor algorithms; Variable-size-decrease algorithms.
Levitin, sections 5.5-5.6
|
| 6 |
Generating combinatorial objects; review for exam.
Levitin, section 5.4
|
|
| 8 |
(away at SIGCSE 2007)
exam due at 3:30 p.m. |
|
| 10-25 | Spring Break
|
|
| 27 |
Transform-and-conquer algorithms.
Levitin, section 6.1
|
|
| 29 |
T-and-c: representation change.
Levitin, section 6.4
|
|
| April | 3 |
T-and-c: problem reduction.
Levitin, section 6.6
|
| 5 |
Space and time tradeoffs; Horspool's algorithm.
Levitin, sections 7.1-7.2
|
|
| 10 |
The Boyer-Moore algorithm. Levitin, section 7.2, continued |
|
| 12 |
Hashing.
Levitin, section 7.3
|
|
| 17 |
Search Trees; DFS, BFS.
Levitin, section 5.2
|
|
| 19 |
B-Trees.
Levitin, section 7.4
|
|
| 24 |
Dynamic Programming; Greedy techniques.
Levitin, section 8.1
|
|
| 26 |
Lower-bound arguments.
Levitin, section 11.1
|
|
| May | 1 |
P, NP, and NP-complete problems.
Levitin, section 11.3
|
| 3 |
P, NP, and NP-complete problems, continued.
|
|
| 11 |
(Friday) Final exam due at 2:00 p.m. Research project presentations, 2:00—5:00 p.m. |
|
| 12 |
(Saturday) Written component of research project due at 5:00 p.m. |
|
[ Return to the CPSCI 330 homepage ]
Brian J. Rosmaita <contact me>