Bryn Mawr College
CS
206: Data Structures
Fall 1999
Course Materials
General Information
Instructor: Deepak Kumar, 248 Park Hall, 526-7485
E-Mail:
dkumar@brynmawr.edu
WWW: http://mainline.brynmawr.edu/~dkumar
Lecture Hours: Tuesdays & Thursdays, 10:00 a.m. to 11:30 a.m.
Room: Park 338
Laboratories:
- CS Mac Bay, Guild Hall (Computing Center)
- Computational Modeling Lab, Room 10, Park Hall (Science Building)
- X Terminal Lab, Room 247 Park Hall (Science Building)
Texts & Software
- Data Structures, Algorithms, and Applications in C++, by Sartaj
Sahni, WCB McGraw Hill 1998.
- C++ How To Program (Second Edition), by H. M. Deitel & P.
J. Deitel, Prentice Hall, 1998.
- The Mac & I: A Laboratory Manual for Introduction to Computer
Science, by Clare Congdon & Deepak Kumar, Bryn Mawr College, Fall
1999.
- CodeWarrior Pro 5 for Macintosh, Software by Metrowerks, 1999.
This software is installed in all the Laboratories mentioned above.
- SUN C++ & GNU C++ compilers. These are available on the
server mainline.brynmawr.edu
Important Dates
August 31 : First lecture
September 28 : Exam 1
November 2 : Exam 2
December 2: Last lecture
December 7 : Exam 3
Assignments
- 8/31/99: Assignment#1
(Due on Tue, September
7):
Write C++ programs for all parts of the exercises
3.30, page 215, and 3.41, page 217 of Dietel & Dietel.
- Assignment#2 (Due on Thu, September 23): Write C++ programs
for exercise 6.16, page 415, of Dietel & Dietel. Only do the first
part (i.e., leave out the "ambitious part").
- Assignment#3 (Due on Thursday, October 7): Extend the List implementation
provided in class to have a copy constructor, an automatic list growing
and shrinking facility, and a member function that reverses the list in
place. See class handout for more details.
- Assignment#4 (Due on Tuesday, October 19): Implement the basic
List operations to use the Linked representation as discussed in class.
Do the same exercise as Assignment#3. Part 3 (about growing and shrinking)
does not apply here.
- Assignment#5 (Due on Thursday, October 28): Implement the Stack
class using a linked representation. Demonstrate its correctness by writing
a postfix calculator as discussed in class.
- Assignment#6 (Due on Tuesday, November 16): Doing empirical
analyses on heights of binary search trees. See details below.
- Assignment#7 (Due on December 2): Performance comparison of
various sorting algorithms. See details below.
Lectures
- Week 1
August 31: First Meeting. Overview
of the course. Review of C++ begins.
Reading: Review
Chapters 1 through 4 from Deitel & Deitel.
Assignment#1
(Due on Tue, September 7): Write C++ programs for all parts of the
exercises 3.30, page 215, and 3.41, page 217 of Dietel & Dietel.
September 2: C++ Review: Functions, formal, actual,
value, reference parameters.
- Week 2 (September 7, 9)
September 7: C++
Review: Functions: constant reference parameters, function overloading,
template functions, array parameters, recursion.
Reading:
Review Chapters 1 through 4 from Deitel & Deitel. Section 1.2 and 1.2
from Sahni.
September 9: By now you should all have
atleast logged in in your mainline accounts.
Pointers in
C++, the & and * operators, pointer arithmetic, arrays and pointers.
Dynamic memory allocation using new. Pointers to functions and their use.
Reading: Chapter 5 from Deitel & Deitel and Chapter
1 from Sahni.
- Week 3 (September 14, 16)
September 14: Pointers
to functions and their use. Arrays of pointers to functions. An introduction
to Data Abstraction and Object-Oriented Programming. OOP in C++(Some Basics):
Classes, members, member fuctions, public and private attributes.
Reading: Chapter 6 from Deitel & Deitel.
Assignment#2
(Due on Thu, September 23): Write C++ programs for exercise 6.16, page
415, of Dietel & Dietel. Only do the first part (i.e., leave out the
"ambitious part").
September 16: Data Abstraction
in C++.
- Week 4 (September 21, 23)
Septmeber 21:
Data Abstraction in C++. Copy constructors, const member functions, using
the this pointer, friends, operator overloading. Using gnu-make and makefiles.
Reading: Chapters 7 & 8 from Deitel & Deitel.
September 23: Project#2 is due today. Review of C++
facilities for data abstraction. Overview of Data Structures: sets, sequential,
hierarchical, network.
- Week 5 (September 28, 30)
September 28:
Exam 1 is today.
September
30: Review of Exam 1. The Linear List data structure.
Reading:
Sections 3.1..3.3 from Sahni.
- Week 6 (October 5, 7)
October 5: Linear
List implementations.
Assignment#3 (Due on Thursday,
October 7): Extend the List implementation provided in class to have
a copy constructor, an automatic list growing and shrinking facility, and
a member function that reverses the list in place. See class handout for
more details.
October 7:
- Week 7 (October 12, 14)
October 12: No class, Fall Break!
October
14: Linked List representation.
Assignment#4 (Due
on Tuesday, October 19): Implement the basic List operations to use
the Linked representation as discussed in class. Do the same exercise as
Assignment#3. Part 3 (about growing and shrinking) does not apply here.
- Week 8 (October 19, 21)
October 19: Postfix
notation (RPN Notation). Stacks: Array Representation using cooperative
program development.
Read Chapter 5 from Sahni.
October 21:
I will be out of town this friday
(10/22) giving a talk at MindFest.
- Week 9 (October 26, 28)
October 26: Queues:
Array and linked representation. Converting infix expressions to postfix.
Read Chapter 6 from Sahni.
October 28:
Alternative linear structures and representations: Circular lists, doubly-linked
lists, etc.
- Week 10 (November 2, 4)
November 2: Exam 2 is today.
November
4: Review of Exam 2. Introduction to trees.
- Week 11 (November 9, 11)
November 9: Binary
Trees. Linked Implementation. Read Chapter 9 from Sahni.
November
11:
Exercise (Due on tuesday November 16): Use
the Binary Search Tree implementation given in class to perform the following
experiment: Insert several random elements into the tree. Measure the height
of the resulting tree. Do this several times varying the number of elements
inserted from 100, 500, 1000, 2000, 3000, 4000, 5000, 10000.For each value
of N, the number of elements, you may want to repeat the run several times
to get the average height of the tree for that many elements. Plot the
data you collect against log2(n) (that is, log of n to the base 2). Based
on the data you collected, can you estimate a relationship between the
empirical height of the tree and and the idealized estimate log2(n)?
- Week 12 (November 16, 18)
November 16:
Sorting: Selection Sort, Insertion Sort, Quicksort. Sorting Arrays vs sorting
Linked Lists. Performance measurement.
Exercise:
This assignment will build up as we discuss more sorting techniques. Create
a library of array sorting functions, each implementing a specific sorting
algorithm. Also, simultaneously, extend your List class (linked representation)
to include methods to sort using each of the algorithms. Then write a main
program that helps you time the performance of each of the algorithms.
The object of the exercise is to do a comparison of all the algorithms
(use varying data sizes ranging from 50, 100, 200, 300, 400, 500, 1000,
2000, 3000, 5000, 10000, etc. elements). Use the C++ timing functions (see
time.h) for getting the times for each run. Again, perform several runs
for each data size and average the resulting times to use in plots.
Try and implement Selection, Insertion, and Quick Sort by thursday
(11/18). On thursday, we will do more sorting techniques.
November
18: Insertion Sort: Linked Version. Quick Sort. Heaps and heap Sort.
- Week 13 (November 23, 25)
November 23:
Heaps and HeapSort.
November 25: No
class, Thanksgiving Break!
- Week 14 (November 30, December 2)
November
30: Graphs: Basic defintions, matrix representation, linked representation,
overview of graph algorthms.
December 2: Graph Searching,
search trees, game playing and game trees.
- Week 15 (December 7)
December 7: Exam
3 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: 15%
Exam 2: 15%
Exam 3: 15%
Programming Assignments: 55%
Total: 100%
Links
Created by dkumar@brynmawr.edu
on August 25, 1999.