CS127 (Data Structures)
Winter 2007, Carleton College
Basic information:
- Instructor: David
Liben-Nowell
- Lecture: 4a (MW 12:30p--1:40p, F 1:10p--2:10p),
CMC
210 CMC 328.
- Office Hours: T10--11a, W2--3p, F 12--1p.
Always feel free to email for an appointment if the scheduled times
aren't good for you.
- Prefector: Laura Helde (heldel).
- Prefecting Sessions: Sunday
3--4pm 4--5pm and Wednesday 10--11pm, CMC
210.
- Grader: Janara Christensen (christej).
- Official catalogue description:
Data structures form the foundation of computer science: they make
algorithms more efficient and facilitate problem solving on both small
scales and large scales. In this course, we will explore these basic
building blocks of computer science and develop computer programs
based on these data structures. We will study stacks, queues, trees,
linked lists, graphs and hash tables, as well as algorithms for
recursion, searching, and sorting. Mathematical methods for analyzing
the performance of algorithms will also be addressed. We will apply
these concepts in a term-long software design project.
Course Resources:
Course Materials:
Week 0:
The Carleton Sentinel is the mailing list of
the CS community here at Carleton. We'll use it to send occasional
updates on things that might be of interest (talks, summer jobs,
social events, etc.). Sign up
here!
There is a
form for
office-hours scheduling available. Please fill it out by Friday,
22 December 2006, and I'll schedule office hours soon thereafter. (Be
sure to include your email address!)
Week 1:
intro to 127 and data structures; dictionaries (Chapter 1).
We've moved! We'll be in CMC 328 (instead of
CMC 210) for all class meetings.
PS1 (convert the sorted-array dictionary's
lookup to binary search) is due on Sunday, 7 January 2007, at 11:59p
via hsp.
- 3 January 2007 (W): intro to 127, Google's problems, and
dictionaries. Reading: Appendix A.
- 5 January 2007 (F): abstract data types, data structures, black
boxes, dictionaries via arrays. Reading: §1.2–1.3.
Week 2:
inheritance, excepctions, and efficiency (Chapters 3 and 2).
Laura's prefecting sessions will be held on
Sundays 3--4pm and Wednesdays 10--11pm in CMC 210.
PS2 (array doubling and abstract-class
organization) is due on Thursday, 11 January 2007, and Sunday, 14
January 2007.
If you're looking for any files from the
course (including in-class code or code/questions for problem sets),
they're in /Accounts/courses/cs127/dlibenno on the mathcs
machines.
- 8 January 2007 (M): inheritance, interfaces, abstract classes.
Reading: §3.1–3.3, §2.3–2.4.
- 10 January 2007 (W): exceptions; efficiency begun. Reading:
§2.8.
- 12 January 2007 (F): efficiency of algorithms, generics. Reading:
§4.4.
Week 3:
linked lists (Chapter 4)
Peer evaluations for
PS2 are due by email at 11:59p on Tuesday, 16 January 2007.
PS3 (JPods) is due on Sunday, Monday, and
Tuesday, 21, 22, and 23 January 2007.
- 15 January 2007 (M): linked lists.
- 17 January 2007 (W): more linked lists (speeding up
implementations by storing more data). Reading:
§4.5–4.7.
- 19 January 2007 (F): linked-list miscellenea (nested classes,
generics, iterators, List); Clue. Reading:
§4.1; optionally §4.2–4.3.
Week 4:
stacks, queues, and a hint of recursion (Chapters 5, 6, and 7)
The first midterm is now officially
(re)scheduled for next Monday, 29 January 2007.
Sunday prefecting has been moved to 4--5pm.
(The Wednesday 10--11pm session remains intact.) Both are in CMC
210.
Peer evaluations for
PS3 are due by email at 11:59p on Thursday, 25 January 2007.
- 22 January 2007 (M): a recursive view of linked lists. Reading:
Chapter 5.
- 24 January 2007 (W): stack ADT and implementations. Reading:
§6.1, 6.3.
- 26 January 2007 (F): queues.
Week 5:
recursion (Chapter 7)
PS4 (stacks and the minibrowser) is due on
Wednesday, 31 January 2007 Thursday, 1 February 2007
at 11:59p.
- 29 January 2007 (M): midterm exam!
- 31 January 2007 (W): queues wrapped up; recursion. Reading:
§7.1–7.5.
- 2 February 2007 (F): recursion, tail recursion, backtracking (8 queens
applet). Reading: §7.6, wikipedia on tail recursion.
Week 6:
trees, binary search trees (Chapter 8)
- 5 February 2007 (M): midterm break!
- 7 February 2007 (W): backtracking, sets/maps, trees. Reading:
§9.1–9.2, 8.1, 8.3.
- 9 February 2007 (F): binary search trees. Reading: §8.1,
8.3, 8.4, 8.2
Week 7:
augmenting data structures, balanced binary search trees (Chapter 11).
PS5 (search with context) is due on
Monday, Wednesday, and Thursday, 12, 14, and 15 February
2007. (See next week.)
- 12 February 2007 (M): binary search trees (animation). Reading: §8.1–8.4.
- 14 February 2007 (W): BSTs, augmenting data structures. Reading: §11.1–11.2.
- 16 February 2007 (F): rotations, AVL trees. Reading:
§11.1–11.2.
Week 8:
priority queues, hashing (Chapters 8 and 9).
Problem Set 5 is due on Tuesday, 20 February
2007, at 11:59p. Sorry again for the mixup with the due dates.
Problem Set 6 (Boggle) is due on Thursday, 22
February 2007 (Parts I and II) and Monday, 26 February 2007 (Part
III).
- 19 February 2007 (M): AVL trees, concluded; spring CS courses. Reading: §11.1–11.2.
- 21 February 2007 (W): priority queues, heaps. Reading: §8.5.
- 23 February 2007 (F): heapsort; hashing (hashing applet). Reading: §9.3–9.4.
Week 9:
sorting (Chapter 10)
Problem Set 7 (semantic networks) is due on
Sunday, Tuesday, and Thursday, the 4th, 6th, and 8th of
March.
The second midterm is now officially scheduled
for Friday, 2 March 2007.
- 26 February 2007 (M): hashing via open addressing. Reading: §9.3–9.4.
- 28 February 2007 (W): hashing concluded; sorting (demos, more demos). Reading: §9.3–9.4, §10.1–10.5, and §10.7–10.10.
- 2 March 2007 (F): midterm
exam!
Week 10:
sorting, graphs (Chapter 12)
Finals Period:
Our scheduled finals slot is Tuesday, 13
March 2007, from 8:30 to 11:00a.