2008 November 20 / jjddaavviiss@@ccaarrlleettoonn..eedduu

Data Structures

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

Introduction

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 linked lists, arrays, 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 significant programming problem. Indeed, most of the assignments in this course take the form of programs, in Python.

The official prerequisite is CS 111 (Introduction to Computer Science). 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 2A (MW 9:50AM-11:00AM, F 9:40AM-10:40AM). The basic materials are

• Problem Solving with Algorithms and Data Structures using Python, by Bradley N. Miller and David L. Ranum. This text has been used in recent terms at Carleton.
• Source code from the textbook.
• Transition to Python, if you need to practice with the Python language.
• Python Documentation sounds useful.
• Exam 1 (Percentiles: 75th = 88, 50th = 75, 25th = 69)
• Exam 1 Answers
• Exam 2 (Percentiles: 75th = 90, 50th = 78, 25th = 72)
• Exam 3 (Percentiles: 75th = 79.5, 50th = 74.5, 25th = 64.5)

Here's how you get in contact with me:

Dr. Joshua R. Davis (most people call me Josh)
E-mail: jjddaavviiss@@ccaarrlleettoonn..eedduu
Office: CMC 327, x4482
Office hours: M 5A (1:40-2:30), T 2C (10:00-11:00), W 3A (11:00-12:00). 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.

There is also a prefect for this course. A prefect holds a couple of review sessions each week, in which you review material from class, get questions answered, tackle additional problems, etc. The prefect is also available for individual tutoring.

Jacob Hilty
E-mail: hhiillttyyjj@@ccaarrlleettoonn..eedduu

Additionally, our computer lab (CMC 306) is often staffed with computer science 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.

Responsibilities

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.

• Participation (5%): This is a measure of how engaged with the course you are. You are expected to attend every class meeting (promptly) and participate in the discussion and group work. You are expected to have read the relevant textbook sections before class; you will then get much more out of the discussion. You are also required to visit me in my office at least once during the first two weeks. You can make up for a deficiency in class participation by talking with me frequently in office hours, demonstrating exceptional effort and interest, etc.
• Homework (35%): In this course, most of your learning takes place while doing homework. Most homework takes the form of programs, but there are occasional written problems too. To give you some flexibility, homework is collected once per week rather than at every meeting.
• Midterm Exam 1 (20%): The first midterm exam is given in class sometime around Day 10.
• Midterm Exam 2 (20%): The second midterm exam is cumulative and given as a take-home exam sometime around Day 19.
• Final Exam (20%): The final exam is cumulative and scheduled for Saturday November 22, 8:30AM-11:00AM. Self-scheduled final exams are not allowed.

You are expected to spend at least 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you spend less, then your education is suboptimal; we should discuss ways to enrich it.

Working With Others

You are encouraged to work with others on homework. Work together to figure out the problems/programs, but write/type them up on your own, in your own words, and hand them in on your own. 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.

Special Accommodations

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 in the first week of class. You may need to make official arrangements with the Office of Disability Services.

Schedule

Date	Day	Reading	Topic	Homework	Notes
M 09/15	01	1.1-1.3	introduction	Homework 1 (due Tue)
W 09/17	02	1.4-1.7	Python	Assignment 2 (due Mon)
F 09/19	03	7.2	linked lists		linkedlist.py
M 09/22	04	4.1-4.2.1	doubly-linked lists, efficiency	Assignment 3 (due Mon)
W 09/24	05	2.3.1-2.3.5	efficiency, stacks		stack.py
F 09/26	06	rest of 2.3	stacks		liststackqueue.pdf, stackapps.pdf
M 09/29	07	2.4	queues, radix sort	Assignment 4 (due Sat)	queue.py, radixsort.py
W 10/01	08	3.1-3.3	recursion		Hanoi.zip, hanoi.py
F 10/03	09	3.4-3.4.3.3	recursion
M 10/06	10	Exam 1
W 10/08	11		recursion	Assignment 5 (due Mon)
F 10/10	12	5.1-5.4	trees
M 10/13	13		trees	Assignment 6 (due Wed)
W 10/15	14	5.5.1	parsing
F 10/17	15	5.5.2	binary tree traversals
M 10/20	midterm break
W 10/22	16	5.6	binary search trees, dictionaries	Assignment 7 (due Mon)	bst.py, dicthasbst.py
F 10/24	17		AVL trees		tree-balancing applet
M 10/27	18	5.7	binary heaps, priority queues
W 10/29	19	4.3.3	building heaps, heap sort, hashing		heap sort applet
F 10/31	20		hash tables	Exam 2 (due Mon)	hash table applet
M 11/03	21		hash tables	Assignment 8 (due Mon)	hashtable.py
W 11/05	22	4.3	searching
F 11/07	23	4.4	sorting
M 11/10	24	6.1-6.3	graphs
W 11/12	25	6.4.1	breadth-first search
F 11/14	26	6.4.2	depth-first search	Assignment 9 (due Wed)	vertex.py, graph.py
M 11/17	27	6.4, 6.5	topological sorting, Dijkstra's algorithm		CS Courses
W 11/19	28		conclusion, evaluations		graphics3D.py
S 11/22	Final Exam, 8:30AM-11:00AM