This course meets Monday, Wednesday, and Friday, 10:00 - 10:50 in ICS 243. Coursework will consist of two midterms and a final exam. Grading will be based 30% on each midterm and 40% on the final exam.

There is no required textbook; however, you may find the following helpful for some of the material:

- Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein. I don't recommend that you buy the book for this course (it is expensive and only covers part of the material) but many of you are likely to have it from undergraduate CS courses and it includes useful material on several topics from this course. Other algorithms texts are also likely to be helpful; the one I use in my undergraduate algorithms courses is "Algorithm Design" by Goodrich and Tamassia.
- Lecture notes from similar courses here and elsewhere:
- When possible I will try to include more specific links to Wikipedia or other related online reading from the schedule of topics below.

Below is a tentative schedule of topics and readings. Dates for specific topics are subject to change, but the exam schedule is firm.

- Week 1 (Jan 4-6-8):
- Introduction: priority queues in selection sort; binary heaps.
- Dijkstra's algorithm and D-ary heaps; amortized analysis and variable-sized arrays.
- Potential functions for amortization.

- Week 2 (Jan 11-13-15):
- Week 3 (Jan 18-20-22):
- HOLIDAY January 18 (Martin Luther King, Jr. Day).
- Hashing: hash chaining, open addressing (double hashing, linear probing). See also this blog post.
- Cuckoo hashing (see also: cuckoo hashing with a stash).

- Week 4 (Jan 25-27-29):
- Bloom filters.
- Hash functions; universal hashing (see also: blog post about Dietzfelbinger et al fast hash, Thorup on universal hashing for linear probing).
- MIDTERM I, Friday, January 29.

- Week 5 (Feb 2-4-6):
- Range sums, prefix sums, and decomposable searching problems.
- Logarithmic lower bounds for dynamic prefix sums.
- Binary search trees; augmented binary search trees and range searching.

- Week 6 (Feb 9-11-13):
- Overview of balanced binary search trees.
- Splay trees.
- The dynamic optimality conjecture. (Additional reading on non-splay-tree approaches to dynamic optimality.)

- Week 7 (Feb 15-17-19):
- HOLIDAY February 15 (Presidents' Day).
- Succinct representation of trees and fast navigation in succinct trees. Level ancestors.
- Lowest common ancestors, range minima, and the Bender-Farach algorithm.

- Week 8 (Feb 22-24-26):
- Persistence. Closures and fully-persistent stacks.
- Persistent search trees, point location, Voronoi diagrams, and the post office problem.
- The node-copying and fat node techniques for making data structures persistent.
- MIDTERM II, Friday, February 26.

- Week 9 (Mar 1-3-5):
- Week 10 (Mar 8-10-12):
- FINAL EXAM, Monday, March 15, 10:30 - 12:30.

For additional course-related information including old exams (which are very likely to be useful as samples for this course) see the syllabus from my previous offering in Winter 2009.