This course meets Monday, Wednesday, and Friday, 2:00 - 2:50 in Bren 1200. Coursework will consist of weekly homeworks, one midterm and a comprehensive final exam. Grading will be based 20% on homework, 35% for the midterm, and 45% for the final.

The reader assigned to the course is Leila Jalali

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 3-5-7):
- Week 2 (Jan 10-12-14):
- Week 3 (Jan 17-19-21):
- HOLIDAY January 17 (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).
- Homework 3, due Wednesday, Jan 26 (solutions)

- Week 4 (Jan 24-26-28):
- Min-wise hashing, Bloom filters, and invertible Bloom filters.
- Hash functions: cryptographic hashing, finding collisions using cycle detection algorithms, universal hashing, tabulation hashing.
- Overview of balanced binary search trees.
- Homework 4, due Wednesday, Feb 2 (solutions)

- Week 5 (Jan 31, Feb 2-4):
- Splay trees.
- The dynamic optimality conjecture. (Additional reading on non-splay-tree approaches to dynamic optimality.)
- MIDTERM, Friday, February 4. (solutions)

- Week 6 (Feb 7-9-11):
- 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.
- Homework 5, due Wednesday, Feb 16 (solutions)

- Week 7 (Feb 14-16-18):
- Succinct representation of trees and fast navigation in succinct trees. Level ancestors.
- Lowest common ancestors, range minima, and the Bender-Farach algorithm.
- Homework 6, due Wednesday, Feb 23 (solutions)

- Week 8 (Feb 21-23-25):
- HOLIDAY February 21 (Presidents' Day).
- 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.
- Homework 7, due Wednesday, Mar 2 (solutions)

- Week 9 (Feb 28, Mar 2-4):
- Week 10 (Mar 7-9-11):
- FINAL EXAM, Friday, March 18, 1:30-3:30pm.

Several exams from past offerings of this course are online: Midterm, Winter 1999 (solutions); Final, Fall 2003; Final, Fall 2004; Midterm, Winter 2006 (solutions); Final, Winter 2006.

For additional course-related information see the syllabus from my previous offering in Winter 2010 and previous quarters linked from there.