Data Structures

CS 23
Spring 1997

Instructor:

Thomas P. Kelliher
Hoyt 160
Office phone: 946-7290
Home phone: 946-3544
E-mail: Send mail to kelliher AT DOMAIN abacus.westminster.edu
URL: keystone.westminster.edu/~kelliher/
Office hours: MW 1:45--3:15pm. TR 1:00--2:00pm. Other times by appointment.

Class:

Hoyt 166
MWF 12:40--1:40pm

Objectives:

1. To learn, and become comfortable with, Unix and its programming tools.

2. To learn advanced data abstraction features of C++: classes, inheritance, polymorphism, virtual functions, etc.

3. To master advanced problem solving techniques such as recursion and data abstraction.

4. To study and make use of data structures such as linked lists, stacks, queues, trees, tables, and graphs

5. To study and compare algorithms such as sorts.

6. To learn how to compare algorithms using asymptotic analysis and to learn techniques for improving the reliability of programs, such as pre- and post-conditions and invariants.

Textbooks:

1. F. M. Carrano, Data Abstraction and Problem Solving with C++, Benjamin/Cummings, 1995.
2. P. W. Abrahams and B. R. Larson, Unix for the Impatient, 2nd edition, Addison Wesley, 1996.
3. S. B. Lippmann, C++ Primer, 2nd edition, Addison Wesley, 1991. Optional, but highly recommended. On reserve in Mack Library.

Suggested Materials:

A few 3.5" floppy diskettes. Preferably, these should be high density diskettes. You can use these to back-up your work. Ultimately, you are responsible for your files; within Unix, once a file has been removed, it's pretty much impossible to un-remove it.

Grading:

Grade Distribution

A = [90--100]
B = [80--90)
etc.

I use +/- grading sparingly.

Course Point Distribution

There will be 550 total points for the class. They will be distributed as follows:

1. Assignments --- Assignments will be of varying length, some written, some involving programming in the Unix lab. Some assignments will be collected in class on the due day. Others will be submitted electronically and will be due at a specific time on a specific day. Late assignments will be accepted only by prior agreement. 150 points.

2. Programming project --- A longer programming assignment, to be done in small (2--3) groups. You will have a few projects from which to choose. 100 points.

3. Midterms --- There will be two in-class midterms, on March 14 and April 11. If you cannot appear for a quiz, you must make arrangements with me beforehand (refer to the College's Student Regulations on absences from examinations). Each midterm will be worth 75 points.

4. Final --- The cumulative final will be worth 100 points.

5. Attendance, participation. 50 points.

No extra credit is available.

Course Handouts:

Most course handouts will be made available once in class. After that, they may be obtained from my personal home page on the World Wide Web (see the URL above). I also expect to distribute quiz solutions through my home page.

Attendance:

Attendance of classes is expected and is a part of your grade. It is your responsibility to catch up on missed class work.

Integrity:

Academic dishonesty will not be tolerated. Refer to the College's Student Regulations on academic integrity and the Cheating Policy of the Department of Mathematics and Computer Science.

That said, I realize that Computer Science is best learned in a collaborative environment. You should work together and enhance each others' understanding of the material. However, you are ultimately responsible for your own learning. By depending too strongly on someone else for help with an assignment, you most definitely jeopardize your ability to learn the material. You have my permission to collaborate only if you list the names of anyone with whom you collaborate on an assignment.

Unix and the Unix Lab:

Your programming assignments will be done using the GNU C++ ( g++) compiler under BSD/OS, an off-shoot of 4.4BSD Unix. Other Unix programming tools that you will be using include emacs (text editing) and gdb (source-level code debugger). There will be an intensive introduction to Unix at the beginning of the semester. Programming tools will be introduced as the need arises.

The Unix Lab, which is adjacent to the Math/CS Lab in the basement of Hoyt, is subject to Westminster's Policy for Responsible Use of Information Resources. Specifically:

1. The Lab exists to serve our students by providing a computing facility in support of their course work and other academic activities. These uses always have priority over recreational use of the facility.
2. You are responsible for doing your share in keeping the Lab a good place to work. To wit: do not distract or offend others, intentionally or unintentionally, in any way; do not leave trash around; recycle paper. In other words, be a good citizen.
3. Your login is for your personal use and no one else's. Do not give your password to anyone. If you need to share data with another student, ask us to set up a group for you.
4. We are all concerned that the hardware be treated properly. Follow any guidelines that are posted near the equipment or that are distributed electronically. Do not try to re-configure any of the equipment, especially the terminals. Do not put food or beverages where they could spill and damage the equipment. You are responsible for anything you damage. It is important to be gentle with the machines even when you are frustrated. Treat them as though you had paid for them and don't be afraid to insist that others do the same.
5. Another hardware issue is security. Don't let anyone who you don't know personally into the lab; you are responsible for the behavior of your guests in the lab. Be sure that doors are closed and locked when you leave.
6. Part of your responsibility as a user is to notify us of any hardware problems you encounter. You can contact us by sending mail to problems on keystone or the language machines. Never reboot or power down a machine except under drastic circumstances (water leaking thru the roof onto a machine or a machine burning, etc.). If such an emergency does occur, do what's right for your personal safety and if there is time power the machine off quickly, call 7777 to report the emergency, and contact me, either in the office or at home, regardless of the time.
7. As a user you must respect the privacy of others. Examples of privacy invasion include reading other people's mail, sending anonymous mail, using accounts other than your own, reading or deleting unprotected files, etc. Help novice users who lack the experience to properly protect their account. We consider data on the disk as real property. As such, finding a file in another user's directory that is readable to the world is like finding a house with the front door unlocked. It is wrong to read that file without invitation from the owner, just as it is wrong to go into a house with an unlocked door and watch TV.
8. Many of the ``goodies'' out on the network are fun, but not really crucial to your computer science career here. Game playing is acceptable, but has the lowest priority. If the lab is full and you are playing a game, it is your responsibility to recognize the situation and offer your seat to someone who comes in to work.
9. Finally, feel free to contact us with any computer related problems or questions which occur. Send mail to problems and mention the problem; be sure to include the name of the machine where it happened and how to illustrate or duplicate the problem. The trouble folks won't do homework for you.

Tentative Initial Schedule:

It is your responsibility to read the assigned material before class. What we do in class will not necessarily be what is in the reading.

Chapter readings with a suffix of ``AL'' are from Abrahams & Larson. All other readings are from Carrano, with supplements from Lippmann (``L'' suffix).

Feb. 5: Introduction and pre-test. Chapter 1. Appendix A.

Feb. 7: Program documentation: invariants, pre- and post-conditions. pp. 14--43. Homework 1 out.

Feb. 10: Unix I. Chapters 1AL and 2AL. Exercise.

Feb. 12: Unix II. Chapters 3AL and 5AL. Exercise.

Feb. 14: Unix III. Chapters 7AL and 9AL. Exercise. Homework 1 in. Homework 2 out.

Feb. 17: Review of recursion. Chapter 2.

Feb. 19: Introduction to abstract data types (ADTs). pp. 102--120.

Feb. 21: Implementing ADTs in C++ I. pp. 120--136. Chapter 5L. Homework 2 in.

Feb. 24: Implementing ADTs in C++ II. 6.1--6.2L. Exercise.

Feb. 26: Pointers and Dynamic Memory Allocation. pp. 141--153. 3.9--3.12L. Homework 3 out.

Feb. 28: Linked lists. pp. 153--190.

Mar. 3: Advanced recursion: searching techniques. pp. 203--218.

Mar. 5: Advanced recursion: language recognition. pp. 218--238. Homework 3 in. Homework 4 out.

Mar. 7: A list-based implementation of a stack. pp. 249--269.

Mar. 10: Using stacks. pp. 269--296.

Mar. 12: Using queues. Chapter 7. Homework 4 in.

Mar. 14: Midterm I.

Mar. 17: Advanced features of classes I. Chapter 8. Chapters 4--9L.

Mar. 19: Advanced features of classes II.

Mar. 21: Advanced features of classes III. Exercise. Initial project proposal due.

Mar. 31: Asymptotic analysis of algorithms. pp. 393--405.

Apr. 2: Sorting algorithms. pp. 405--432. Homework 5 out.

Apr. 4: Binary trees and their uses. pp. 439--468. Detailed project proposal due.

Apr. 7: Binary search trees and their uses. pp. 468--503

Apr. 9: Tables I. pp. 512--530. Homework 5 in.

Apr. 11: Midterm II.

Apr. 14: Tables II. pp. 530--549.

Apr. 16: Balanced search trees. pp. 556--591.

Apr. 18: Hashing. pp. 591--614.

Apr. 21: Graphs and their traversals. pp. 620--632.

Apr. 23: Graph applications. pp. 632--647.

Apr. 25: Remainder of semester devoted to ``reality check,'' project, and object-oriented design.

Apr. 28:

Apr. 30:

May 2: Project due.

May 5: Project presentations this week.

May 7:

May 9:

May 12: