Bryn Mawr College
CS 206: Data Structures
Spring 2007
Course Materials
Prof. Deepak Kumar
General Information
Instructor: Deepak Kumar, 248 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
Lab: TBA
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.
Lab Assistants: The following Lab assitants will be available during the week (names and schedules will be posted by the end of this week) for assistance on lab assignments.
- Julia Ferraioli (jferraoi), Mondays 4:00p to 6:00 and Fridays 11:a to 1:00p
Texts & Software
Problem Solving with Algorithms & Data Structures using Python: by
Bradley Miller & David Barnum, Franklin Beedle & Associates, 2006. ISBN 1-59028-053-9
Python Software + IDLE (This software is already installed in the Computer Science Lab). The software is also available for your own computer from the CD included in your text.
|
 |
Important Dates
January 23 : First lecture
March 8: Exam 1
May 3: Last lecture/Exam 2
Assignments
-
Assignment#1 is posted (Due on Thursday, February 1)
- Assignment#2 is posted (Due on Tuesday, February 13)
- Assignment#3 is posted (Due on Tuesday, February 27)
- Assignement#4 is posted (Due on Tuesday, March 6)
- Assignement#5 is posted (Due on Thursday, March 29)
- Assignment#6 is posted (Due on Thursday, April 5)
- Assignment#7 is posted (Due on Tuesday, April 17)
- Assignment#8 is posted. Due on Tuesday, May 2.
Lectures
- Week 1 (January 23, 25)
January 23 : First class meeting. An overview of this course. What is computer science? The role of abstraction (procedural and data). Abstract Data Types, algorithms, algorithms+ data structures. Python: A quick Review.
Read: Sections 1.1-1.4.3 from Miller & Ranum
January 25: Review of Python.
Assignment#1 is posted (Due on Thursday, February 1)
- Week 2 (January 30, February 1)
January 30 : Review of Python, contd. List comprehensions. Introduction to Object-oriented programming. Data Abstraction in Python.
Read: All of Chapter 1 from Miller & Ranum
February 1: A look at computing prime numbers. Efficiency of algorithms (a first view). Data Abstraction in Python, contd.
Assignment#2 is posted (Due on Tuesday, February 13)
- Week 3 (February 6, 8)
February 6 : Number systems: decimal, binary, octal, hexadecimal. Converting from decimal to other number systems and vice versa. Stacks as an asbtract data type. Defining the interface and various implementations in Python.
Read: Sections 2.1-2.3 from Ranum & Miller
February 8 : Applications of Stacks. Expressions: infix, prefix, and postfix expressions. Converting from infix to postfix. Evaluating postfix expressions. the 'eval' function in Python.
Read: Section 2.3 from Ranum & Miller.
- Week 4 (February 13, 15)
February 13: Data Abstraction in Python, revisited. Modeling a deck of cards (and cards). Shuffling Algorithms: Human and computer. Python coding conventions. Simple exception handling.
February 15: Alternative representations for playing cards. Simple exception handling in Python and how to use it in your ADT modules. An introduction to Discrete event Simulation: single-queue single server to multiple-queues multiple servers. Doing discrete event simulation using queues. The Queue abstract data type.
Do: Assignment#3: Assignment#3 is posted (Due on Tuesday, February 27)
- Week 5 (February 20, 22)
February 20: Queues, contd. Discrete event simulation example: printer queues and wait times. Double-ended queues.
Read: Section 2.4 from Ranum & miller.
February 22: Recursion: an introduction. Writing simple recursive functions.
Read: Chapter 3 from Ranum & Miller.
- Week 6 (February 27, March 1)
February 27: Recursion, contd. The Python graphics.py module. Drawing the Sierpinski Triangles. An introduction to Koch Curves. Designing snowflakes...
Assignement#4 is posted (Due on Tuesday, March 6)
March 1: Review of simulation assignment. How to write reports. Review of turtle abstraction.
- Week 7 (March 6, 8)
March 6: What is an algorithm? A short history, and an introduction to Algorithm Analysis: empirical analysis (timing programs), and Asymptotic analysis (Big-O notation).
Read: Section 4.1 and 4.2 from Ranum & Miller
March 8: Exam 1 is today.
- Week 8 (March 13, 15)
No classes. Spring Break!
- Week 9 (March 20, 22)
March 20: Review of exam. Algorithm analysis. Searching: sequential search.
Read: Section 4.3 from Ranum & Miller
March 22: Searching: Binary search. Sorting.
RRead: Section 4.4 from Ranum & Miller
Assignement#5 is posted (Due on Thursday, March 29)
- Week 10 (March 27, 29)
March 27: Problem Session for Assignment#5 run by Julia Ferraioli. Thanks, Julia!
March 29: Sorting: Selection Sort, Insertion Sort, Shell Sort, Merge Sort, Quick Sort.
Read: Chapter 4 from Ranum & Miller
Assignment#6 is posted (Due on Thursday, April 5)
- Week 11 (April 3, 5)
April 3: Quicksort. Partitioning algorithms for use in Quicksort. Introduction to hiearchical data structures: trees, terminology, types of trees.
April 5: Making the sort more generic (use of cmp in Python). Binary Search Trees: implementation in Python. Tree traversals.
Read: DO NOT read Chapter 5 (it is horribly written and the code us rather ugly!). Rely on class notes!
Assignment#7 is posted (Due on Tuesday, April 17)
- Week 12 (April 10, 12)
April 10 : Binary Search Trees, contd. Implementation. Traversals. Some Python features: __len__, __contains__, __iter__. Iterators in Python using __iter__ as well as using the 'yield'. Writing an iterator for Binary Search Trees.
Read: Handouts from class AND try to run all the files provided yourself to understand the material.
April 12 : Heaps: Min/Max Heaps and their implementation. Priority Queues.
- Week 13 (April 17, 19)
April 17 : Graphs: An introduction: Konigsberg Bridges & Euler. Other graph problems.
April 19 : Graphs contd. State space graphs. Common graph algorithms: search: blind and informed searches. Searchign state-space graphs.
- Week 14 (April 24, 26)
April 24 : Graph Algorithms: Contd. Graph representations: Adjacency Matrix and Adjacency Lists. Implementing Adjacency lists in Python. Implementing Graph ADT in Python.
Assignment#8 is posted.
Due on Tuesday, May 2.
April 26 :
Heuristically informed graph searches: Hill Climbing, Best First, A*. Spanning Trees: Finding Minimum Spanning Trees: Kruskal's algorithm, Prim's algorithm. Greedy algorithms.
- Week 15 (May 1, 3)
May 1: Review Day. Please send topics you would to be reviewed in class today.
May 3: 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%
Links
Created on
January 19, 2007.