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
E-Mail: gtowell at cs dot brynmawr dot edu
WWW: http://cs.brynmawr.edu/~gtowell
Office hours: T 10:00-11:00AM, W 1:00-2:00PM, or by appointment
Textbook: Data Structures and Algorithms by Goodrich, Tamassia and Goldwasser
TA hours in Park 231
Sun - Thurs 6pm-10pm
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:25-3: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
- Nov 14: Dec 5
- Dec 12: Review questions for final Attendance at lab is not required and not expected. I will not post solutions but I am available for discussion.
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 :
- Nov 21 Hashing :
- Nov 26 NO CLASS :
- Take home midterm due by 11:30 AM in Park 204. The instructions mistakenly say as slightly different location. Apparently I do not know the number of my own office.
- Test with answers
- Dec 3 Binary Search Trees, Balanced Birary Trees :
- Dec 5 Introduction to Graphs :
- Lecture covered the representation of graphs: Edge lists, Adjacency lists, and Adjacency Matrices.
- Node for Graphs
- Edge for Graphs
- Graph Both a driver class and examples of the use of depth first search to find if two nodes are connected and to find a path between two nodes.
- Dec 5 Dijkstra's shortest path :
Links
|