\documentstyle[11pt]{article}
% \pagestyle{empty}
%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.5in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.0in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\parindent}{1pc}
% \newenvironment{proof}%
% {\relax{\noindent\sc Proof.\ \ }}%
% {\ifhmode\nobreak\qed\par\fi\medskip}
% \newcommand{\forprelim}[1]{#1}
% \newcommand{\forfinal}[1]{\mbox{}}
\begin{document}
\title{Computer Science 580 \\
Algorithm Design}
\author{Dr. Stephen Bloch \\
office 1101 POT, phone 257-3416 \\
email {\tt sbloch@s.ms.uky.edu} \\
office hours MW 3-5 PM or by appointment}
\maketitle
\section{Subject Matter}
A beginning programmer is generally content to write a program that
gives the correct answer without going into an infinite loop. In this
class we shall concentrate on {\em efficiency} of algorithms, trying
to minimize the time, memory, and other resources required by an
algorithm. One can often improve the efficiency of an algorithm simply
by learning and applying various heuristics for
``efficient algorithm design'',
but to achieve the most dramatic results or to document one's success
one must also study the {\em analysis} of algorithms, the process of
figuring out mathematically exactly how much resources a given
algorithm uses.
Often such analysis shows each of two algorithms to be better than the
other in different circumstances, and then a good designer must choose
the algorithm more suited to the circumstances. In addition, however,
the process of analysis itself often gives insights that lead to the
implementation of new, significantly more efficient algorithms.
Any working algorithm, together with its analysis, gives an
{\em upper bound} on the intrinsic difficulty of the problem.
Sometimes after we have tried without success to improve an algorithm,
we may grow to suspect that it {\em cannot} be improved. Techniques
for proving that {\em no} algorithm can take less than a certain time,
or a certain amount of memory, or whatever, give us {\em lower bounds}
on the intrinsic difficulty of the problem. Although lower bounds are
often difficult to prove, they can prevent a programmer from wasting
time trying to improve an already-optimal algorithm. It's also
immensely satisfying to know, with mathematical certainty, that your
algorithm is essentially the best there can be for a given problem.
In this course we shall examine a number of fundamental problems in
computing. For each we shall typically write a na\"{\i}ve algorithm,
analyze it (looking for aspects of the algorithm that most affect its
efficiency), write and analyze one or more improved algorithms, and
attempt to find lower bounds on the problem's intrinsic difficulty.
The textbook for the course is {\em Introduction to Algorithms}, by
Cormen, Leiserson, and Rivest. Both reading and homework assignments
will come from this textbook, and you are strongly advised to buy your
own copy.
\section{Grading}
There will be numerous homework assignments (some written and
mathematical, some programming) and a final exam.
The exam is worth 50\% of your semester grade, the homework assignments
(all weighted equally unless I state otherwise at the time I assign
them) the remaining 50\%. I may list, say, twenty problems in one
homework assignment and promise to grade, say, five;
this means I expect you to at least read {\em all} the problems,
work and turn in as many of them as you can,
but indicate which five you want me to grade.
If there are other problems you want me to look at but {\em not} grade
(say, the ones that really stumped you), write a big question mark or
something next to them.
Each day that a homework assignment is due, part of the class period
will be devoted to students presenting solutions at the board.
Each student in the class must present at least one (preferably two)
starred homework problem(s) in class: this means write up your solution
on the board, explain the tricky parts, and answer questions about your
solution from the professor and the other students. This course
requirement may be modified depending on the number of students.
I shall convert the numeric grade calculated from exam and homework
into a letter grade 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.
Homework is due in class on specified days.
If you leave it at home or
something like that and are sufficiently persuasive, I may give you a
few hours' extension. A documented medical or family emergency may
also warrant an extension. Homework turned in late without such an
extension will be recorded with a grade of 0.
You must take the final exam at the scheduled time, unless arranged in
advance or prevented by a documented medical or family emergency.
If you have a
religious holiday that conflicts with an exam,
University policy requires you to notify me in writing before 31 August
in order to receive due consideration. Exams not taken without one of
the above excuses will be recorded with a grade of 0.
\section{Ethics}
You are allowed, indeed encouraged, to discuss homework problems with
classmates, but you must write them up by yourself. If two people's
homeworks are consistently very similar, I may ask those two not to
work together on the next assignment so I can make sure each of them
is capable of doing the work alone. If two people's exams are very
similar, I will charge them with cheating.
A proven instance of cheating or plagiarism carries a {\em minimum}
penalty of failing the course, and the University may also impose
further penalties such as suspension or expulsion. Don't do it.
\pagebreak[3]
\section{Schedule}
This class meets every Monday, Wednesday, and Friday from 2:00 PM to
2:50 PM, except on University holidays or if I cancel class.
\nopagebreak[3]
\subsection{Events Fixed to Dates}
\begin{tabular}{ll}
25 Aug & First class meeting \\
6 Sept & Labor day holiday \\
15 Sept & Last day to drop without a grade \\
18 Oct & Last day to drop \\
26 Nov & Thanksgiving holiday \\
10 Dec & Last class meeting \\
17 Dec & Final exam, 1:00 PM
\end{tabular}
The final exam may in fact be take-home, in which case it will be due
either during finals week or during the last week of class. I haven't
decided this yet.
% \subsection{Sequence of Topics}
% Dates in this schedule are approximate. Some topics may take us
% more, or less, time than I've given them.
% \begin{tabbing}
% {\bf \ \ \ Date(s)\ \ \ } \= \=
% % {\bf Homework} \=
% {\bf \ \ \ Reading\ \ \ } \=
% {\bf Topics} \\
% 25 Aug \> \> \> Introduction, administrivia \\
% 27 Aug--6 Sept \> \> Chaps.\ 1--6 \> Mathematical foundations \\
% 8--28 Sept \> \> Chaps.\ 7--10 \> Sorting, Heaps, and Order Statistics \\
% 30 Sept--5 Oct \> \> Chaps.\ 16,17 \> Optimization problems \\
% 7 Oct \> \> Chap.\ 18 \> Amortized analysis \\
% 12--21 Oct \> \> Chaps.\ 20--22 \> More heaps and related data structures \\
% 26 Oct \> \> \> catch up, assuming we're behind schedule by now \\
% 28 Oct \> \> Chap.\ 28 \> Sorting networks? \\
% 2--4 Nov \> \> Chap.\ 29 \> Arithmetic circuits \\
% 9--11 Nov \> \> Chap.\ 30 \> Parallel algorithms \\
% 16--18 Nov \> \> Chap.\ 32 \> Fast Fourier transforms \\
% 23 Nov \> \> Chap.\ 31 \> Matrix algorithms \\
% 30 Nov--2 Dec \> \> Chap.\ 33 \> Number theory and cryptography \\
% 7--9 Dec \> \> Handouts \> Enumeration and Isomorph Rejection \\
% \end{tabbing}
% \pagebreak
% \bibliography{all}
% \bibliographystyle{alpha}
\end{document}
1 26 Aug
2 31 Aug
3 2 Sept
4 7 Sept
5 9 Sept
6 14 Sept
15 Sept (Last day to drop w/o grade)
7 16 Sept
8 21 Sept
9 23 Sept
10 28 Sept
11 30 Sept
12 5 Oct
13 7 Oct
14 12 Oct
15 14 Oct
18 Oct (Last day to drop)
16 19 Oct
17 21 Oct
18 26 Oct
19 28 Oct
20 2 Nov
21 4 Nov
22 9 Nov
23 11 Nov
24 16 Nov
25 18 Nov
26 23 Nov
25 Nov (Thanksgiving holiday)
27 30 Nov
28 2 Dec
29 7 Dec
30 9 Dec
13 Dec Final Exam (8:00 AM)