Data Structures

CS 23
Spring 1996

Instructor:

Thomas P. Kelliher
Hoyt 160
Office phone: 946-7290
Home phone: 946-3544 (emergencies only, please)
email: Send mail to kelliher AT DOMAIN abacus.westminster.edu
URL: http://www.westminster.edu/~kelliher
Office hours: MW 3:00--4:00pm. TR 1:00--2:30pm. Other times by appointment.

Class:

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

Objectives:

The objective of this class is to study some advanced problem solving techniques, such as recursion and data abstraction, and then to use them. We will be using these techniques to implement several of the ``classic'' data structures and algorithms (which will also be studied): stacks, queues, trees, tables, and graphs. We will learn how to analyze the efficiency of an algorithm and some techniques for improving the reliability of our programming, such as pre-conditions, post-conditions, and invariants.

Along the way, we'll learn a substantial amount about data abstraction in C++: classes, inheritance, polymorphism, virtual functions, etc. We'll also become quite familiar with Unix (all programming work will be done in Unix).

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. Sobell's A Practical Guide to the Unix System, 3rd edition, is an acceptable substitute. You should avoid any book which doesn't cover emacs (such as Hahn's A Student's Guide to Unix.
3. It might be helpful to have a book devoted to C++. Lippmann's C++ Primer is a very good book. This is not available at the College's bookstore. If there is sufficient interest, I will place an order. This book will be 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 approximately 1000 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. Still others may require you to demonstrate your work to me at a scheduled time. Late assignments will be accepted only by prior agreement.

2. Unannounced Quizzes --- Five short unannounced quizzes will be given throughout the semester. Each quiz will cover the reading assignment for the day it is given and will be worth 20 points.

3. Midterms --- There will be two in-class midterms, on March 15 and April 26. If you cannot take one of these midterms, please let me know as soon as possible. If you have a good reason, a make-up will be scheduled. This make-up must be scheduled to be taken within 48 hours of the in-class midterm. Each midterm will be worth 175 points.

4. Final --- The cumulative final will be worth 250 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 homework and exam solutions through my home page.

Attendance:

Attendance of classes is expected, but not required. It is your responsibility to catch up on missed class work. I keep a record of attendance for my own information, but this record has no bearing upon your grade.

Integrity:

Academic dishonesty will not be tolerated. Refer to the Handbook for Students and the Cheating Policy of the Department of Mathematics and Computer Science. Relevant points include:

1. Program/module plagiarism will be suspected if a programming assignment results in two or more non-trivial program/module solutions so similar that one can be converted to another by a mechanical transformation.

2. Cheating will be suspected if a student who was to complete an assignment cannot adequately explain the intricacy of their solution nor the techniques used to generate that solution.

A first offense will result in a grade of zero points for the assignment, Any subsequent offenses may result in a charge of academic dishonesty being filed with the Dean of the College, along with a grade of zero.

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 perform well on a midterm or final. The name of anyone with whom you collaborate on an assignment must be listed on the 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 during the second week of class. 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 some supplements from Lippmann.

Feb. 5: Introduction. pp. 1--20.

Feb. 7: Programming Issues, Loop Invariants. pp. 21--42.

Feb. 9: Unix, Introduction and Concepts. 1.3--1.6AL, 2.1--2.10AL, 2.12--2.14AL. Homework 1 out.

Feb. 12: Unix, File System and Utilities. 3.1--3.7AL, 3.9--3.14AL, 5.1.1--5.1.3AL, 5.2.2AL, 5.3.1AL, 5.4.4--5.4.5AL, 5.6AL.

Feb. 14: Unix, tcsh and emacs: 7.1AL, 9AL.

Feb. 16: Unix, Wrap-Up and Hands-On.

Feb. 19: Recursion, Concepts and Examples. pp. 49--93.

Feb. 21: Introduction to Abstract Data Types. pp. 101--120. Homework 1 in.

Feb. 23: Implementing ADTs in C++. pp. 120--135. Homework 2 out.

Feb. 26: Pointers and Dynamic Memory Allocation. pp. 141--152. 3.11--3.12 Lippmann (on reserve).

Feb. 28: Class Subtleties. 6.1--6.2 Lippmann.

Mar. 1: Linked Lists I. pp. 141--177.

Mar. 4: Linked Lists II. pp. 177--189.

Mar. 6: Advanced Recursion: Searching Techniques. pp. 203--218.

Mar. 8: Advanced Recursion: Language Recognition. pp. 218--238. Homework 2 in.

Mar. 11: Catch-Up Day.

Mar. 13: Midterm 1 Review.

Mar. 15: Midterm 1.