2009 June 1 / jj|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Carleton College CS 201, Spring 2009, Prof. Joshua R. Davis
This is a second course in computer science. The focus is on data structures, which are used to organize information in computer programs. Examples include stacks, queues, trees, graphs, and hash tables. For each data structure, our goal is to understand both its theoretical properties and its practical value. We perform a mathematical analysis of its efficiency, and we apply the data structure to a concrete programming problem. Indeed, most of the assignments in this course take the form of programs, in Python.
The official prerequisite is CS 111. More generally, this course is appropriate for students who are comfortable with programming, including recursion and objects, and who have not taken more advanced courses. Talk to me if you are concerned about your background.
Our class meets in CMC 209 during period 4A (MW 12:30PM-1:40PM, F 1:10PM-2:10PM). The basic materials are
Here's how you get in contact with me:
Dr. Joshua R. Davis (most people call me Josh)
E-mail: jj|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Office: CMC 327, x4482
Office hours: Mon 3:00-3:50, Tue 2:00-2:50, Wed 3:00-3:50, Thu 1:00-1:50. You can also make an appointment; simply pick a free time from my weekly schedule and e-mail me. You can also talk to me after class.
Eric Alexander, a junior CS major, is the prefect for this course. As a prefect, he 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.
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 ("How do I run my Python program?") as well as conceptual questions about assignments.
Final grades (A, B, C, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades. The following elements contribute to the final grade.
You are expected to spend at least 10 hours per week on this course outside class. 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.
For some assignments the students are expected to work in pairs. Your pair hands in a single copy of the assignment with both names on it. You are encouraged to talk with other pairs — to bounce ideas off them, for example — but the work that you submit must be the work of your own pair. The two members of a pair must contribute roughly equally.
Other assignments are individualized, in that each student hands in her own work. Even on these assignments you are encouraged to talk with other students. However, you should write up your work separately, in your own words.
In short, you may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is an act of Academic Dishonesty.
During the term, you have one free pass to hand in an assignment late. Here is how you activate it. Instead of handing in the assignment, send me e-mail (by the due date) declaring that you are using your late pass and proposing a new due date. If the due date is extended by only one class meeting, then no explanation is necessary; if you need longer, then convince me. Use your free pass wisely; once you have used it, no late assignments are accepted, except in extreme circumstances that are truly beyond your control.
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 Office of Disability Services.
| Date | Day | Reading | Topic | Assignment | Notes |
|---|---|---|---|---|---|
| M 3/30 | 01 | 1.1-1.3 | introduction, sets | Introduction | set.py
|
| W 4/01 | 02 | 1.4-1.7 | Python | Tic Tac Toe | |
| F 4/03 | 03 | 7.2 | linked lists, arrays | ||
| M 4/06 | 04 | 4.1-4.2.1 | efficiency | Efficiency | |
| W 4/08 | 05 | 2.3 | stacks | stack.py
| |
| F 4/10 | 06 | 2.4 | queues | Well-Formed XML | queue.py, radixsort.py
|
| M 4/13 | 07 | 3.1-3.3 | recursion | gcd.py, debug.py
| |
| W 4/15 | 08 | 3.4-3.4.3.3 | recursion | Solving Mazes | hanoi.py, Hanoi.zip
|
| F 4/17 | 09 | 5.1-5.4 | trees | binarytree.py, tree.py
| |
| M 4/20 | 10 | 5.5.1 | parsing | parser.py
| |
| W 4/22 | 11 | Exam 1 | |||
| F 4/24 | 12 | evaluation | Interpretation | syntaxsemantics.py
| |
| M 4/27 | 13 | 5.5.2 | tree traversal | ||
| W 4/29 | 14 | 5.6 | binary search trees | binarysearchtree.py, dictionarybst.py
| |
| F 5/01 | 15 | AVL trees | Color Histograms | tree-balancing applet | |
| M 5/04 | Midterm Break | ||||
| W 5/06 | 16 | 4.3.3 | hash tables | hash table applet | |
| F 5/08 | 17 | hash tables | hashtable.py, QHash, GHashTable, NSDictionary, .NET Dictionary
| ||
| M 5/11 | 18 | 6.1-6.3 | graphs | Search With Context | graph.py
|
| W 5/13 | 19 | 6.4.1 | breadth-first search | ||
| F 5/15 | 20 | 6.4.2 | depth-first search, topological sort | CS Course Graph 2009-2010 | |
| M 5/18 | 21 | 6.4.5 | Dijkstra's algorithm | Exam 2 | |
| W 5/20 | 22 | 5.7 | binary heaps, priority queues | ||
| F 5/22 | 23 | building heaps, heap sort | Final Project | heap sort applet | |
| M 5/25 | 24 | project work | |||
| W 5/27 | 25 | implementing Python | |||
| F 5/29 | 26 | project work, progress report | |||
| M 6/01 | 27 | quick sort | |||
| W 6/03 | 28 | conclusion, progress report | |||
| S 6/06 | Final Project due 11:00AM | ||||