CS 206 Data Structures; Course Materials from Spring 2003

Bryn Mawr College
CS 206: Data Structures
Spring 2003
Course Materials

Information

Texts

Important Dates

Assignments

Lectures

Grading

Links

General Information

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

Teaching Assistant: Ioana Butoi
E-Mail: ibutoi@brynmawr.edu
TA Lab Hours: Mondays 9:00 p.m. to 11:00 p.m. in Room 232 except on February 24 (10:00 p.m. to midmight)

Lecture Hours: Tuesdays & Thursdays, 1:00 p.m. to 2:30 p.m.
Laboratory Hours: Wednesdays 2:00 p.m. to 4:00 p.m.
Room: Park 232

Laboratories:

PC Lab Room 232 (Science Building)

Texts & Software

Data Structures and Abstractions with Java, by Frank M. Carrano and Walter Savitch, Prentice Hall, 2003.

In addition, you will need a good Java reference. Here are some recommendations:
Java in a Nutshell, David Flanagan, O'Reilly Publishers.
Java Precisely, Peter Sestoft, MIT Press 2002
Or, your old CS110 text will do.
Software: We will be using the Java programming language for all laboratory exercises. Software for writing and running Java programs is available on Windows PCs in Room 232 as CodeWarrior 8 and also on other computers on the campus. You may also use the Java SDK installed on the Computer Science Linux cluster in Room 232. The Linux server can be accessed via a terminal session from any networked computer on campus via a SSH client.

Important Dates

January 21: First lecture (See below)
February 20: Exam 1
April 3: Exam 2
May 1: Last lecture
May 1: Exam 3 (Take Home Exam)

Assignments

Unless explicitly specified, all assignments are due at the beginning of the class on the date due. No credit will be awarded for any late work.

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

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

*/

(Due on Thursday, January 30) Write a Java applet that implements the exercise on Page 60 of the Java Reference handout. Do the exercise for random lines in random colors only. Draw at least 5000 lines.
Exercise: (Due on Tuesday, February 4) Click here for details.
Exercise: (Due on Thursday, February 6) Click here for details.
Exercise: (Due on Tuesday, February 11) Click here for details.
Exercise: (Due on Tuesday, February 13) Click here for details.
Exercise: (Due on Tuesday, February 25) Click here for deatils.
Exercise: (Due on Thursday, February 27) Click here for deatils.
Exercise: (Due on Tuesday, March 4) Click here for deatils
Exercise: (Due on Thursday, March 6): Click here for details.
Exercise: (Due on Thursday, March 20): Click here for details.
Exercise: (Due on Tuessday, March 25): Click here for details.
Exercise: (Due on Thursday, March 27): Click here for details.
Exercise: (Due on Tuesday, April 1): Click here for details.
Exercise: (Due on Tuesday, April 8, 15, 22): Click here for details.
Exercise: (Due on Tuesday, April 10, 15, 22): Click here for details.
Exercise: (Due on Thursday, April 17): Click here for details.
Exercise: (Due on Thursday, April 24): Click here for details.
Exercise: (Due on Tuesday, April 29): Click here for details.

Lectures

Week 1 (January 21, 23) I will be away all day on tuesday and wednesday afternoon through sunday so there will be no formal class meetings this week. However, send me an e-mail and make an appointment to see me this week to discuss your enrollment in this class.
January 21: Class cancelled.
January 23: Class cancelled.
Read:
Week 2 (January 28, 30)
January 28: Introduction to the course. A review of Java: Basic statements, applets, structure and life cycle of an applet.
Read: Skim over the Java Reference handout. Read Appendix A from Carrano & Savitch. Review Applet Examples 1 through 10 from CS110.
Exercise: (Due on Thursday, January 30) Write a Java applet that implements the exercise on Page 60 of the Java Reference handout. Do the exercise for random lines in random colors only. Draw at least 5000 lines.
January 30: Java Review, contd: Commonly used Java API's, GUI elements, methods and parameter passing.
Read: Finish reading the Java Reference handout. Read Appendix A from Carrano & Savitch. Review Applet Examples 11-14 from CS110.
Exercise: (Due on Tuesday, February 4) Click here for details.
Week 3 (February 4, 6)
February 4: Java Review, contd.: Characters, strings and arrays. Layout managers.
Read: Finish Appendix A, Review Applet Examples 15-18 from CS110.
Exercise: (Due on Thursday, February 6) Click here for details.
February 6: Object-oriented programming in Java. Objects, classes, methods, constructors, difference between primitive type variables and reference variables.
Read: Chaper 1 from Carrano & Savitch.
Exercise: (Due on Tuesday, February 11) Click here for details.
Week 4 (February 11, 13)
February 11: Building classes from other classes: composition, adapters, inheritance. Overloading, overriding, and polymorphism. Static variables and more information on Java classes.
Read: Chapter 2 from Carrano & Savitch.
Exercise: (Due on Tuesday, February 13) Click here for details.
February 13: Method signatures, abstract classes and methods. Interfaces. The array as a data structure. The Java Collection Framework.
Read: Chaper 3 from Carrano & Savitch.
Exercise: Complete Exercise#5.
Week 5 (February 18, 20)
February 18: Class cancelled due to snow day!
Exercise: (Due on Tuesday, February 25) Click here for deatils.
February 20: Exam 1 is today.
Read: Chapter 4 from Carrano and Savitch (as self study). We will discuss it in class on Tuesday, Feb. 25th.
Week 6 (February 25, 27)
February 25: ADTs and Data Structures. Overview of the Java Collections Framework. Linear, hierarchical and network structures. The List ADT. Data Structures for implementing the List ADT.
Exercise: (Due on Thursday, February 27) Click here for deatils.
Read: Chapters 4 & 5 from Carrano & Savitch.
February 27: Implementing the ListADT using dynamic arrays and linked lists. Java inner classes.
Read: Chapter 6 from Carrano & Savitch.
Exercise: (Due on Tuesday, March 4) Click here for deatils.
Week 7 (March 4, 6)
March 4: The LIST ADT: Linked implementations.
Exercise: (Due on Thursday, March 6): Click here for details.
March 6: Linked representations of Lists. Discussion on primes.
Read: Chapter 6 from Carrano & Savitch. Also find out information about creating Java applications, and reading and writing from/to files. You will find some of this information in Appendix C of Carrano & Savitch.
Exercise: No exercise assigned today. Enjoy the break!!
Week 8 (March 11, 13)
No class, Spring Break!!
Week 9 (March 18, 20)
March 18: Comparison of list implementations. Analyzing complexity of operations: Big-Oh notation. Exceptions and exception handling.
Read: Chapters 6&9 from Carrano & Savitch as well as Appendix B.
Exercise: (Due on Thursday, March 20): Click here for details.
March 20: Exceptions and exception handling. Understanding the exception mechanism in Java. Defining your own exceptions. Defining exceptions for the ListADT.
Read: Appendix B from Carrano & Savitch.
Exercise: (Due on Tuessday, March 25): Click here for details.
Week 10 (March 25, 27)
March 25: Iterators in Java. Implementation choices for iterators. Doing File I/O in Java.
Read: Chapters 7 and 8 from Carrano & Savitch.
Exercise: (Due on Tuessday, March 25): Click here for details.
March 27: The Stack and Queue ADT and their implementation and applications.
Read: Chapters 20, 21, 22, and 23 from Carrano and Savitch.
Exercise: (Due on Tuesday, April 1): Click here for details.
Week 11 (Apri1 1, 3)
April 1: The Queue ADT and the Dequeue ADTs. Review for Exam 2.
Read: Chapters 22 & 23 from Carrano & Savitch.
Exercise: (Due on Tuesday, April 8, 15, 22): Click here for details.
April 3: Exam 2 is today.
Week 12 (Apri1 8, 10)
April 8: Searching: Linear and binary searches.
Read: Chapter 16 from Carrano & Savitch
Exercise: (Due on Tuesday, April 10, 15, 22): Click here for details.
April 10: More on binary search and its implementation. Trees: Terminology & traversal.
Read: Chapter 24 from Carrano & Savitch
Exercise: (Due on Tuesday, April 15): Click here for details.
Week 13 (Apri1 15, 17) Happy Birthday Ioana!
April 15: Review of Exam 2. Trees, contd. Binary Trees, Binary Search Trees. Implementing binary search trees: interfaces, classes, etc.
TA Session: Ioana will not hold TA hours today.
Read: Chapters 25 & 26 from Carrano & Savitch.
Exercise: (Due on Tuesday, April 17): Click here for details.
April 17: Trees, contd. Binary Trees, Binary Search Trees. Implementing binary search trees: interfaces, classes, etc.
Read: Chapters 25 & 26 from Carrano & Savitch.
Exercise: (Due on Thursday, April 24): Click here for details.
Week 14 (Apri1 22, 24)
April 22: Balanced Binary Search Trees: AVL Trees, 2-3 Trees, 2-4 Trees, Red-Black Trees. Heaps.
Read: Chapters 27 & 28 from Carrano & Savitch.
Exercise: (Due on Tuesday, April 29): Click here for details.
April 24: MaxHeaps, MinHeaps, Prioroty Queues. Implementing Heaps.
Read: Chapter 28 from Carrano & Savitch.
Week 15 (April 29, May 1)
April 29: Graphs: Terminology and applications. Data Structures for implementing graphs. Graph Algorothms.
Read: Chapters 29 & 30 from Carrano & Savitch.
May 1: Wrap up! Exam 3 is today.
Read:

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%
Labs: 55%
Total: 100%