\documentclass[12pt]{article}
% \usepackage{fullpage}
\advance \textheight by \topmargin
\advance \textwidth by \oddsidemargin
\topmargin 0pt
\oddsidemargin 0pt
\evensidemargin 0pt

\begin{document}

\title{Computer Science 172 \\
Introduction to Algorithms and Data Structures}

\author{Dr. Stephen Bloch \\
office 114 Alumn\ae\ Hall \\
phone 877-4483 \\
email \texttt{sbloch@adelphi.edu} \\
Web page \texttt{http://www.adelphi.edu/sbloch/} \\
Class Web page \texttt{http://www.adelphi.edu/sbloch/class/172/} \\
office hours 10:00-12:00 Monday \& Friday,
1:00-4:00 Tuesday \& Thursday}

\maketitle

\section{Who Should Take This Course}
This course is the second half of Adelphi's first-year programming
sequence for computer science majors and minors. It assumes you have
taken the first half, CSC 171, or the equivalent, in C++;
if your first programming class was at another
school or in other than C++, talk to me and we'll work it out.
If you've never taken a programming course at all, you should
take either CSC 160 (``A First Course in Computer Programming'') or
CSC 171 first; talk to me to choose between those.

If you want to learn how to use a computer (for word processing,
spreadsheets, databases, Web
browsing, email, etc.) and perhaps create your own Web page, but not
write full computer
programs yourself, you should probably take CSC 170, ``Introduction to
Computers and Their Applications'', instead. 

\section{Subject Matter}
This course is intended to follow CSC 171, which most of you took last
semester in C++.  We'll start by reviewing basic C++ syntax for a week
or so, then discuss software engineering, recursion, and some of the
principles of object-oriented programming.  This should take us into 
March.  Then we'll start looking at a variety of common data
structures, one by one: lists, stacks, queues, trees, \emph{etc.}

Throughout the semester, we'll focus on the paired concepts of
\emph{algorithm} and \emph{data structure}. 

\begin{description}
\item[algorithm]
A specification of how to accomplish a particular task.
Many books use the example of a recipe in a cookbook, which specifies
how to convert raw materials (eggs, flour, etc.) into a desired end
product (a batch of cookies); other examples would be the procedure
you go through to start your car, or to multiply two large numbers
together, or the quadratic formula.  Most books also define an algorithm
as a \emph{sequence} of operations, but the notion of sequence is not
essential: the quadratic formula, for example, doesn't look like a
sequence of operations at first glance, and in fact it can be evaluated
in several different orders with no impact whatsoever on the result.

An algorithm is not quite the same thing as a program, although every
program has one or more algorithms at its heart.
An algorithm is more or less independent of the \emph{language} in
which it is expressed: one can write essentially the same algorithm in
Java, Pascal, C++, Visual Basic, and Scheme, although they will all look
cosmetically different (with different sequences of semicolons, commas,
braces, keywords, etc).

\item[data structure]
A specification of how to represent a particular kind of information
in a computer.  Most languages provide several ``primitive'' data
types, e.g. integers, characters, strings, functions, \emph{etc.}
But if the information you need to manipulate isn't exactly one of those
kinds of information, you need to figure out how to represent it.  Most
languages provide several constructs to help you build new data
structures from old ones, typically \emph{arrays}, \emph{structs},
\emph{inheritance}, and \emph{polymorphism}.
\end{description}

Data structures and algorithms are usually mentioned in the same breath,
because if you come up with a wonderful data structure to hold
information, you still need to supply algorithms for accessing and
manipulating the information.  Furthermore, as we'll see,
frequently the ``shape'' of a method corresponds to the ``shape'' of the
data on which it operates, so it makes sense to design a data structure
and algorithms for it simultaneously.

This principle is put into practice in the 
methodology of programming called ``Object-Oriented Programming'', or OOP
for short.  In an object-oriented program, not only are the data structure
and its algorithms designed simultaneously, but the program code to describe
them is tightly interwoven.  You'll see what this means as the semester
goes on.

\section{Texts}
This semester we'll use several ``textbooks'': 

\begin{itemize}
\item \emph{Data Abstraction and Problem Solving with C++: Walls and
Mirrors}, 3rd edition, by Carrano and Pritchard.
Most of the reading assignments, and some of the homework, will be from
this book.
\item Watts Humphrey's \emph{Introduction to the Personal Software Process}.
Using exercises in this book, you'll study your own programming style
and learn to predict how long you'll take to accomplish a specified
programming task, as well as to budget your time so you finish each
program without staying up until 3 AM the night before it's due.
I won't give specific reading
assignments in this book, but expect you to finish it on your own by the end
of the semester.  Each homework assignment you turn in should be
accompanied by various work logs, described in the book.
\item Bjarne Stroustrup's \emph{The C++ Programming Language}.
This \textbf{optional} book is a reference, not a textbook: it doesn't explain things
in as much detail as a ``teach-yourself-C++'' book would, but gives you
the information you need.  Since professional
computer scientists have to learn a new language every year or two, you should
get used to learning a language from this sort of book.
I've ordered the third edition as an ``optional'' textbook for the
course; if you already have a previous edition, you can use it for most
of the topics we'll cover.  
\end{itemize}

The reading assignments are an important part of the course.  If you're
going to pay \$50 or more for a textbook, you might as well get your
money's worth by \emph{reading} it.  We'll go through about 10 chapters
of the Carrano-Pritchard book, most of the Humphrey book, and
scattered parts of the Stroustrup book this semester, so
\emph{make time in your weekly schedule} for at least fifty pages a
week.

\textbf{You are responsible for everything
in the reading assignments, whether or not I discuss it in a lecture.}
You are also responsible for checking my class Web page % and the WebBoard
at least once a week or so for assignments, corrections to assignments,
solutions to assignments, \emph{etc.}.

\section{Grading}
I expect to give seven or eight programming assignments, one every week or two.
Most assignments are to be turned in by email, and will be considered late
if the time stamp on the email is after midnight on the assigned due
date.  Assignments turned in up to a day late lose 10\% credit; those up
to two days late lose 20\% credit; \emph{etc.}  Any homework assignment
turned in more than ten days late will get a zero.  So if you have a
choice between turning in an incomplete program today and a better one
tomorrow, you should turn it in late only if you think the extra day
will allow you to improve it by more than 10\%.
Any homework assignment turned in after midnight, Friday, May 10 (the 
last day of class) will get a zero.  (This is so I have, perhaps, time to
grade them before the final exam.)

We'll have a two-hour final exam, weighted the same
as a programming assignment.  It will include material from the whole
semester, but concentrate on the most recent topics (those on which you
haven't done a homework assignment).

There will also be a ``brownie points''
score, weighted the same as a programming assignment.  The ``brownie
points'' score is my purely subjective opinion of how seriously you're
taking the course.  You gain brownie points by asking good questions in
class, coming to my (or the tutors') office hours when you have a problem,
\emph{etc.}  You lose brownie points by cheating, by being confused and
not doing anything about it, and by doing anything else that annoys the
professor.

The final exam must be taken at the scheduled time, unless arranged in advance
or prevented by a documented medical or family emergency.  If you have
three or more exams scheduled on the same date, or
a religious holiday that conflicts with the exam date,
please notify me in writing within the first two
weeks of the semester in order to receive due consideration.
% (and I'd
% prefer it if you let me know earlier --- you should know within the
% first week of class when all your exams are).
Exams not taken without one of
the above excuses will be recorded with a grade of 0.


\section{Program standards}
Every program must contain, in the first few lines,
a comment indicating the name(s)
of the student(s) working on it, the course number (CSC 172),
and which assignment it is.
Programs not containing
this information, clearly visible, will get a zero.
If you're turning in homework by e-mail, please put this same
information in the Subject: line as well, so it's easier for me to
file my e-mail correctly.

A program that hasn't been adequately tested is worthless.  I expect you
to choose, and write down, a good selection of test cases (along with
the ``correct'' result of each one) for every function \emph{before}
you write its body.
Every program must be accompanied by a session log
showing how the program works on test cases.
Programs with inadequate or poorly-chosen test cases will lose points.

Every program must be adequately and accurately commented.
Ideally, most of your code
should be so easy to read that it doesn't need comments, but if there
are non-obvious restrictions on the use of a particular variable or
function, or non-obvious tricks in your algorithm, explain these.

Having done my share of programming, I know that sometimes you hit a
brick wall and cannot get the thing to work for love or money.  If this
happens, turn in the program together with a description of
how the program fails, what you've tried in your attempts to fix it,
and how those attempts didn't succeed.  You won't get full credit, but
if I'm convinced that you're working on it diligently, you'll get some
partial credit.  Note that ``how the program fails'' does \emph{not}
mean saying ``I got an error message'': you need to tell me \emph{which}
error message you got, \emph{when} you saw it, and \emph{what} you think
the error message means.  Similarly, if the program fails by producing
wrong answers, you need to tell me \emph{when} it produces wrong answers
(are they \emph{all} wrong, or just in a few cases?), \emph{how} they
are wrong (\emph{e.g.} are all the numbers consistently higher than you
expected, are they the negatives of the correct answers, or are they
all over the place with no apparent pattern?), and your speculations on
\emph{how} such an error might have arisen.  I'm requiring all this not
because I'm mean and horrible, but because by the time you've written
all this down, you may have enough information to actually \emph{fix}
the problem, which is much better than turning it in incomplete.

I also expect you to keep track of the time you spend on various
aspects of programming, how many and what kinds of defects you encounter,
\emph{etc.}  For each assignment, I'll tell you which tracking information
is required.  The easiest way to turn in this information is through a
collection of on-line PSP forms, which I'll show you how to use.  Indeed,
I recommend that while you're programming, you have a Web browser running
the forms in the background, so you can easily record each defect and
each block of time before you forget about it.  Failure to turn in this
tracking information will lower your grade for that assignment.

% Programs are not abstract works of art,
% they are supposed to run and solve real problems.  So if I get a program
% that doesn't compile or run, or a program that has little or nothing to do
% with the problem I assigned, I will give it a zero, no matter how much
% time you put into it.  Don't bother turning in a program you haven't
% tested yourself.
 
Programs will be graded not only on producing correct answers (although
that's obviously a requirement), but on how they're written --- the
topics discussed in the second half of chapter 1 of the ``Walls and
Mirrors'' textbook.  One of these criteria is ``modifiability'',
and to drive home its importance, I'll often
\textbf{change the assignment slightly on the day that it's due}.
When you read an assignment, you should immediately start thinking
``how is Dr. Bloch likely to change this at the last minute?'' and
write the program in such a way that you can respond to such changes
easily.  If it takes you more than an hour to handle my last-minute
change, you didn't design the program well.

\section{Ethics}
Most homework assignments in this course involve writing, testing, and
debugging a program.  For most of these assignments, I would prefer that
you work in teams of two students, switching teams from one assignment
to the next; for other assignments, I may ask you to work individually.

When I say
``teams of two students'', I don't mean ``you write the first half of the
assignment, and I'll write the second half''; I want \emph{both} students
working \emph{together} on \emph{all} of the assignment, using the techniques
of Pair Programming: two people using one workstation, with one typing and
the other ``looking over the first one's shoulder''.  If you haven't
encountered this approach before, I'll point you to a good article about it.

It's hard to define what constitutes ``cheating'' in this sort of
course.  Students are encouraged to help one another with mechanical and
linguistic difficulties (``how do I save this file?'', ``how do you declare
a static instance variable?'', \emph{etc.}), regardless of whether
they're on the same team, but designing, coding, testing, and debugging 
should be done by team members.  It's remarkably easy for a professor to
notice when three different teams have turned in nearly-identical
programs; if that happens, I'll grade it once and divide the credit
among the three, so the best any of them can hope for is 33\%.

All work on the final exam must be entirely the work of the one
person whose name is at the top of the page.  If I have evidence that
one student copied from another on an exam, \emph{both} students will be
penalized; see above.

% \pagebreak

\section{Schedule}
This class meets every Monday and Wednesday from 2:25-3:40 PM in the
Gallagher lab of Swirbul Library.
Our final exam will be from 3:30--5:30 PM, in the same room, on
Monday, May 13.  If you have a problem
with these scheduled dates and times, let me know \emph{at least two
weeks in advance} so we can make suitable arrangements.

All dates in the following schedule are tentative, except those fixed
by the University; if some topic listed here as taking one lecture in
fact takes two lectures to cover adequately, or \emph{vice versa},
the schedule will shift.

In the column marked ``Reading'', all page numbers are in the ``Walls
and Mirrors'' book unless stated otherwise.  Remember, I also expect
you to read through most of the Humphrey book, and look up individual
language topics in the Stroustrup book, as necessary.

% In no case will an assignment be due earlier than indicated in the
% following schedule, but some may be due later; this will be announced
% in class a reasonable time in advance.  I'll try to keep an updated
% version of this schedule available online.  

I expect you to have read the reading assignments 
\emph{before} the lecture that deals with that topic.  
This way I can
concentrate my time on answering questions and clarifying subtle or
difficult points in the textbook, rather than on reading the textbook
to you, which will bore both of us.  \textbf{Please read ahead!}

When I say ``read'' above, I
mean an active process, involving not only the textbook but
pencil, scratch paper, and a notebook for writing down key points.
Finally, and perhaps most importantly, you'll need a computer for trying
out the new ideas you find in your reading.  Just as you cannot learn
to drive a car or to cook just by reading about it, you cannot
learn about programming just by reading about it.  In short,
\emph{every} time you read about a new programming idea, \emph{try it!}

\end{document}

HW1: write a program that takes in a 0-terminated sequence of
numbers and computes the average of the numbers.  At the last minute,
change the assignment so it's (-1)-terminated.
Also read some of my "adages" and write about your reaction to them.
HW2: a bunch of recursive functions, including wild-card matching.
At the last minute, change the I/O behavior.
HW3: A class with some instance variables, constructors, access methods,
etc. (like "Instrument" last year).
At the last minute, add another kind of Instrument.
HW4: Something polymorphic (like the music store), with a polymorphic
implementation of a linked list.
HW5: Replace the polymorphic implementation with a null-terminated
implementation.
HW6: C++ analogues to "map", "filter", etc. in both polymorphic and
null-terminated implementations.  Some more recursion problems?
Iterators and Visitors?
HW7: Something involving stacks and queues: a discrete-event simulation?
HW8: Comparison of a number of sorting and searching algorithms