ICS 261, Winter 2006:
Data Structures

This course meets Monday, Wednesday, and Friday, 3:00 - 3:50 in PSCB 230. 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 Wednesdays, due in class the following Monday. Due to lack of teaching assistance for graduate classes, we will be employing the following homework grading policy: you must be present in class Monday 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:

• Fri 6-Jan: Introduction; range search type problems.
• Mon 9-Jan to Fri 13-Jan: Priority queues [CLRS 6,19,20].
  HOMEWORK ASSIGNMENT 1. Due: Wed 18-Jan.
• Mon 16-Jan: ACADEMIC HOLIDAY.
• Wed 18-Jan to Fri 20-Jan: Hashing [CLRS 10,11,17].
  HOMEWORK ASSIGNMENT 2. Due: Fri 27-Jan.
• Mon 23-Jan to Wed 25-Jan: NO CLASS.
• Fri 27-Jan to Fri 3-Feb: Binary search trees [CLRS 12,13,18]
  HOMEWORK ASSIGNMENT 3. Due: Wed 8-Feb.
• Mon 6-Feb to Wed 8-Feb: Augmenting data structures [CLRS 14]
• Fri 10-Feb: MIDTERM.
• Mon 13-Feb to Fri 17-Feb: Segment trees, interval trees, and fractional cascading [CLRS 14.3].
  HOMEWORK ASSIGNMENT 4. Due: Fri 24-Feb.
• Mon 20-Feb: ACADEMIC HOLIDAY.
• Wed 22-Feb to Fri 24-Feb: Onion layers and paths with low stabbing number.
  HOMEWORK ASSIGNMENT 5. Due: Fri 3-Mar.
• Mon 27-Feb to Fri 3-Mar: Navigation in trees; level ancestors; least common ancestors
  HOMEWORK ASSIGNMENT 6. Due: Fri 10-Mar.
• Mon 6-Mar to Wed 8-Mar: Integer and string data structures
  HOMEWORK ASSIGNMENT 7. Due: Fri 17-Mar.
• Fri 10-Mar to Mon 13-Mar: Persistence
• Wed 15-Mar to Fri 17-Mar: Disjoint sets [CLRS 21].

Other course-related information:

• 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.