2010 November 17 / j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
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:
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 EhrenbergAdditionally, 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:
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
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.
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.
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.
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.
| Date | Day | Reading | Topic | Assignment | Notes |
|---|---|---|---|---|---|
| M 09/13 | 01 | 1.1-1.7 | introduction, sets | Introduction | set.py
|
| W 09/15 | 02 | 7.2 | sets, lab time | Classes | |
| F 09/17 | 03 | 4.2-4.2.1 | efficiency, lists | Efficiency | |
| M 09/20 | 04 | 2.3.1-2.3.5 | stacks, parentheses | XML | stack.py, callstack.py
|
| W 09/22 | 05 | 2.4 | queues, radix sort | queue.py, radixsort.py
| |
| F 09/24 | 06 | 3.1-3.3 | recursion | Recursion | recursive.py
|
| M 09/27 | 07 | 3.4-3.4.3.3 | recursion | hanoi.py
| |
| W 09/29 | 08 | 5.1-5.3 | trees, lab time | Scene Trees | |
| F 10/01 | 09 | First Exam (Days 01-07) | |||
| M 10/04 | 10 | 5.4 | binary trees, lab time | binarytreenode.py
| |
| W 10/06 | 11 | 5.5.1 | parsing | Interpretation | parser.py
|
| F 10/08 | 12 | 5.5.2 | evaluation, tree traversal | syntaxsemantics.py
| |
| M 10/11 | 13 | 5.6 | binary search trees | binarysearchtreenode.py
| |
| W 10/13 | 14 | hashing, chaining | Dictionaries | intdictionary_bstn.py
| |
| F 10/15 | 15 | AVL trees | AVL Trees | applet | |
| M 10/18 | Midterm Break | ||||
| W 10/20 | 16 | 4.3.3 | hash tables | Profiling | dictionary_list.py, dictionary_table.py, applet
|
| F 10/22 | 17 | Second Exam (Days 08-15) | |||
| M 10/25 | 18 | 6.1-6.3 | graphs | graph.py
| |
| W 10/27 | 19 | 6.4.1 | breadth-first search | Mazes | |
| F 10/29 | 20 | 6.4.2 | depth-first search, topological sort | Courses, courses.py, scope.nb
| |
| M 11/01 | 21 | 6.4.5 | Dijkstra's algorithm | Project | priorityqueue_list.py
|
| W 11/03 | 22 | 5.7 | priority queues, binary heaps | Heaps | priorityqueue_avltn.py
|
| F 11/05 | 23 | heap sort, building heaps | Heap Building, applet | ||
| M 11/08 | 24 | 4.4.5-4.4.6 | sorting | Selection | |
| W 11/10 | 25 | lab time, progress report | |||
| F 11/12 | 26 | Third Exam (Days 16-24) | |||
| M 11/15 | 27 | conclusion | |||
| W 11/17 | 28 | lab time, progress report | |||
| M 11/22 | Project due 5:00 PM | ||||