CS127 (Data Structures)
Winter 2006, Carleton College
- Instructor: David
Liben-Nowell ("David"; not "Dave"), dlibenno
- Lecture: 1a (MW 8:30a–9:40a, F 8:30–9:30a), CMC 206.
- Office Hours: Tuesday 10–11a; Wednesday 1–2:30p;
Always feel free to email for an appointment if the scheduled times
aren't good for you.
- Prefector: George Kachergis (kachergg). Prefecting sessions: 7pm
on Sundays and 6pm on Tuesdays, CMC 319. Feel free to drop by!
- Grader: Daniel Lew (lewda).
- 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. Prerequisite:
Computer Science 117 or consent of the instructor.
- The final exam is Monday, 13 March 2006, 7:00–9:30p, in our
- Review session for the final: 11:00a–12:00p on Sunday, 12
March 2006, in our regular classroom. Bring questions; we'll quit
early if you don't ask anything.
- The optional PS8 was distributed in
class on Monday, 27 Feburary 2006. It needs to be submitted by 5:00p
on Friday, 10 March 2006, if you want credit for it.
- There is an anonymous feedback form
available for any comments that you have about the course. If you
have any suggestions or comments on the class (style, content,
workload, etc.), please feel free to use this form to let me
- Old announcements.
Estimated Approximate Rough Tentative Schedule (subject to change):
- Week #1: introduction to data structures, Java review, inheritance
and interfaces. Chapters 1 and 3 and Appendix A, as necessary.
- Week #2: efficiency of algorithms, linked lists. Chapters 2 and 4.
- Week #3: more linked lists, stacks. Chapters 4 and 5.
- Week #4: queues, recursion. Chapters 6 and 7.
- Week #5: midterm exam, recursion, sets and maps, trees.
Chapters 2 and 9.
- Week #6: midterm break, trees, binary search trees.
- Week #7: balanced binary search trees. Chapter 11.
- Week #8: heaps and priority queues, hashing. Chapters 8 and 9.
- Week #9: sorting and graphs. Chapters 10 and 12.
- Week #10: graphs and presentations. Chapter 12.
Classes, Assignments, and Labs:
- 04 January 2006 (W): CS127, dictionaries. For Friday: PS0
(survey), read §1.2–1.3, §3.1–3.4, and some information on pair programming,
and Appendix A if needed.
- 06 January 2006 (F): array-based dictionaries, ADTs, efficiency
begun. For Monday: read §2.8 and §3.4. If you feel like
it, read §2.7 on loop invariants.
- 09 January 2006 (M): inheritance, abstract classes, interfaces, and
how to compare algorithms. For Wednesday: reread §2.8.
- 11 January 2006 (W): algorithmic efficiency, and a sketch of
generics. For Friday: read §4.4.
- 13 January 2006 (F): more efficiency, digressions on sorting, and
linked lists begun. For Monday: read §4.5–4.6. Don't
- 16 January 2006 (M): PS1 debriefing, linked-list implementation.
For Wednesday: read the rest of Chapter 4. Complete peer evaluation for PS1 by tonight (Monday) at
- 18 January 2006 (W): linked lists, sentinels, iterators (LinkedList127.java, LinkedListTester.java). PS2 assigned. For Friday: read §5.1–5.4
(skim 5.4); complete PS2 design.
- 20 January 2006 (F): recursive view of linked lists, stacks. PS2
design document due tonight; PS2 due Monday. For Monday: read
- 30 January 2006 (M): 8 queens analyzed, review. For Wednesday:
study! Don't forget PS3.
- 1 February 2006 (W): Midterm exam. Reading for Friday:
- 3 February 2006 (F): trees, binary search trees. For Wednesday: review
- 6 February 2006 (M): midterm break!
- 8 February 2006 (W): binary search trees, tree traversal. For
Friday: review §8.1–8.4, read §11.1, §11.3.
Don't forget PS4!
- 10 February 2006 (F): more BSTs, a digression on computability,
augmented BSTs. For Monday: review §11.1, §11.3.
- 13 February 2006 (M): (Amy.) AVL trees (applet
for AVL trees). For Wednesday: read §11.2 (on AVL trees), and
§11.1, §11.3 (for real this time).
- 15 February 2006 (W): red/black trees (applet for red/black trees). Reading for Friday: §8.5.
- 17 February 2006 (F): red/black trees, concluded. Finish PS5 for
- 20 February 2006 (M): priority queues. For Wednesday: read
§9.3 and §9.4; fill out PS5 peer evals; work on PS6.i.
- 22 February 2006 (W): hashing—chaining (hashing applet). For Friday: reread
§9.3–9.4; work on PS6.
- 24 February 2006 (F): hashing—open addressing (hashing applet).
For Monday and Wednesday: read Chapter 10 (skip §10.6,
- 13 March 2006 (M), 7:00–9:30p: final exam!