Thomas P. Kelliher
Office phone: 946-7290
Home phone: 946-3544 (emergencies only, please)
email: Send mail to kelliher AT DOMAIN abacus.westminster.edu
Office hours: MW 3:00--4:00pm. TR 1:00--2:30pm. Other times by
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
F. M. Carrano, Data Abstraction and Problem Solving with C++,
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
- 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.
A = [90--100]
B = [80--90)
I use +/- grading sparingly.
Course Point Distribution
There will be approximately 1000 total points for the class. They will be
distributed as follows:
- 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
Late assignments will be accepted only by prior agreement.
- 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.
- 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
- 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 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
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:
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.
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
- 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
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.
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.
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.
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.
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
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.
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.
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.
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.