ICS 261, Winter 2009:
Data Structures
This course meets Monday, Wednesday, and Friday,
10:00 - 10:50 in ICS 253.
Textbook: Advanced Data Structures, by Peter Brass, available online for
free from Brass's web
site
Coursework will consist of weekly homeworks (assigned and due each
Friday), a midterm, and a final exam. As in previous course offerings, courseworks
will be graded in-class at the start of the class on which they are
due. Grading will be based 20% on the homework score and 40% on each exam.
Tentative schedule of topics and readings:
- Week 1: No lecture January 5 and 7; course begins January 9.
Introduction. Amortized
analysis and vector data structures.
- Week 2: Priority queues.
- Homework 1, due January 23.
- Monday, January 19: No class (Martin Luther King, Jr., Holiday)
- Week 3-4: Hashing. Chaining, open addressing. Cuckoo hashing. Bloom filters.
- Homework 2, due February 2.
- Weeks 5-6: Binary search trees. Skip
lists. Cache-efficient data structures. Splay trees and
the dynamic optimality conjecture. Augmenting data structures.
- Homework 3, due February 11.
- Friday, February 13: Midterm
- Monday, February 16: No class (Presidents' Day Holiday)
- Week 7: fractional
cascading, Segment trees, interval trees.
- Homework 4, due February 27.
- Week 8: Geometric data structures: quadtrees, kd trees, point
location, onion layers and paths with low stabbing number.
- Homework 5, due March 6.
- Week 9: Navigation in trees; least common ancestors. Persistence
- Homework 6, due March 13.
- Week 10: Integer and string data structures; suffix
trees, van
Emde Boas trees; Disjoint sets.
Other course-related information:
David Eppstein,
ICS, UC Irvine.