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:
David Eppstein,
ICS, UC Irvine.