CS 261, Spring 2017: Data Structures
This course meets Mondays, Wednesdays, and Fridays, 10:00 - 10:50
in Steinhaus Hall
134. Coursework will consist of weekly homeworks, turned in online
and returned at the reader's office hours, one midterm, and a
comprehensive final exam. 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. 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 (April 3-7):
- 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 11:59PM Friday, April 14 —
- Week 2 (April 10-14):
- The dictionary problem and hash tables. Hash chaining, linear probing, and cuckoo hashing.
- Homework 2, due 11:59PM Friday, April 21 —
- Week 3 (April 17-21):
- 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 11:59PM Friday, April 28 —
- Week 4 (April 24-28):
data structures and frequent item detection.
- Boyer–Moore majority voting,
and the count-min sketch.
- Homework 4, due 11:59PM Friday, May 5 —
- Week 5 (May 1-5):
heaps and k-ary
- Homework 5, due 11:59PM Friday, May 12 —
- Week 6 (May 8-12):
search trees and predecessor
trees and B-trees.
- Splay trees,
the dynamic optimality conjecture.
- Week 7 (May 15-19):
- Review session Monday, May 15
- Midterm Wednesday, May 17
- Tries and suffix trees.
- Week 8 (May 22-26):
searching, Dynamic prefix sums
- Homework 6, due 11:59PM Friday, June 2 —
- Week 9 (May 29-June 2):
- Memorial day holiday Monday, May 29
- Range minima, Cartesian trees, and lowest common ancestors.
- Homework 7, due 11:59PM Friday, June 9 —
- Week 10 (June 5-9):
- Integer searching.
- Finals Week
- Final exam, Monday June 12, 10:30–12:30.
See also: Spring 2013 syllabus and Fall 2011 syllabus including
sample homeworks and exams with their solutions.
ICS, UC Irvine.