Bryn
Mawr College
CS 206: Introduction to Data Structures
Fall 2019
The course at a glance
General
Information
An introduction to the fundamental data structures of computer science: lists, stacks, queues, trees, BSTs, graphs, sets and their accompanying algorithms. Principles of algorithmic analysis and object reasoning and design will be introduced using mathematical techniques for the notions of both complexity and correctness. More practical issues, such as memory management and hashing, will also be covered.
Instructor: Geoffrey Towell , Park 204
EMail: gtowell at cs dot brynmawr dot edu
WWW: http://cs.brynmawr.edu/~gtowell
Office hours: T 10:0011:00AM, W 1:002:00PM, or by appointment
Textbook: Data Structures and Algorithms by Goodrich, Tamassia and Goldwasser
TA hours in Park 231
Sun  Thurs 6pm10pm
Prerequisites
One of the following courses (or their equivalents at Haverford or Swarthmore) is required.
Or permission of the instructor.
Assignments/Projects
Labs
Thursday 2:253:45 Park 231 (Lab attendance is required)
 Sept 5: Lab 01
 Sept 12: Lab 02
The code below is uncommented becase you are not expected to comment code you write in labs.
 Sept 19: Lab 03
 Sept 26: Lab 04
 Oct 31: Lab 07
 Nov 14: Lab 08
Classes
 Sept 3:
 Sept 5:
 Sept 10 Generics (Ch 2 in text):
 Sept 12 Array List (Ch 3 in text):
 Sept 17 Linked List (Ch 3 in text):
 Sept 19 Doubly Linked Lists and Circular Linked Lists (Ch 3 in text):
 Sept 24 Exceptions, Scope, and Restaurants :
 Sept 26 Analysis of Algorithms:
 Oct 1 Stacks:
 Oct 3 Queues:
 Oct 22 Midterm, Iterators and Recursion:
 Oct 24 Recursion and Backtracking with recursion:
 Oct 29 Trees:
 Towers of Hanoi challenge For extra credit (5 points), do the towers of hanoi well and believably (I will define well.) For even more extra credit, do the towers of hanoi very well (beat my time, again, I have to believe). In either case, use the link above to time yourself on the towers. Use you login name as your ID. You may enter as many times as you wish. I will use your best time. If you have a particularly nimble friend, have thet person do the towers  you may submit their time.
 Slides
 Deep vs Shallow CopyObject.java
 Oct 31 Trees Again:
 Nov 05 Priority Queues:
 Slides
 Midterm 2 change: Midterm 2 will be take home. Distributed on Nov 20, due before 11:30AM Nov 26. No class on Nov 26.
 Nov 07 Priority Queues and Sorting:
 Slides
 Code for Sorting comparison. This code contains sample code for upheap and downheap This code is tied to a very simple implementation that handles only arrays of integers.
Interestingly, for random data, the time required for the heap poll is 15 to 20 times greater than the time for heap insert. This analysis will be expanded in the coming classes.
 Towers of Hanoi challenge ends Sunday Nov 10
 Nov 12 Recusion and merge sort:
 Nov 14 Recusion and quick sort:
 Nov 19 Maps and Hashing :
Links
