ICS 261, Winter 2008:
Data Structures

This course meets Monday, Wednesday, and Friday, 3:00 - 3:50 in ICS 180. The text is "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, however the lectures will also cover additional material not in that text. Coursework will consist of weekly homeworks (25%), a midterm (30%), and a comprehensive final exam (45%).

Homeworks will be assigned on Fridays, due in class the following Wednesday. Due to lack of teaching assistance for graduate classes, we will be employing the following homework grading policy: you must be present in class Wednesday for your homework to be scored. At the start of the lecture, I will go over the answers to the homeworks together with a scoring rubric, and each student will grade his or her own homework according to the rubric. I will then collect and record the graded homeworks.

Tentative schedule of topics and readings:

• Week 1: Introduction; range search type problems. Amortized analysis and vector data structures [CLRS 6,17].
• Weeks 1-2: Priority queues [CLRS 19,20].
• Homework 1, due Wednesday, January 16: Exercises 17.3-5 and 17.4-3, and problem 6-2.
• Weeks 2-3: Hashing [CLRS 10,11,17]. Chaining, open addressing. Robin hood hashing. Bloom filters.
• Monday, January 21: No class (Martin Luther King, Jr., Holiday)
• Wednesday, January 23: No class
• Homework 2, due Friday, February 1: Problems 11-1 and 11-2.
• Weeks 4-5: Binary search trees [CLRS 12,13,18]. Skip lists. Cache-efficient data structures. Splay trees and the dynamic optimality conjecture.
• Week 5: Augmenting data structures [CLRS 14].
• Homework 3, due Wednesday, February 13: Problem 13-4(a-d), exercises 14.1-5 and 14.1-8.
• Week 6: fractional cascading, quadtrees, and kd trees.
• Homework 4, due Friday, February 22.
• Monday, February 18: No class (Presidents' Day Holiday)
• Week 7: Orthogonal range searching: Segment trees, interval trees [CLRS 14.3]
• Homework 5, due Wednesday, February 27.
• Week 8: Non-orthogonal range searching: point location, onion layers and paths with low stabbing number. Navigation in trees; least common ancestors
• Homework 6, due Wednesday, March 5.
• Week 9: Persistence
• Homework 7, due Wednesday, March 12.
• Weeks 9-10: Integer and string data structures; suffix trees, van Emde Boas trees
• Week 10: Disjoint sets [CLRS 21].

Other course-related information:

• Syllabus, Midterm and final exam from Winter 2006.
• Solutions to Fall 2003 final, Spring 2004 Phase II exam, and Fall 2004 last homework
• Lecture outlines from Fall 2003
• Final exam from Fall 2003 (answers to be provided later)
• Too-difficult phase II exam from Spring 2004 (answers to be provided later)
• Gerth Brodal's course on external-memory data structures including notes on (a,b)-trees.
• Advanced data structures at MIT. Lecture notes including flat trees, fusion trees, splay trees, suffix trees, and LCAs.
• Python implementations of various data structures including LCA and Union-Find.
• Study problems from 1999 on LCAs and cutting and linking trees -- Solutions
• Study problems on segment and interval trees
• Syllabus from Winter 1999

David Eppstein, ICS, UC Irvine.