CS S-124 -- Algorithms and Data Structures

Instructor: Michael Mitzenmacher
E-mail: michaelm@eecs.harvard.edu
Course web page: http://www.fas.harvard.edu/~libcs124/SUMMER/class.html

Warning

To clarify things right up front, this class is essentially the same class given to Harvard undergraduates over the spring semester. We are squeezing a 14 week semester into an 8 week summer class. As such, this class is very challenging and represents a serious time commitment. If you don't have (at least) 20 hours a week to spend on this class, it might not be right for you.

For students at Harvard (or other universities) that take this class, I will be happy to document that the class is equivalent to the regular semester class and deserves full credit.

Objectives

This course covers the modern theory of algorithms, focusing on the themes of efficient algorithms and intractable problems. The course goal is to provide a solid background in algorithms for computer science students, especially those working in industry or planning to continue on with further advanced coursework. I strongly encourage mathematicians and people from other areas of study to take the course as well.

Besides introducing the basic language and tools for algorithm analysis, we will also cover several specific problems and general design paradigms. Toward the end of the quarter, we will also examine heuristic techniques often used in practice, even though in many cases formal theoretical results are not known.

We will focus on the theoretical and mathematical aspects in class and on the homework assignments. But because one gains a deeper understanding of algorithms from actually implementing them, the course will include a substantial programming component. More details will be available when the first programming assignment is given.

As you can see from the preliminary list of topics (included below), we will be covering a great deal. I expect the course to be challenging, both in terms of the workload and the difficulty of the material. You should be prepared to do a lot of work outside of class. The payoff will be that you will learn a lot of both useful and interesting things.

Prerequisites

Students should be able to program in a standard programming language; C, C++, or Java is preferred. Some mathematical maturity also will be expected; students should have some idea of what constitutes a mathematical proof and how to write one. Some knowledge of basic probability will also be helpful. If you do not have sufficient math background (such as Math E-104), you should reconsider taking this course. A very basic self-diagnostic quiz is available on the class web page.

Assessment

Your performance will be measured in four ways. (The percentage contributions to your grade given below are approximate and subject to change.)

All assignments will be due on the date assigned. Assignments will not be accepted late with the exception of medical emergencies or similar exceptional circumstances that must be discussed in advance with the instructor. Please remember it is better to turn in an incomplete assignment rather than no assignment.

Collaboration Policy

I would like to emphasize the rules on working with others on homework assignments. For the programming assignments, in somce cases it may be possible to work in pairs; this will be decided further in the course. In such a case, it is assumed you will not work with anyone besides your partner. For problem sets, limited collaboration in planning and thinking through solutions to homework problems is allowed, but no collaboration is allowed in writing up solutions. You are allowed to work with one or two other students currently taking 124 in discussing, brainstorming, and verbally walking through solutions to homework problems. But when you are through talking, you must write up your solutions independently and may not check them against each other. There may be no passing of homework papers between collaborators; nor is it permissible for one person simply to tell another the answer.

If you collaborate with one or two other students in the course in the planning and design of solutions to homework problems, then you should give their names on your homework papers.

Under no circumstances may you use solution sets to problems that may have been distributed by the course in past years, or the homework papers of students who have taken the course past years. Nor should you look up solution sets from other similar courses, or otherwise take solutions from the Web. (They're probably wrong anyway.)

To be perfectly clear: when you are writing your solutions, you should be alone, and your writing should therefore clearly be in your own words . Talking about problems before writing your solution is OK; going over solutions line by line as you write them is not. Please ask if you are unclear on this.

Violation of these rules may be grounds for giving no credit for a homework paper and also for serious disciplinary action. Severe punishments will apply, so please do not violate these rules. If you have any questions about these rules, please ask an instructor.

Required Text

There is no required text. I recommend, however, you consider at least one of the following books:

In place of a book, class notes will be regularly made available. Generally these notes will not be available until a few days after the corresponding lecture.

Class Information/Notes

Class notes, homework assignments, and other information will be made available on the Web when possible. For access go to the class web site. Generally this information will be available in Postscript, so you will want to find a Postscript viewer. In many cases, the class web-site may be the only location where information is posted or available, so look in from time to time!

Incomplete List of Topics