\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)