2010 November 17 / j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Data Structures

Carleton College CS 201, Fall 2010, Prof. Joshua R. Davis


Computer science is the study of algorithms. Algorithms are often closely connected to data structures, which are methods of organizing information. Philosophically, algorithms are about the use of time — first this happens, then that, then that — while data structures are about the use of space — this information is stored here, this information is stored here, and so forth. A good choice of data structure can make or break an algorithm. Some algorithms are really just data structures; for example, the heap sort algorithm is "put the items into a heap and then take them out".

So, whereas your first course in computer science probably focused on algorithms, this second course focuses on data structures. For each data structure we perform four core tasks:

These tasks don't come in any particular order. In the real world, a programmer might begin with a problem to solve, design a data structure to solve that problem, think about its efficiency, redesign, and finally write code to implement it; then she might redesign, reanalyze, reimplement, etc. By the end of the course you'll be doing all of this unconsciously. Along the way, we'll also study some algorithms, learn a bit more about how computers work, practice our problem-solving skills — all of that good computer science stuff.

The official prerequisite for this course is CS 111. More generally, this course is appropriate for students who are comfortable with elementary programming, have some experience with recursion and objects, and who have not taken more advanced courses. Most of our assignments take the form of Python programs. Talk to me if you are concerned about your background. In particular, if you're new to Python, then try my Getting Started with Python, Prof. Ondich's Transition to Python, and the general Python Documentation.


Our class meets in CMC 319 during period 5A (MW 1:50PM-3:00PM, F 2:20PM-3:20PM). Here's how you get in contact with me:

Dr. Joshua R. Davis (most people call me Josh)
E-mail: j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Office hours: Mon, Wed, Fri immediately after class, and Tue 10:00-11:00 AM. For other meetings, e-mail me for an appointment.
Office: CMC 326, x4369

This course has a prefect, who holds a couple of review sessions each week, in which you review material from class, get questions answered, tackle additional problems, etc. He is also available for individual tutoring.

Daniel Ehrenberg
E-mail: e|h|r|e|n|b|e|d|@|c|a|r|l|e|t|o|n|.|e|d|u
Sessions: Wed 8:00 PM, Sun 10:00 PM
Location: CMC 306, 319, 328, or around there
Additionally, our computer lab (CMC 306) is often staffed with CS majors who serve as lab assistants. They can help you with technical computer problems. When it's time to study for an exam, How to Study gives my advice. Here are our exams from this term: Here are the exams from my Spring 2009 version of this course: Here are the exams from my Fall 2008 version of this course:


You are expected to spend at least 10 hours per week on this course outside class. (This is a typical expectation of faculty at Carleton.) Some students may need to spend more than 10 hours. If you are spending more than, say, 15, then talk to me. If you are spending fewer than 10, then your education is suboptimal; we should discuss ways to enrich it, such as extra readings or side projects based on your personal interests.

The following elements contribute to your course grade.

At the end of the term, I compute a total numerical score for each student, using the scheme just described. Then the numerical scores are converted to letter grades according to an approximate curving process. By "curving" I do not mean that there are predetermined numbers of As, Bs, etc. to be awarded; rather, I mean that there are no predetermined percentages (90%, 80%, etc.) required for those grades. Class participation, effort, and progress made over the term are considered in making final adjustments to grades.

If some medical condition affects your participation in class or your taking of exams, let me know during the first week of class. You may need to make official arrangements with the Disability Services for Students.

Late Pass

During the term, you have one free pass to hand in an assignment late. Once you have used your late pass I become quite inflexible; no late assignments are accepted, except in extreme circumstances that are truly beyond your control (e.g. documented medical emergencies).

Here is how you activate your late pass. Instead of handing in the assignment, send me e-mail (by the due date) declaring that you are using your late pass. You do not need to speak to me in person; you must send me e-mail, because your e-mail is part of my record-keeping system. In your e-mail, propose a new due date. Typically the extension is by one class meeting (two or three calendar days). You do not need to explain why you're using your late pass; the reason makes no difference to me.

Academic Honesty

Carleton's academic honesty policy governs cheating, plagiarism, and similar offenses. It is academically dishonest for you to copy work from another student, an Internet site, or any other source and present the work as your own. If the college finds that you have violated its standards of academic honesty in this course, whether for a major infraction or a minor one, then you will receive an F in the course.


Readings are from our textbook, Problem Solving with Algorithms and Data Structures using Python, by Bradley N. Miller and David L. Ranum. The source code is available electronically, but note well that our official class code snippets are often a bit different.

M 09/13011.1-1.7introduction, setsIntroductionset.py
W 09/15027.2sets, lab timeClasses
F 09/17034.2-4.2.1efficiency, listsEfficiency
M 09/20042.3.1-2.3.5stacks, parenthesesXMLstack.py, callstack.py
W 09/22052.4queues, radix sortqueue.py, radixsort.py
F 09/24063.1-3.3recursionRecursionrecursive.py
M 09/27073.4-
W 09/29085.1-5.3trees, lab timeScene Trees
F 10/0109First Exam (Days 01-07)
M 10/04105.4binary trees, lab timebinarytreenode.py
W 10/06115.5.1parsingInterpretationparser.py
F 10/08125.5.2evaluation, tree traversalsyntaxsemantics.py
M 10/11135.6binary search treesbinarysearchtreenode.py
W 10/1314hashing, chainingDictionariesintdictionary_bstn.py
F 10/1515AVL treesAVL Treesapplet
M 10/18Midterm Break
W 10/20164.3.3hash tablesProfilingdictionary_list.py, dictionary_table.py, applet
F 10/2217Second Exam (Days 08-15)
M 10/25186.1-6.3graphsgraph.py
W 10/27196.4.1breadth-first searchMazes
F 10/29206.4.2depth-first search, topological sortCourses, courses.py, scope.nb
M 11/01216.4.5Dijkstra's algorithmProjectpriorityqueue_list.py
W 11/03225.7priority queues, binary heapsHeapspriorityqueue_avltn.py
F 11/0523heap sort, building heapsHeap Building, applet
M 11/08244.4.5-4.4.6sortingSelection
W 11/1025lab time, progress report
F 11/1226Third Exam (Days 16-24)
M 11/1527conclusion
W 11/1728lab time, progress report
M 11/22Project due 5:00 PM