Thomas P. Kelliher
Office phone: 946-7290
Home phone: 946-3544
E-mail: Send mail to kelliher AT DOMAIN abacus.westminster.edu
Office hours: MW 1:45--3:15pm. TR 1:00--2:00pm. Other times by
- To learn, and become comfortable with, Unix and its programming tools.
- To learn advanced data abstraction features of C++: classes,
inheritance, polymorphism, virtual functions, etc.
- To master advanced problem solving techniques such as recursion and
- To study and make use of data structures such as linked lists,
stacks, queues, trees, tables, and graphs
- To study and compare algorithms such as sorts.
- 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.
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.
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.
A = [90--100]
B = [80--90)
I use +/- grading sparingly.
Course Point Distribution
There will be 550 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.
Late assignments will be accepted only by prior agreement.
- 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.
- 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.
- Final --- The cumulative final will be worth 100 points.
- 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 of classes is expected and is a part of your grade. It
is your responsibility to catch up on missed class work.
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
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 supplements from Lippmann (``L''
- 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.
- 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: