CS206: Data Structures, Bryn Mawr College
Douglas Blank, Associate Professor
Bryn Mawr College
Department of Computer Science
Fall 2010
Overview
This course provides an introduction to the fundamental algorithms and data structures of computer science: sorting, searching, recursion, backtrack search, lists, stacks, queues, trees, graphs, dictionaries. It also provides an introduction to the analysis of algorithms. Prerequisite: CMSC 205 or 110, or permission of instructor.
We will be especially interested in using data structures to solve problems that you are interested in. This might include: social justice, mathematics, scientific analysis, education, creativity, game playing, artificial intelligence, problem solving, and more.
General Information
Course URL: cs.brynmawr.edu/Courses/cs206/fall2010
Instructor: Douglas Blank, 248 Park Science Building, 526-6501
Email: dblank (at) cs (dot) brynmawr (dot) edu
Web: cs.brynmawr.edu/~dblank
Office hours: Tuesday and Thursday, 1-2pm and by appointment
Course Meetings: Monday and Wednesday, 2:30-4:30am
Lab: Park Science Building, room 337 Lab Assistants: Marissa (mmocenigo), Mondays 8-10pm, and Wednesday 9-11pm
Texts
|
|
Learning Python, Fourth Edition by Mark Lutz, O'Reilly Media, September 2009. ISBN 978-0-596-15806-4. 4th edition (which covers Python 3). |
|
How to Think like a Computer Scientist by Jeffrey Elkner, Allen B. Downey and Chris Meyers |
Materials
| For your final project, you may use a One Laptop Per Child. This would be especially appropriate if your final project was an educational project. |
|
Software
We will be using Python, version 3, for this course. In addition, we will use some custom Python modules that will be available here for downloading.
- chess.py - a general chess playing engine
Schedule (approximate, schedule may change)
| Week | Dates | Topic | Assignment |
|---|---|---|---|
| 1 | Mon 08/30/2010, Wed 09/01/2008 | Review of Python: Lists and Functions | Python Review |
| 2 | Mon 09/06/2010, Wed 09/08/2008 | Files and Input/Output; Dictionaries | No classes on Monday, Labor Day |
| 3 | Mon 09/13/2010, Wed 09/15/2008 | Lists, Dictionaries, and Files | |
| 4 | Mon 09/20/2010, Wed 09/22/2008 | Defining Classes | |
| 5 | Mon 09/27/2010, Wed 09/29/2008 | Object-Oriented Programming | mylist.py - code from class on Monday |
| 6 | Mon 10/04/2010, Wed 10/06/2008 | Binary Trees | |
| 7 | Mon 10/11/2010, Wed 10/13/2008 | Fall Break! No classes | |
| 8 | Mon 10/18/2010, Wed 10/20/2008 | Midterm Exam. Binary Trees. | |
| 9 | Mon 10/25/2010, Wed 10/27/2008 | Binary Trees, continued. Lab: 1 Million Items in tree; Lab: 20 Questions. Solution #1, #2, Solution #3. | |
| 10 | Mon 11/01/2010, Wed 11/03/2008 | Project: Interactive Fiction. | Format. For Wed: pick a game context, draw out a map, write code to read game file. |
| 11 | Mon 11/08/2010, Wed 11/10/2008 | Graphs | Reading the game file: interactive_fiction2.py |
| 12 | Mon 11/15/2010, Wed 11/17/2008 | Graph Traversals | Projects |
| 13 | Mon 11/22/2010, Wed 11/24/2008 | Loose Ends: Inheritence, Sorting, and Big O, Sorting, Searching, and Big O |
Thanksgiving begins after class! |
| 14 | Mon 11/29/2010, Wed 12/01/2008 | Searching and Review | Searching Graphs, Review |
| 15 | Mon 12/06/2010, Wed 12/08/2008 | Project Presentations | Projects, Final Projects |
Other dates of interest in Fall 2010:
| Monday, August 30 | Classes begin at Bryn Mawr, Haverford, and Swarthmore |
| Thursday/Friday, September 2- 3 | Confirmation of Registration for new students |
| Monday, September 6 | Labor Day (no classes at Bryn Mawr or Haverford) |
| Tuesday/Wednesday, September 7 and 8 | Confirmation of Registration for returning students |
| Friday, October 8 | Last day to declare a class Credit/No Credit; Fall break begins after last class |
| Monday, October 18 | Classes resume |
| Friday, October 22 | Last Day of 1st Qtr. Classes: all work due |
| Monday, October 25 | 2nd Qtr. Classes begin |
| Monday, November 1-12 | Preregistration for Spring 2011 |
| Fri-Sun, November 5-7 | Parents’ Weekend |
| Wednesday, November 24 | Thanksgiving begins after last class |
| Monday, November 29 | Classes resume |
| Thursday, December 9 | Last Day of Classes: all written work due |
| Friday/Saturday, December 10-11 | Review Period |
| Sun-Fri, December 12-17 | Examination Period |
| Saturday, December 18 | Winter Break begins (dorms close at 10:00 a.m.) |
Grading
Final grades will be calculated as a weighted average of all grades according to the following weights:
Written work: 25%Midterm Exam: 20%
Final Exam: 20%
Class participation: 25%
Project: 10%
dblank (at) cs (dot) brynmawr (dot) edu