Bryn Mawr College
CS 206: Introduction to Data Structures
Spring 2020

General Information

An introduction to the fundamental data structures of computer science: lists, stacks, queues, trees, Binary Search Trees, 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.

Instructor: Geoffrey Towell , Park 204
E-Mail: gtowell at brynmawr dot edu
WWW: http://cs.brynmawr.edu/~gtowell
Office hours: T 10-11AM, W 3-4pm, or by appointment
Textbook: Data Structures and Algorithms by Goodrich, Tamassia and Goldwasser

TA hours in Park 231

Sun - Thurs 6:30pm-9:30pm

Prerequisites

One of the following courses (or their equivalents at Haverford or Swarthmore) is required.

CS 110
CS 113
CS 115

Or permission of the instructor.

Total grade breakdown

Grades will be awarded based on the number of points earned and according to the percentage breakdowns shown.

Homework 45%

Lab 5%

Midterms (2) 32%

Exam 1: Feb 27, In class
Exam 2: ~~April 7, In class~~ TBA

Final exam 18%

~~The final will be self-scheduled during exam week. It will cover material from the whole course, but will focus on topics from second half of the semester.~~
Grade Percentage Breakdown:

First Exam: 20%
Final Exam: 20%
Mini Homeworks: 10%
Programming Homework: 50%

Percentages are based on total points available in each part. For mini-homeworks 100% is turning in a credible effort on 10 of the 12 minis. All extra credit points will be assigned to the homework group

Based on advice from the school administration the final optional. yes OPTIONAL. Should you choose to not take the final the grade breakdown will be

First Exam: 24%
Mini Homeworks: 14%
Programming Homework: 60%
Email saying you are not taking the final: 2%

If you turn in the final and it does not help your grade I will consider it as equivalent to an email saying you do not want to take the final.

The final will be posted on the class website no later than May 3. Rules for taking the exam will be in a separate file from the exam. The exam must be turned in (or am email saying you will not take the exam) by May 15. (Seniors have an earlier due date.) Open and read the rules first and at your leisure. Do not open the exam until you are ready to start. (This will be clear on the class website.) I will send another email when the final exam is posted.

All exams will be closed book, closed notes, no electronic devices unless otherwise noted.

Final Exam

Read the instructions first. Read the instructions second. Only when you are ready to take the exam should you click on the link to get the test. The final is due by 12:30pm EDT on May 15. This is the end of the Bryn Mawr exam period.

Instructions One late modification to the instructions. You may have a computer (or tablet) open to write directory into the PDF using you favorite PDF writing tool. There may (or may not) be enough space for your answers. However you submit, legibility is your responsibility. That said, I have not had significant problems with legibility on any of the mini-homeworks.
The exam Do not click on this link until you are ready to start the exam

Late work policy

Everyone gets 2 24 late passes. These can be used at any time simply by sending me an email. The only requirement is that you send email requiesting the use of a late pass prior to the due date of the assignment. You need not get my approval, it is automatic. Other than these passes, late work is not accepted.

Attendance and Participation

Attendance at, and active participation in, all class sessions is expected of all students. Participation will be taken into account in awarding of final grades for students who are on the edge between two grades. For example, a student with a B+/A- average and a strong attendance and participation record would receive an A-, while a student with a weak record would receive a B+.

Collaboration

It is your responsibility to understand and follow the collaboration policy in this class. The goal of the policy is to encourage collaboration while ensuring that you and your classmates really engage in learning how to solve the challenging problems you will see in this course. If you are ever uncertain if collaboration or certain sources are allowed, ask. should ask the professor.

You are encouraged to discuss the lecture material and the labs and problems with other students, subject to the following restriction: the only product of your discussion should be your memory/understanding of it - you may not write up solutions together, or exchange written work or computer files.

Code should not be copied without permission from the author. If permission is given, code should be cited at the location it is used with a comment. If your solution is inspired by any outside resources (I understand that sometimes it is hard to not see things), you MUST cite.

Assignments/Projects

Despite my best efforts, homeworks may have sections that are not quite correct. If you find one, let me know. If I agree that the issue is an issue, bonus points will be awarded as follows:

3 points for the first issue reported
2 points for the second issue reported
1 point for the third issue reported

Ordering is based on date of email recipt. One bonus per person per assignment.

Assignment 1 due Jan 31 prior to 11:59pm
Assignment 2 due Feb 06 prior to 11:59pm
Assignment 3 due Feb 13 prior to 11:59pm
Assignment 4 due Feb 20 prior to 11:59pm
Assignment 5 due March 5 prior to 11:59pm
Assignment 6 due March 26 prior to 4:59pm
Assignment 7 due April 2 prior to 11:59 pm
Assignment 8 due April 9 prior to 11:59 pm
Assignment 9 due April 16 prior to 11:59 pm The extended priority queue interface Heap Priority Queue
Assignment 10 due April 23 prior to 11:59 pm SortBase.java MergeLL.java

Full credit answer

Assignment 11 due April 30 prior to 11:59 pm BookReader.java dickens.txt

Labs

Lab 1 Jan 23

Lab 2 Jan 30

Lab 3 Feb 6

Lab 4 Feb 13

Lab 5 Feb 20

Lab 6 March 5

Also, the following files are used in Maze 6.

Extra Credit

Towers of HanoiThe challenge returns. This time with video!

Lectures

Jan 21
Intro and Review
- Lecture Notes
- Intro Quizlet, with answers
Jan 23
More Java Review
- Lecture Notes We did not get to the last 2 slides
- The SPCA example Animal Dog Cat Shelter
- Throwing and catching NameAndAge.java
- Some string work Stringer.java
Jan 28
More about inheritance, Generics
- Lecture Notes
- Try catch example from start of class
- Method overriding and casting. Going to the dogs example.
- String splitting. Introduced but not discussed in class
- Generic Methods
- Generic Classes
- Nested Classes. This is similar, but not nearly as well motivated at the nexted class for holding a three part name I discussed in class.
Jan 30
the ArrayList data structure
- Lecture Notes
- The ArrayList interface -- handed out in class
- A complete (and commented) implementation of the ArraListInterface
- The WordCounter class
- A simple text file to use with Word Counter I cannot put the text I used in class as it is still under copyright
Feb 4
the Linked List data structure
- Lecture Notes
- References and Equality in java
- An enumerated type of Rabbit Breeds
- A very simple class for holding rabbits
- An interface defineition for linked list Same as handout in class
- A linked list class for Rabbits
Feb 6
Generic Linked Lists, Doubly linked lists
- Lecture Notes
- Using Comparable
- An enumerated type of Rabbit Breeds (identical to lec 5)
- A very simple class for holding rabbits Identical to lec5 except for implementing Comparable
- An interface defineition for linked list follows lec 5 except its generic
- A generic linked list class
- A generic double linked list class
- Sorted Double Linked List An extension of DoubleLinkedList
Feb 11
Algorithmic Analysis
- Lecture Notes
- An enumerated type of Rabbit Breeds (identical to lec 5)
- A very simple class for holding rabbits Identical to lec5 except for implementing Comparable
- An interface defineition for linked list follows lec 5 except its generic
- A generic linked list class
- A generic double linked list class
- Sorted Double Linked List An extension of DoubleLinkedList
- A class to time how long it takes to run
- Speedy InterfaceA very simple interface definition for various algorithm runtimes
Feb 13
Exceptions, Scope and Restaurants
- Lecture Notes
- bad Exception handling example 1
- bad Exception handling example 2
- OK-ish Exception handling
- better Exception handling but still has issues
- Scope
Feb 18
Stacks
- Lecture Notes
- Java interface for Stack
- Array-based implementation of Stack
- Small class to show JVM method stack
- Using a stack to recognize palindromes
Feb 20
Queues
- Lecture Notes
- Java interface for Queue
- Array-based implementation of Queue
- Bank Simulator Bank Interface Bank Bank Simulator (this is the "main" class)Customer Customer provider
Feb 25
Review
- Same sample questions, mostly discussed in class The table on page 2 now has a copy, filled out, on page 3.
- From one of the questions posed in class
- Another question from class
- Java interface for QueueSlightly different names, just for QM
- Interface that defines a merge function
- Some stylistically poor code The version is annotated with all of the flaws I found. The version in the sample question doc is not so annotated.
March 3
Exam Recap -- Recursion
- Lecture notes
- most of the code from lecture
- Writing to files
- Code for the towers of Hanoi
March 5
More Recursion
- Lecture notes
- mostly code from previous lecture, but touched on again
- May not actually be discussed. Writing to files
- Code for the towers of Hanoi
- Code for binary search and Backtracking binary(ish) search
March 19
Trees -- Part 1 Watch the video available on the course moodle page. The lecture only goes through slide 11. From slide 11, using paper and pencil build and label binary trees for the second, third and fourth sets of numbers. Send a picture of these trees to gtowell206@cs.brynmawr.edu. Lecture notes
March 24
Trees -- Part 2
- Lecture notes
- The interface specifying the public functions of Binary Trees
- Binary Tree implementation
March 26
Trees -- Part 3
- Lecture notes
- The interface Unchanged from lec 15.
- Binary Tree implementation lightly revise from lec 15. In particular, the insert and altInsert methods have been reworked. The altInsert method here is the one discussed in today's lecture
March 31
Trees -- Part 4
- Lecture notes
- The interface Unchanged from lec 15.
- Binary Tree implementation lightly revised from lec 15 and 16. In particlar, a non-recursive version of iMaxKey was added. Likewise iRemoveAlt was added as this is the code presented in the lecture.
April 2
Trees -- Part 5 (the last part)
- Lecture notes
- The interface Still unchanged from lec 15.
- Array-based Binary Tree implementation This is a complete implementation of an array-based binary tree. In lecture I only discussed height. It is all here!
April 7
Priority Queues (chapter 9.1, 9.2)
- Lecture notes
- Interface for Priority Queue
- Unsorted Priority Queue This is built on top of an ArrayList
April 9
Priority Queues (chapter 9.3)
- Lecture notes
- Interface for Priority Queue Slightly changed from the previous lecture to include the enum for queue order here rather than in the priority queue implementation
- Heap Priority Queue A heap based priority queue. This is a form of array based binary tree.
April 14
Sorting with Priority Queues (chapter 9.4)
- Lecture notes
- Interface plus more(!)for Priority Queue This replaces the interface definition we have been using with an abstract class. Using abstract class allows definition of inner class to be defined here then used by descendents.
- Heap Priority Queue Much the same as in lect 20, but for use of AbstractPriorityQueue
- ArrayList Priority Queue doing selection sort. Much the same as in lect 19, but for use of AbstractPriorityQueue
- ArrayList Priority Queue doing insertion sort.
April 16
Merge Sort (Chapter 12.1)
- Lecture notes
- Abstract class base for all sorting Provides several utility methods
- Heap sort
- Insertion sort
- Selection sort
- Merge sort
April 21
Quick Sort (Chapter 12.2)
- Lecture notes
- Abstract class base for all sorting Provides several utility methods. Unchanged from Lec 22.
- QuickSort sort
April 21
Final Sort comments and intro to hash tables (Chapter 10.1-10.2)
- Lecture notes
- Abstract class base for all sorting Provides several utility methods. Unchanged from Lec 22.
- QuickSort sort
- Merge sort
- A very simple student class with some static methods (gasp)
- QuickSort on objects. It is not stable
- Mergesort of objects. It is stable.
April 28
Hash tables (Ch 10.2)
- Lecture notes
- Very simple hashtableSo simple as to be almost useless
- Separate Chaining Hashtable Does everything but rehash
- BookReader class From HW11 Used in main of SepChainHT
- A book to read
April 28
Hash tables and a final example program
- Lecture notes
- Log Analyzer Very simple log analysis
- Log line Hold the line and parses the line
- A very small web server log

Links

Learning Accommodations

Students requesting accommodations in this course because of the impact of disability are encouraged to meet with me privately early in the semester with a verification letter. Students not yet approved to receive accommodations should also contact Deb Alder, Coordinator of Accessibility Services, at 610-526-7351 in Guild Hall, as soon as possible, to verify their eligibility for reasonable accommodations. Early contact will help avoid unnecessary inconvenience and delays.

This class may be recorded.