\documentclass[12pt]{article} \usepackage{fullpage} \newcommand{\tm}{\mbox{\sc tm}} \begin{document} \title{Computer Science 344 \\ Algorithms and Complexity \\ Spring 1997} \author{Dr. Stephen Bloch \\ office 112 Alumn\ae\ Hall \\ phone 877-4483 \\ email \texttt{sbloch@boethius.adelphi.edu}} \maketitle \section{Subject Matter} This is a course for anybody who's ever complained about a computer being slow. When faced with a computer program that takes unacceptably long to solve the problem at hand, one option is to buy faster, more expensive computer hardware. But this option has its limits: perhaps your money will run out, or perhaps you'll upgrade to the fastest computer on the market and still be unsatisfied. Often a better option is to find a more efficient approach to the problem ---~to re-think the \emph{algorithm} so that it makes \emph{better use} of the hardware. A \$2,000 personal computer running a good algorithm can often outperform a \$2,000,000 supercomputer running a bad (although still correct) algorithm. In this course we'll learn how to measure the efficiency of an algorithm, independent of language, operating system, or hardware. We'll survey a variety of techniques for designing efficient algorithms. (Many of these techniques will help you program correctly even when you're not worried about efficiency.) We'll even learn how to prove that a given algorithm is ``as good as it can get,'' in the sense that \emph{no} algorithm, no matter how clever, will \emph{ever} be better than this one. \section{Textbook} This course will involve reading assignments and homework exercises from the textbook \emph{Fundamentals of Algorithmics} by Gilles Brassard and Paul Bratley. This book is required. For any of you who are especially interested in this subject, I recommend a more advanced book, \emph{Introduction to Algorithms} by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. I may also give out other reading assignments by email or in journals. I hope to cover all of chapters 1--8 of the Brassard-and-Bratley book, and as much of chapters 9--12 as we have time for. This is about 400 pages, so you need to read about 15 pages per lecture, on average. \section{Prerequisites} I assume that everyone in the class has passed CSC-MTH 254 (Discrete Structures) or an equivalent course covering Boolean logic and algebra, graphs and trees, and perhaps recurrence relations. I also assume that everyone in the class has passed one or more programming courses; I don't care about the language, as long as you have written and debugged a number of programs and are familiar with the notions of algorithm, recursion, loop, array, list, \emph{etc.} \section{Grading} As I write this (a week before classes start), I envision three homework assignments, each worth 15\% of the semester grade, a midterm worth 20\%, and a final exam worth 35\%. % If we get behind schedule, we'll % actually do fewer assignments than this. I'll try to keep an up-to-date schedule on my Web page. % 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. Exams 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. Homework and programming assignments will be accepted late, with a penalty of 1/5 per 24 hours or portion thereof after they're due. An hour late is 20\% off, 25 hours late is 40\% off, \emph{etc.} No matter how late you are, however, it's better (both for your education and for your grade) to do the assignment than not to do it at all. The majority of assignments in this course will be on paper, \emph{i.e.} non-programming. \section{Ethics} Most of the assignments in this class are to be done individually. You may \emph{discuss general approaches} to a problem with classmates, but you \emph{may not copy} large pieces of programs or homework solutions. If you do, \emph{all} the students involved will be penalized. All work on an 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. \section{Schedule} This class meets every Tuesday and Thursday from 9:25 to 10:40 AM, except on University holidays or if I cancel class. 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 {\em vice versa}, the schedule will shift. 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!} \begin{tabbing} {\bf Date(s) \hskip20pt} \= {\bf Assignment} \= {\bf Reading \hskip30pt} \= {\bf Subject} \kill {\bf Date(s)} \> {\hskip-20pt \bf Assignment} \> {\bf Reading} \> {\hskip40pt \bf Lecture Subject} \\ % 23 Jan \> \> \> Administrivia, ``what is this course about?'' \\ 28 Jan \> \> 1 \> Proofs and proof techniques \\ 30 Jan \> \> 2 \> Problems \emph{vs.} instances, average \emph{vs.} worst case, \emph{etc.} \\ 4 Feb \> \> skim 12.1--12.4 \> Lower bounds and proof techniques \\ 6 Feb \> HW1 \> 3 \> Asymptotic notation \\ 7 Feb \> \> \> Last day to add courses \\ 11 Feb \> \> 4.1--4.5 \> Analyzing basic control structures \\ 13 Feb \> \> 4.6 \> Amortized analysis \\ 18 Feb \> \> 4.7 \> Recurrence relations \\ 20 Feb \> HW1 due \> 5.1--5.5 \> Basic data structures \\ 21 Feb \> \> \> Last day to drop courses \\ 25 Feb \> \> 5.6 \> Associative tables \& hashing \\ 27 Feb \> \> 5.7--5.8 \> Heaps \\ 4 Mar \> \> 5.9 \> Disjoint sets and union/find data structures \\ 6 Mar \> \> \> Catch up and review for midterm \\ 11 Mar \> \> \> Midterm exam \\ 13 Mar \> \> 6.1--6.4 \> Greedy algorithms \\ 18 Mar \> \> 6.5--6.6 \> Knapsack and scheduling algorithms \\ 20 Mar \> HW2 \> \> Discuss midterm \\ 21 Mar \> \> \> Last day to withdraw from classes \\ 25--27 Mar \> \> \> Spring break --- no classes \\ 1 Apr \> \> 7.1--7.4 \> Divide-and-conquer, sorting \\ 3 Apr \> \> 7.5 \> Selection and medians \\ 8 Apr \> \> 7.6--7.8 \> Matrix multiplication, exponentiation \\ 10 Apr \> HW2 due \> 7.8 \> Cryptography \\ 15 Apr \> \> 8.1--8.4 \> Dynamic programming \\ 17 Apr \> HW3 \> 8.5--8.8 \> Applications of dynamic programming \\ 22 Apr \> \> \> Passover --- no classes \\ 24 Apr \> \> 9.1--9.4 \> Graphs and trees \\ 29 Apr \> \> 9.5--9.6 \> Breadth-first search and Backtracking \\ 1 May \> \> 11.1--11.4 \> Parallel computation \\ 6 May \> \> \> I may be at a conference \\ 8 May \> HW3 due \> reread 12.1--12.4 \> Catch up and review for final \\ 15 May \> \> \> 10:30--12:30, Final Exam \\ 18 May \> \> \> Commencement \\ \end{tabbing} \end{document} Homework assignments HW1: chaps. 1-3: proofs, problems vs. instances, asymptotic notation Midterm: largely chaps. 4-5: basic data and control structures HW2: chap. 6, some of chaps. 4-5 (whatever they flubbed on midterm) HW3: chap. 7,8 Final: largely chaps. 9,11