Computer Science 344
Algorithms and Complexity
Spring 2010

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 $1,000 personal computer running a good algorithm can often outperform a $1,000,000 supercomputer running a bad (though 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.

Near the end of the semester, we’ll study problems believed to have no efficient solution by computer program, and even some problems which have no computational solution at all, and how we deal with such problems in reality.

2  Textbook

This course will involve reading assignments and homework exercises from the textbook Algorithm Design by Jon Kleinberg and Eva Tardos (Addison-Wesley 2005, ISBN 0-321-29535-8). This book is required, and you may find it a useful reference in subsequent courses and software projects. For any of you who are especially interested in this subject, I recommend a more advanced and encyclopedic book, Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. I may also give out other reading assignments by email, on the Web, or in journals.

This is a 3-credit class, which means you should budget 6 hours per week outside class for reading and homework. In particular, you’ll need to read about 30 pages per week, on average. Make time in your weekly schedule for this!

3  Prerequisites

I assume that everyone in the class has passed CSC-MTH 156 (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 at least a year of 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, linked list, etc.

4  Grading

There will be probably 7 homework assignments, each worth 11% of the semester grade (part of which is an in-class presentation of one or more problems) , and a final exam worth 15%. The remaining 8% of your semester grade will be “brownie points”, which you by asking and answering good questions in class, coming to me for help when you need it, etc, and you lose by cheating, being a pain in class, etc. All of these percentages may be adjusted, e.g. if we only do 6 homework assignments rather than 7.

The final exam 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.

For each homework assignment, I’ve allocated a day in the class schedule. The homework assignment is due at the beginning of that class, and the rest of that class will be devoted to student presentations of homework solutions. No later than the previous class meeting, choose one or two problems from the assignment that you’d like to present to the class, and confirm your choice with me. (I don’t want three different students presenting the same problem, so first-come, first-served.) On the scheduled presentation day, try to get to class a few minutes early and start writing your solution on the board; you will be expected to explain your solution orally, and answer technical questions about it from me and from your classmates. If you’re not sure of your solution or your presentation, feel free to discuss it with me in my office before the day you want to present it in class. Your grade for in-class presentations will be my assessment of how well you presented a solution and answered questions about it. Homework assignments will not be accepted late, since you’ve just seen other students’ solutions to several of the problems; however, if you haven’t finished all the problems, turn in the ones you’ve got.

There will be several kinds of homework in this class. At one extreme are the analysis and “thought” problems on paper, resembling problems in a math class. At the other extreme are programming assignments, which may be written in any language that you and I both know and that runs at Adelphi (e.g. Scheme, Prolog, Java, C, C++). In between are pseudocode assignments: these need to be precise descriptions of an algorithm, like a computer program, but they don’t need to meet the syntactic requirements of a compiler (only a human being will read them) and you can ignore details that aren’t relevant to the problem at hand. For example, in a problem that wasn’t primarily about sorting, you might say “sort table A in increasing order by value” as one line of the algorithm. On the other hand, if the assignment were about sorting, I would expect you to give the details of your sorting algorithm.

5  Ethics

The Adelphi University Code of Ethics applies to this course; look it up on the Web at http://academics.adelphi.edu/policies/ethics.php.

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 (e.g. I’ll grade the assignment once and divide the points equally among the several people who turned it in).

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 Monday, Wednesday, and Friday from 9:00-9:50 AM in Harvey 106, unless we agree to change that. The schedule of topics, reading assignments, and homework assignments will be maintained on the Web at http://www.adelphi.edu/sbloch/class/344/344_calendar.shtml. The dates are subject to change depending on how classroom discussions actually go. 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!