Computer Science 344 Algorithms and Complexity Spring 1997

Dr. Stephen Bloch office 112 Alumnæ Hall phone 877-4483

                email sbloch@boethius.adelphi.edu

January 13, 1997

1 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 algorithm so that it makes 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 no algorithm, no matter how clever, will ever be better than this one.

2 Textbook

This course will involve reading assignments and homework exercises from the textbook 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, 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.

3 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, etc.

4 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%. I’ll try to keep an up-to-date schedule on my Web page.

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. 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, 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, i.e. non-programming.

5 Ethics

Most of the assignments in this class are to be done individually. You may discuss general approaches to a problem with classmates, but you may not copy large pieces of programs or homework solutions. If you do, 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, both students will be penalized; see above.

6 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 vice versa, the schedule will shift.

I expect you to have read the reading assignments 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. Please read ahead!

Date(s) Assignment Reading Lecture Subject 23 Jan Administrivia, “what is this course about?”

28 Jan  1  Proofs and proof techniques
30 Jan  2  Problems vs. instances, average vs. worst case, 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