\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 M 1:00-2:15, T 9:00-4:00, other days by appointment}

\maketitle

\section{Who Should Take This Course}
This course is the second half of Adelphi's first-year programming
sequence. It assumes you have taken the first half, CSC 171, or the equivalent,
in either Scheme or C++; if your first programming class was at another
school or in other than those two languages, talk to me and we'll make
arrangements.

The course will also be of benefit
to people who know another programming language like Scheme, Pascal, C,
or Basic, and want to
learn Java and/or object-oriented programming (OOP). I expect the class
to include some
computer science majors, some computer science minors, and some people
here for just one or two courses. 

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.  Since some of you took CSC 171 in Scheme and others in C++,
we'll spend the first six weeks or so learning the syntax of Java,
the basics of object-oriented programming, and a little about graphics
and applets; we'll re-visit some techniques that you learned last
semester in another language, and see how they're done in Java.
Then we'll go on with more advanced techniques that we didn't have time
for in CSC 171.
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.  Examples
that some of you saw last semester are \emph{structures}, \emph{arrays},
\emph{lists}, and \emph{trees}.
\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 saw last semester,
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 Goodrich \& Tamassia's \emph{Data Structures and Algorithms in
Java}.  This book starts with a quick two-chapter introduction to the
Java language, and then takes a tour through a number of common data
structures, discussing the strong and weak points of each data structure,
its efficiency for various operations, and how to implement it.
\item Watts Humphrey's \emph{Introduction to the Personal Software Process},
which some of you used last semester.  I will not give specific reading
assignments in this book, but expect you to finish it on your own by the end
of the semester.  I'll expect each homework assignment you turn in to be
accompanied by various kinds of work logs, described in the book.
\item David Flanagan's \emph{Java in a Nutshell}.
This is not really a textbook, but a reference book: it doesn't explain things
in as much detail as a ``teach-yourself-Java'' book would, but it gives you
the information you need in a clear, concise package.  Since professional
computer scientists have to learn a new language every year or two, you should
start getting used to learning a language from this sort of book.
\item On-line documentation for Java's predefined classes.
\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 most of the
Goodrich \& Tamassia book, most of the Humphrey book, and scattered
parts of the Flanagan book this semester, so \emph{make time in your
weekly schedule} for about 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.
Any homework assignment turned in after midnight, May 9 (the second to
last day of class) will get a zero.  (This is so I have, perhaps, time to
grade them before the final exam.)

I also plan a few brief in-class quizzes (say,
15 minutes each), mostly on Java language issues.
Which aren't nearly as interesting
as designing data structures, but you \emph{do} need to know it in order to do
your assignments, and these quizzes seem the best way to make sure
everybody learns the language.
Each quiz will count for 2\% of your semester grade.  Quizzes cannot be made
up; if you're not there the day I give the quiz, you get a zero on it.

% These numeric grades will be converted to letter grades as follows:
% I'll draw a curve showing the distribution of numeric grades, and look
% for naturally-occurring ``clumps''.  For each clump, especially the
% top and bottom ones, I'll examine some exam and
% homework papers to decide what letter grade seems appropriate.  This
% method corrects for excessively hard or excessively easy assignments
% while not penalizing anybody for having genius classmates.

We'll also have a two-hour final exam on Monday, May 14,
weighted like one or two programming
assignments; more details to come.

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 an exam or assignment due 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.

Every program must be accompanied by a session log
(I'll show you how to do this)
showing how the program works on test cases.
Programs with inadequate or poorly-chosen test cases will lose points;
programs turned in with no test runs at all will lose
\emph{lots} of points.

Every program must be adequately and accurately commented.  BlueJ gives you some
sample comments when you create a new class, but these comments are presumably
not correct for your program, so I expect you to replace them with correct comments.
Each class should have at least a sentence indicating what it represents, and each
method should have at least a sentence indicating what it does.  Local and instance
variables may or may not need individual documentation, depending on how complicated
their purpose is.  Follow the ``javadoc'' guidelines.

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 concise 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.
 
\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 (ideally one with a C++ background and
one with a Scheme background), 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\%.
Ask the students who took my class last semester about this.

All work on quizzes and 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}
Section 1 of this class meets every Monday, Wednesday, and Friday from
10:00-10:50 AM, with a final exam Monday, May 14, from 10:30 AM to 12:30
PM.  Section 2 meets every Monday and Wednesday from 2:25-3:40 PM, with
a final exam Monday, May 14, from 3:30-5:30 PM.  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'', the letters ``GT'' precede page
numbers in Goodrich \& Tamassia's \emph{Data Structures and Algorithms
in Java}; the letters ``DF'' indicate the page numbers of optional
reading in David Flanagan's \emph{Java in a Nutshell}, and
the letters ``WH'' precede chapter numbers in Watts Humphrey's
\emph{Introduction to the Personal Software Process}.
I'll also direct you to on-line documentation on Java's built-in classes.

% 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!}

\subsection{Schedule for Section 1}
blah blah
\subsection{Schedule for Section 2}
blah blah
% \begin{tabbing}
% {\bf Date(s)} \=
% {\bf Assignment \hskip1.5em} \=
% {\bf Reading \hskip4em} \=
% {\bf Subject} \kill
% {\bf Date(s)} \>
% {\bf Assignment} \>
% {\bf Reading} \>
% {\hskip3em \bf Lecture Subject} \\
% %
% 25 Jan
% \> HW1 \> \> Using Java; arithmetic, variables, 
% \\* \> \> \> spaces, punctuation \\
% 27 Jan
% \> \> TiJ 5--66 \> Built-in types, variable declaration,
% \\* \> \> \> using methods; the String type \\
% 1 Feb
% \> HW1 due; HW2 \> TiJ 67--77, 86--90 \> Classes for compound data types;
% \\* \> \> \> instance variables; \texttt{javadoc} \\
% 3 Feb
% \> \> TiJ 77--86, 91--94 \> Defining methods and constructors;
% \\* \> \> \> \texttt{this}, \texttt{return}, \texttt{toString}, \texttt{equals} \\
% 4 Feb \> \> \> Deadline to add (Adelphi) classes \\
% 8 Feb
% \> HW2 due; HW3 \> TiJ 95--132 \> Built-in operators, types, and conditionals \\
% 10 Feb
% \> \> TiJ 147--178 \> More on constructors \\
% 15 Feb
% \> HW3 due; HW4 \> TiJ 217--226 \> Mixed data, interfaces,
% \\* \> \> \> abstract and concrete classes, class diagrams \\
% 17 Feb
% \> \> TiJ 226--249 \> Composition \emph{vs.} inheritance \\
% 18 Feb \> \> \> Deadline to drop (Adelphi) classes \\
% 22 Feb
% \> \> TiJ 251--278 \> More on mixed data and polymorphism \\
% 24 Feb
% \> HW4 due; HW5 \> TiJ 306--321 \> More on inheritance hierarchies \\
% 29 Feb
% \> \> review HtDP \> Self-referential data structures \\
% 2 Mar
% \> \> review HtDP \> More on self-referential data structures \\
% 7 Mar
% \> HW5 due \> \> Catch-up and review for midterm \\
% 9 Mar
% \> \> \> Midterm exam \\
% 13--19 Mar \> \> \> Spring Break \\
% 21 Mar
% \> HW6 \> \> Methods as parameters, sorta \\
% 23 Mar
% \> \> TiJ 278--305 \> Inner classes \\
% 28 Mar
% \> \> \> Visitor classes \\
% 30 Mar
% \> HW6 due; HW7 \> \> Visitor classes \\
% 4 Apr
% \> \> HtDP chaps. 25--26 \> Generative Recursion \\
% 6 Apr
% \> HW7 due; HW8 \> HtDP chaps. 27--28 \> Generative Recursion \\
% 11 Apr
% \> \> HtDP chaps. 29--30 \> Accumulative Recursion \\
% 13 Apr
% \> HW8 due; HW9 \> HtDP chaps. 31--32 \> Accumulative Recursion \\
% 17--23 Apr \> \> \> Snow Days, Passover, Easter \\
% 25 Apr
% \> \> TiJ 179--186 \> Arrays \\
% 27 Apr
% \> HW9 due; HW10 \> TiJ 132--146 \> Loops \\
% 2 May
% \> \> TiJ online chap. 8 \> Predefined Collection classes \\
% 4 May
% \> HW10 due; HW11 \> TiJ online chap. 13 \> Applets and event-driven programming \\
% 9 May
% \> \> TiJ online chap. 13 \> Applets and event-driven programming \\
% 11 May
% \> HW11 due \> \> Catch up and review for final \\
% 18 May \> \> \> Final Exam \\*
% \> \> \> section 1, 10:30-12:30 \\*
% \> \> \> section 2, 1:00-3:00 \\
% 21 May \> \> \> Commencement \\

% 28 lecture periods

% \end{tabbing}
\end{document}

HW1: write several expressions of varying complexity (types: int, double,
and String; various operators and built-in methods) in Java syntax.
HW2: write a class with instance variables, constructor, access methods,
and some more interesting methods
HW3: ditto, adding conditionals and multiple constructors
HW4: mixed data: CartesianPoint and ManhattanPoint, or animals and cages,
or something like that
HW5: something involving self-referential data structures
HW6: Java analogues to "map", "filter", etc.
HW7: Same thing (and more) with Visitors
HW8: Some generative-recursion assignment from HtDP
HW9: Some accumulative-recursion assignment from HtDP
HW10: Arrays and loops
HW11: An applet, using Swing classes and event-handling