\documentstyle[12pt,fullpage,psfig]{article}
\begin{document}

\addtolength{\topmargin}{-0.5in} 
\addtolength{\textheight}{+0.5in} 

\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
\vspace{1em}
 
\fbox{\parbox{5.7in}{
\begin{center}
{\Large 
{CS 15-299 \hfill Spring 1998}
}
\begin{tabular}{l@{\hspace{.3in}}l}
\multicolumn{2}{c}{Main Lecture: TR 10:30-11:50 in 2210 Dougherty Hall}\\
\multicolumn{2}{c}{Section A: Mon 10:30-11:20 in 203 Student Center}\\
\multicolumn{2}{c}{Section B: Mon 11:30-12:20 in 203 Student Center}\\
\multicolumn{2}{c}{Section C: Mon 12:30-1:20 in 203 Student Center}\\
\multicolumn{2}{c}{Section D: Mon 1:30-2:20 in 203 Student Center}\\\\
Professor Maggs & 4123 Wean,  268-7654,  bmm+@cs\\
TA (A) Rob Miller & 5117 Wean,  268-3046,  rcm+@cs\\
TA (B) Adam Kalai & 7113 Wean,  268-7123,  akalai+@cs\\
TA (C \& D) Hal Burch & 7110 Wean Hall, 268-7670, hburch+@cs \\
TA Doug Beeferman & 5101 Wean, 268-8139, dougb+@cs\\

\\
Secretary: Dorothy Zaborowski & 4116 Wean,  268-3779,  daz+@cs\\
\\
\end{tabular}

\fbox{{\large http://www.cs.cmu.edu/afs/cs/academic/class/15299/
}}

\end{center}

}}

\vspace{.1in}

\fbox{\parbox{5.7in}{

{\small

{\bf \begin{center} \Large Ten Powerful Ideas \end{center}}

\begin{description}
\begin{description}



\item[Counting:] Learn how to count without counting. 

\item[Induction:] Recognize it in all its guises. 

\item[Exemplification:] Find a sense in which you can try out a problem
or solution on small examples.

\item[Abstraction:] Abstract away the inessential features of a problem. 

\item[Modularity:] Decompose a complex problem into simpler subproblems.

\item[Representation:] Understand the relationships between different
possible representations of the same information or idea.

\item[Refinement:] The best solutions come from a process of repeatedly
refining and inventing alternative solutions.

\item[Toolbox:] Build up your vocabulary of abstract structures.

\item[Optimization:] Understand which improvements are worth it.

\item[Randomization:] Flipping  a coin can be surprisingly helpful!

\end{description}
\end{description}
}
}}
\pagebreak

\begin{center}
{\bf \huge Course Schedule}\\
\vspace{.5em}
{\bf CS 15-299 \hfill Spring 1998}
\vspace{3em}

\begin{tabular}{|c|cc||l|}
\hline \hline
Lecture	&	Date & Day &	Topic \\ \hline				  
1  & 13-Jan & T  & Introduction\\
2  & 15-Jan & Th & Dating\\
3  & 20-Jan & T	 & Powers\\
4  & 22-Jan & Th & Multiplication\\
5  & 27-Jan & T	 & Golden Ratio\\
6  & 29-Jan & Th & Design by Induction\\
7  & 3-Feb  & T	 & Groups\\
8  & 5-Feb  & Th & Computer Arithmetic \\
9  & 10-Feb & T  & Counting\\
10 & 12-Feb & Th & Counting\\
11 & 17-Feb & T	 & Counting\\ 
12 & 19-Feb & Th & Counting\\
   & 23-Feb & M  & {\bf Quiz 1 in Recitation}\\
13 & 24-Feb & T	 & Counting\\ 
14 & 26-Feb & Th & Infinity\\
15 & 3-Mar  & T	 & Undecidability\\
16 & 5-Mar  & Th & Intractability\\
17 & 10-Mar & T	 & Automata Theory\\
18 & 12-Mar & Th & Probability\\
   & 16-Mar & M  & {\bf Quiz 2 in Recitation}\\
19 & 17-Mar & T	 & Probability\\
20 & 19-Mar & Th & Probability\\
   & 24-Mar & T	 & Spring Break	\\
   & 26-Mar & Th & Spring Break	 \\
21 & 31-Mar & T	 & Probability\\
22 & 2-Apr  & Th & Probability\\
23 & 7-Apr  & T	 & Probability\\
24 & 9-Apr  & Th & Graph Theory\\
25 & 14-Apr & T	 & Graph Theory\\
26 & 16-Apr & Th & Graph Theory\\
   & 20-Apr & M  & {\bf Quiz 3 in Recitation}\\
27 & 21-Apr & T	 & Graph Theory\\
28 & 23-Apr & Th & Cryptography\\
29 & 28-Apr & T	 & Cryptography\\
30 & 30-Apr & Th & Surprise\\
\hline \hline
\end{tabular}

\end{center}

\pagebreak

\begin{center}
{\bf \huge Important Course Information}\\
\vspace{.5em}
{\bf Bruce Maggs \hspace{7em} Jan 12, 1998}
\end{center}
 
\vspace{.3in}
\noindent
{\bf Course Description}

This course is about how to rigorously formulate and solve problems
relevant to Computer Science.  Examples will be taken from Algorithms,
Complexity Theory, Game Theory, Probability Theory, Graph Theory,
Automata Theory, Algebra, Cryptography, and Combinatorics.  Besides
providing an introduction to some of the most useful and important
ideas from these areas, this class will challenge students to develop
their general thinking ability.

The technical content of the course will include an introduction to
discrete mathematics: how to count, how to compute probabilities,
how to solve sums and recurrences, and graph theory.


\vspace{.3in}
\noindent
{\bf Prerequisites}

15-127, 21-127, and either 15-211 or concurrent enrollment in 15-211
Lecture II.  Special arrangements may be made by permission of the
instructor.  This course can be substituted for 21-228 in the CS
undergraduate curriculum.

\vspace{.3in}
\noindent
{\bf Text}

There is no required text for the course. The material is fairly
diverse, and no standard text contains it. Photocopies of the
transparencies used in the lectures will be handed out or made
available on the web. 

If you want to look at books which contain part
of the course material, I recommend the following:

\begin{enumerate}

\item \underline{Applied Combinatorics}, by A. Tucker, published by Wiley \& Sons.

\item \underline{Elements of Discrete Mathematics}, by C.L. Liu, published by McGraw-Hill.

\item \underline{Combinatorics: Topics, Techniques, Algorithms}, by P.
Cameron, published by Cambridge University Press.

\item \underline{Concrete Mathematics: A Foundation for Computer Science},by R. Graham, D. Knuth, and O. Patashnik, published by Addison-Wesley.

\item \underline{Elementary Probability Theory with Stochastic Processes}, by K.L. Chung, published by Springer-Verlag.

\item \underline{Fifty Challenging Problems in Probability}, by
F. Mosteller, published by Dover.

\item \underline{Introduction to Algorithms}, by T. Cormen, C. Leiserson,
and R. Rivest, published by MIT Press.

\item \underline{Discrete Mathematics and its Applications},
by K. H. Rosen, published by McGraw-Hill.

\item \underline{Cryptography: Theory and Practice}, by D.R. Stinson,
published by CRC Press.

\item \underline{How To Solve It: A New Aspect of Mathematical Method},
by G. Polya, published by Princeton University Press. 

\item \underline{Programming Pearls} and \underline{More Programming
Pearls}, by J. Bentley, published by Addison-Wesley.

\item \underline{Conceptual Blockbusting: A Guide to Better Ideas},
by J. L. Adams, published by W. W. Norton \& Company.

\end{enumerate}

\vspace{.3in}
\noindent
{\bf Web Page, Bboards, and Mailing Lists}

The class Web page will provide a wealth of up-to-date information
about the course. The URL is
\begin{itemize}
\item {\tt http://www.cs.cmu.edu/afs/cs/academic/class/15299/}
\end{itemize}
If you are
using a local UNIX system, a better URL is
\begin{itemize}
\item {\tt file:/afs/cs/academic/class/15299/index.html}
\end{itemize}
It will provide
faster access.

From the Web page, you can access the class Bboards. \\
{\tt cmu.andrew.academic.cs.15-299.announce} is for the course
staff to make announcements to the class. Please do not post
messages on this bulletin board. 

{\tt
cmu.andrew.academic.cs.15-299.discuss} is for general discussion
among members of the class. Please keep discussion relevant and
polite.

The Web page will include all assignments and on-line handouts, as well
as facilities to check how you are doing in the course. You should
visit it frequently.

The class will also have mailing lists: the list cs-299@cs mails to
the entire class and teaching staff; cs-299-A@cs, cs-299-B@cs,
cs-299-C@cs, and cs-299-D@cs mails only to the specified recitation
section (and its TA); cs-299-staff@cs mails only to the teaching
staff.

\vspace{.3in}
\noindent
{\bf Homework Assignments and Exams}

There will be problem sets, programming assignments, three quizzes,
and a final exam.

The grading formula will be:
\begin{description}
\begin{description}
\item[35\%] Homework (problem sets, programming assignments)
\item[30\%] Quizzes
\item[35\%] Final
\end{description}
\end{description}

This formula is a lower bound on your grade. If the class average as
computed by this formula is lower than a 77,
I will use a curve to raise your grades.  {\em Under no
circumstances will I use a curve to lower your grades.} From past
experience, I expect the formula to determine your grade exactly.
90 and above is A range, 80-89 is B range, 70-79 is C range, and
so forth.

Notice that if it is your habit to put in marginal effort on the
homework and to come through on the exams, your grade will suffer a
bit. This is deliberate; I think the homework is important.

Your mid-term grade will reflect your anticipated final grade.

\vspace{.3in}
\noindent
{\bf Typesetting}

{\em You must typeset your solutions to the problem sets.} This makes
the graders' job much easier. I recommend that you learn and use
\LaTeX, but anything typed is fine.  Both Microsoft Word and FrameMaker
can typeset equations.


\vspace{.3in}
\noindent
{\bf Late Work}

The good news is that you can hand in any assignment up to one week
late (seven days). The bad news is that you will lose five points (out
of 100) per day for the privilege. To be unambiguous, we define a
``day'' to start at midnight. You will lose five points for each extra
midnight that it takes you to do the assignment. {\em Late work makes
a class much harder to administer. It also hurts you. Please try and
avoid it.}  If your assignment is more than seven days late, you will
get a grade of zero (0) for that assignment.

Written assignments can be handed in only once, in their entirety.  If
you hand in multiple versions of a written assignment, only the first
version will be graded.

Programming assignments may be resubmitted any number of times
throughout the 7-day grading period.  Each night at midnight, starting
on the night the assignment is due, our scripts will automatically
collect all the new handins and grade them, taking into account the
5-point-per-day lateness penalty.  Your best current grade for the
assignment will be posted to the Web page by the following morning.

If you slip an assignment under my door, please put the date and time
on the top.  If I come in late at night and find that you have lied to
me, I will consider you to have cheated.

If you have a good excuse (such as being very sick), you should
contact me. For compelling reasons (that extend beyond the fact that
you have a lot of work lately and didn't plan ahead), I will excuse
you from the lateness penalty.

\vspace{.3in}
\noindent
{\bf Honors Problems}

A few of you will find the assignments too easy. For this
reason, I will include honors problems as a more
challenging alternative. These problems will be substantially
more sophisticated. Of course, you will learn much more by
doing them. In each assignment the honors alternative will
be made clear. Their point value will be specified.

If you do both the normal problem and the honors version you
will get the maximum of the two scores.

If you think that you might want to do research with me, or
if you will want a letter of recommendation from me, it is
a good strategy to attempt these problems.

\newcommand{\policy}{{\bf Policy on Collaboration and Cheating}

You \underline{may} verbally collaborate on homework problems and the
programming assignments.  On each problem and program that you hand-in,
you \underline{must} include the names of the people with whom you have
had discussion concerning your solution. Indicate  whether you gave
help, received help, or worked something out together. {\em You may
\underline{not} share written work or programs with anyone else.} You
may \underline{not} receive help from students who have taken the
course in previous years. You may \underline{not} review any course
materials (or software) from previous years. You may \underline{not}
read the current solution (handed out) if you will be handing in the
current assignment late. You may \underline{not} look up the answer to
a homework assignment which happens to appear in the published
literature. You may \underline{not} attempt to violate the security of
the electronic grading system. You \underline{may} get help from
anyone concerning programming issues which are clearly more general
than the specific assignment (e.g., what does a particular error
message mean?).

Thus, clear examples  of {\em cheating} include:

\begin{itemize}

\item Showing your code to another student.

\item Copying a program from someone else.

\item Getting help from someone whom you do not acknowledge
on your solution.

\item Showing a draft of a written solution to another
student.

\item Copying from another student during an exam.

\item Receiving exam related information from a student who has
already taken the exam.

\item Submitting a program that attempts to alter or erase grading
information.

\item Looking at someone else's files containing draft solutions, even
if the file permissions allow it.

\item Lying to the course staff.

\end{itemize}


\noindent
{\bf Penalty for Cheating}

My reaction to your cheating will vary according to the situation.

\begin{description}
\begin{description}

\item[Unsolicited Confession] If you seek me out and admit that
you have cheated, I will probably let it go.

\item[Solicited Confession] If I come to you and ask if you have cheated
and you freely admit it, I will take that into consideration. I will
either ask you to drop the class, or fail you in the course.

\item[Denial] If you do not admit that you have cheated, I will
provide my evidence that you have done so. I will at the very least
fail you in the class; furthermore, I will take my evidence to the
dean and seek more substantial penalties.


\end{description}
\end{description}

\noindent
{\bf Pedagogical Rationale and Advice}

Collaboration not only helps you get the job done, it teaches you how
to explain your (inchoate) ideas to others. This is why I permit
discussion of the problems between students. Be careful not to let
other people do all the work. If you misuse the opportunity for
collaboration in this manner, you will fail the exams and do poorly in
the course. The best is usually to find a single partner with whom you
have a relatively balanced collaboration. A group of four is usually
too big for everyone to be following the joint problem solving
process.


Many of the course materials will be the same as in previous years.
This is not because I am lazy. It takes years to develop good problems.
The only reason to change them is to make cheating more difficult. It
is far better for you to work on the most excellent problems that I
could find in my life so far. I appeal to your sense of honor because this is what is
optimal from a pedagogical point of view.

}


\vspace{.3in}
\noindent
{\policy}

\vspace{.3in}
\noindent
{\bf Signing the Statement on the Back Page}

I understand that most of you would never consider cheating in any
form. There is, however, a small minority of students for whom this is
not the case.  In the past, when I have caught students cheating
they often insisted that they did not understand the rules and
penalties. For this reason I require that each student sign and return
the back page of this document.

\pagebreak



\begin{center}
{\bf \Large Commitment to Honor the Cheating Policy}
\end{center}

\vspace{2em}

\fbox{\parbox{5in}{
{\tiny \policy}}}

\vspace{.6in}

\newcommand{\sigline}[1]{\raisebox{-.5\baselineskip}{
\begin{tabular}{c}
\rule{3in}{0.1mm}\\
{\sc #1}
\end{tabular}
}}


{\large I, \sigline{(print your name)}, have read and understood the above
statement of the CS 15-299 policy on collaboration and cheating which
was distributed on the first day of class. I agree to honor the
rules which the policy statement describes.\\\\

\hspace*{10em} \sigline{(sign and date)}

}

\end{document}
