CS206: Data Structures (Spring 2010)

Bryn Mawr College
CS 206: Data Structures
Spring 2010
Course Materials
Prof. Deepak Kumar

Information

Texts

Important Dates

Assignments

Lectures

Grading

Links

General Information

Instructor: Deepak Kumar, 246 Park Hall, 526-7485
E-Mail: dkumar at cs brynmawr dot edu
WWW: http://cs.brynmawr.edu/~dkumar

Lecture Hours: Tuesdays & Thursdays , 10:00a to 11:30a
Room: Park 336 (WE WILL CONTINUE TO MEET IN ROOM 336)
Lab: TBA in Room 231 (additional lab hours will also available, see below)

Laboratories:

Computer Science Lab Room 231 (Science Building)
You will also be able to use your own computer to do the labs for this course.

Texts & Software

(REQUIRED) Data Structures & Algorithms Using Python and C++, by David reed & John Zelle, Franklin, Beedel & Associates, 2009.
Software: We will be using Python, and C++ programming languages for all laboratory exercises. Software for writing and running programs is available on all computers in the lab.

Important Dates

January 19: First lecture
March 4: Exam 1
April 27: Last lecture
April 29: Exam 2

Assignments

Unless explicitly specified, all assignments are due at the beginning of the class (BY 10:15a sharp) on the date due. No credit will be awarded for any late work.

For all programming exercises, hand in a printout of your program file along with a printout of the screen output of your program showing an example run. On the top of every program include the following comment header:

/* Name:     Your Name 
   Exercise: Exercise#
   Date:     Date assigned        
   
   Purpose:  A short description of the program/exercise.  

*/

Extra Credit Assignment#1 (Due on Thursday, January 21): Write and run the car loan program. Hand in a print out of the program along with a couple of sample runs.
Assignment#1 is posted (Due on Tuesday, January 26, 2010). Click here for details.
Assignment#2 is posted (Due on Tuesday, February 2, 2010): Click here for details.
Assignment#3 is posted. (Due on Tuesday, February 9, 2010): Click here for details.
Assignment#4 is posted (Due on Thursday, February 25): Click here for details.
Assignment#5 is posted (Due on Thursday, February 25): Click here for details.
Assignment#6 is posted (Due on Tuesday, March 30):Click here for details.
Assignment#7 is posted (Due on Thursday, April 15): Click here for details. (Note: Part#2 is due on Tuesday, April 20)

Lectures

Week 1 (January 19, 21)

January 19: Course introduction, logistics, overview. Refresher on Python.

Extra Credit Assignment#1 (Due on Thursday, January 21): Write and run the car loan program. Hand in a print out of the program along with a couple of sample runs.
January 21: Python refresher, contd. Control flow in Python: if-statements, for and while loops, etc.

Read: The Python Overview handout.

Assignment#1 is posted (Due on Tuesday, January 26, 2009). Click here for details.

WE WILL CONTINUE TO MEET IN ROOM 336
Week 2 (January 26, 28)

January 26: Writing functions in Python. Doing random sampling with bias. Modules and APIs. Other examples.

January 28: Creating and using modules in Python. Example of a calendar module. Using the Zelle graphics module.

Assignment#2 is posted (Due on Tuesday, February 2, 2009): Click here for details.
Week 3 (February 2, 4)

February 2: (Groundhog Day) Reviewing parameterized graphic designs. Taking it a step further: modeling objects. Classes, instances, properties, attributes, components, peers, capabilities, etc. The vocabular of object modeling. How to model objects in Python. Examples: Dice, a drawing turtle, ...

Read: Chapter 2 from Reed & Zelle.

Programs from class: Dice.py , circle.py, ellipse.py

February 4: Modeling a LOGO-style turtle. Fun with turtle graphics.

Assignment#3 is posted. (Due on Tuesday, February 9, 2010): Click here for details.

Programs from class: Scribbler.py, Square.py
Week 4 (February 9, 11)

February 9: Implementing the Scribbler class. Using it. Drawing Koch curves and Koch snowflakes...

Program(s) from class: Koch.py

February 11: Snow Day! No class. College is clsoed. Have fun designing your own Koch Snow Flakes!
Week 5 (February 16, 18)

February 16: Modeling Playing cards. Chosing between representations. Implementing the interface as a class.

Read: Chapter 2 from Reed & Zelle.

Program(s) from class: Card.py

February 18: Modeling a deck of cards. Shuffling a deck: techniques for humans; algorithms for computers. Knuth/Fisher-Yates algorithm.

Assignment#4 is posted (Due on Thursday, February 25): Click here for details.

Programs from class: Deck.py

Read: Chapter 3 from Reed & Zelle.
Week 6 (February 23, 25)

February 23: Dictionaries in Python. More on modeling data.

Read: Chapter 3 from Reed & Zelle.

Assignment#5 is posted (Due on Thursday, February 25): Click here for details.

February 25: Modeling large data. Pre-processing prior to processing data. E.g. Zip code data for the United States.
Week 7 (March 2, 4)

March 2: Dictionaries in Python. Counting word frequencies in text.

March 4: Exam 1 is today.
Week 8 (March 9, 11)

No classes. Spring Break!
Week 9 (March 16, 18)

March 16: Review of exam. Discrete Event Simulation: concepts and key ideas. Queues as an abstract data type. Implementing Queues in Python. Using queues for simulations.

March 18: No class. Deepak is out of town.
Week 10 (March 23, 25)

March 23: Simulation contd. Exceptions and exception handling in Python. Python data model: references, shallow and deep copy, revisitng function parameters.

Read: Chapter 4 from Reed & Zelle.

Assignment#6 is posted (Due on Tuesday, March 30). Click here for details.

March 25: Python data model: references, shallow and deep copy, revisitng function parameters. Linked implementation of Queues in Python.

Read: Chapter 5 from Reed & Zelle.
Week 11 (March 30, April 1)

March 30: Efficiency of algorithms. Sorting algorithms: Selection Sort, Insertion Sort, Quick Sort.

April 1: (April Fool's Day) No class. Deepak is out of town.

Week 12 (April 6, 8)

April 6: QuickSort. An introduction to hierarchical data structures. trees. terminology.

Read: Chapter 6 from Reed & Zelle.

April 8: Binary Trees, Binary Search Trees. Implementations. Other kinds of trees.

Assignment#7 is posted (Due on Thursday, April 15): Click here for details. Note: Part#2 is due on April 20.
Week 13 (April 13, 15)

April 13: Implementing Binary Search Trees. Testing the implementation.

April 15: (Tax Day) Overloading comparison operators. Heaps: Min/Max Heaps, Priority Queues, implementations.

Read: Chapter 13 about Heaps.
Week 14 (April 20, 22)

April 20: Network Data Structures: Graphs: Terminology, topology, applications, representations-Adjacency Matrix and Adjacency lists.

April 22: (Earth Day) Graph implementations in Python, search algorithms on graphs: Depth-first and breadth-first.

Week 15 (April 27, 29)

April 27: Graph algorithms: implementation. Course wrap up.
April 29: Exam 2 is today.

Grading

All graded work will receive a grade, 4.0, 3.7, 3.3, 3.0, 2.7, 2.3, 2.0, 1.7, 1.3, 1.0, or 0.0. At the end of the semester, final grades will be calculated as a weighted average of all grades according to the following weights:

Exam 1: 20%
Exam 2: 25%
Labs & Written Work: 55%
Total: 100%

General Information

Texts & Software

Important Dates

Assignments

Unless explicitly specified, all assignments are due at the beginning of the class (BY 10:15a sharp) on the date due. No credit will be awarded for any late work.

Lectures

Grading

Links

The graphics.py file

HTML documentation of graphics.py

A database of color names

General Information

Texts & Software

Important Dates

Assignments Unless explicitly specified, all assignments are due at the beginning of the class (BY 10:15a sharp) on the date due. No credit will be awarded for any late work.

Lectures

Grading

Links

The graphics.py file

HTML documentation of graphics.py

A database of color names

Assignments

Unless explicitly specified, all assignments are due at the beginning of the class (BY 10:15a sharp) on the date due. No credit will be awarded for any late work.