CS 261, Winter 2018: Data Structures
This course meets Mondays, Wednesdays, and Fridays, 3:00 - 3:50
in Social Ecology II, room 1304. Coursework will consist of weekly homeworks, turned in online
and returned at the reader's office hours, one midterm, and a
comprehensive final exam. No books or notes are permitted for the exams.
Group work on homeworks is permitted; each
student should turn in his or her own copy of the homeworks. Homeworks
will usually be assigned Fridays and due on the following
Friday. Grading will be based 20% on homework, 35% for the midterm, and
45% for the final.
Rather than setting specific office hours, I will be trying an open
door policy: I will be available in my office most afternoons, and if
my door is open you are welcome to interrupt me with course questions.
If this becomes too problematic I will set more specific office hours,
and if you need me to be available at a more predictable time please
email me for an appointment.
There is no
required textbook; however, much of the course material will be drawn
from the Wikipedia articles collected together in
the Wikipedia "book"
Fundamental Data Structures.
Additionally, suggested internet readings for the
topics covered here will be linked from the schedule of topics.
This course may be used as part of the comprehensive exam in the
computer science masters program. To pass the comprehensive exam,
students must score at least 66% of the possible points on the final
examination for the course. If you are enrolled in the course,
you will be automatically considered eligible for the comprehensive exam.
Students who wish to take the
comprehensive exam but are not enrolled in the
course should contact me by email before the end of week 8 of the
quarter to reserve a place in the exam.
Tentative schedule of topics
- Week 1 (January 8–12):
- Introduction: Abstract data types versus data structures. Worst case versus amortized complexity.
potential method of amortized analysis. Dynamic arrays. Stacks, queues, and deques.
- Homework 1, due Monday, January 22 (11:55pm)
- Week 2 (January 15–19):
- Holiday Monday, January 15: Martin Luther King Day
- The dictionary problem and hash tables. Hash chaining, linear probing, and cuckoo hashing.
- Homework 2, due Monday, January 29 (11:55pm)
- Week 3 (January 22–26):
- Hash functions: cryptographic hash functions, k-independent hashing, and tabulation hashing.
- Representing sets by bitmaps, dictionaries, and Bloom
- Cuckoo filters and invertible Bloom
- Homework 3, due Monday, February 5 (11:55pm)
- Week 4 (January 29 – February 2):
data structures and frequent item detection.
- Boyer–Moore majority voting,
and the count-min sketch.
- Homework 4, due Monday, February 12 (11:55pm)
- Week 5 (February 5 – 9):
heaps and k-ary
- Homework 5, due Tuesday, February 20 (11:55pm)
- Week 6 (February 12 – 16):
search trees and predecessor
trees and B-trees.
- Splay trees,
the dynamic optimality conjecture.
- Week 7 (February 19 – 23):
- Holiday Monday, February 19: Presidents' Day
- Midterm Wednesday, February 21
- Integer searching.
- Week 8 (February 23 – March 2):
searching, Dynamic prefix sums
- Homework 6, due Friday, March 9 (11:55pm)
- Week 9 (March 5 – 9):
- Homework 7, due Friday, March 16 (11:55pm)
- Week 10 (March 12 – 16):
- Tries and suffix trees.
- Finals Week
- Final exam, Monday March 19, 4:00–6:00.
See also syllabi from Spring 2013 and Fall 2011 including
sample homeworks and exams with their solutions,
Demaine's open courseware class on similar material.
ICS, UC Irvine.