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

## Introduction

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:

• Design the data structure. What capabilities should it have?
• Implement the data structure. That is, write the code that provides the capabilities.
• Apply the data structure. What interesting problems does it let us solve?
• Analyze the data structure. How much time does each of its operations take? How much memory does it use?
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.

## Logistics

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:
• Exam 1, Answers (Percentiles: 75th = 38/48, 50th = 36/48, 25th = 28/48)
• Exam 2, Answers (Percentiles: 75th = 37/48, 50th = 36/48, 25th = 31/48)
• Exam 3, Answers (Percentiles: 75th = 35/39, 50th = 33/39, 25th = 30/39)
Here are the exams from my Spring 2009 version of this course:
• Exam 1, Answers (Percentiles: 75th = 31/36, 50th = 28/36, 25th = 22/36)
• Exam 2 (Percentiles: 75th = 21/24, 50th = 18/24, 25th = 15/24)
Here are the exams from my Fall 2008 version of this course:
• Exam 1, Answers (Percentiles: 75th = 88/100, 50th = 75/100, 25th = 69/100)
• Exam 2 (Percentiles: 75th = 90/100, 50th = 78/100, 25th = 72/100)
• Exam 3 (Percentiles: 75th = 79.5/100, 50th = 74.5/100, 25th = 64.5/100)

## Responsibilities

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.

• Participation: 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 in office hours (either about course material or other computing topics) or demonstrating unusual effort and interest.
• Assignments: In this course, most of your learning takes place while doing homework assignments. Most assignments take the form of programs, but there are occasional written reports too. Assignments count for 20% of your grade.
• First Exam: Given in class around Day 09, it counts for 20% of your grade.
• Second Exam: Given in class around Day 17, it counts for 20% of your grade.
• Third Exam: Given in class around Day 26, it counts for 20% of your grade.
• Project: The project is due at the end of the college's final exam period — Monday 2010 November 22, 5:00 PM. You are welcome to turn it in earlier, but you might have a partner, so do not make travel plans until your project is set. The final project counts for 20% of your grade. There is no final exam.
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.

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.

## Schedule

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
F 09/24063.1-3.3recursionRecursionrecursive.py
M 09/27073.4-3.4.3.3recursionhanoi.py
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