Design and analysis of algorithms

Lectures: 2 sessions / week, 1.5 hours / session

Recitations: 1 session / week, 1 hour / session

This course is the header course for the Theory of Computation concentration. You are expected, and strongly encouraged, to have taken:

Petitions for waivers will be considered by the course staff. Students will be responsible for material covered in prerequisites.

This course assumes that students know how to analyze simple algorithms and data structures from having taken 6.006. It introduces students to the design of computer algorithms, as well as analysis of sophisticated algorithms.

Upon completion of this course, students will be able to do the following:

Students who complete the course will have demonstrated the ability to do the following:

The primary written reference for the course is:

Cormen, Thomas, Charles Leiserson, et al. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848. [Preview with Google Books]

In previous semesters the course has used the first or second edition of this text. We will be using material and exercise numbering from the third edition, making earlier editions unsuitable as substitutes.

You are responsible for material presented in lectures, including oral comments made by the lecturer.

You are also responsible for material presented in recitations. Attendance in recitation has been well correlated in the past with exam performance. Recitations also give you a more personalized opportunity to ask questions and interact with the course staff. Your recitation instructor, together with the lecturers, will assign your final grade.

The final grade will be based on the problem sets, two evening quizzes, and a final given during final exam week.

The grading breakdown is as follows:

Although the problem sets account for only 20% of your final grade, you are required to at least attempt them. The following table shows the impact of failing to attempt problems:

Please observe that this table is for questions skipped, not problem sets.

The goal of homework is to give you practice in mastering the course material. Consequently, you are encouraged to collaborate on problem sets. In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study group meeting. Specifically, you should spend at least 30–45 minutes trying to solve each problem beforehand. If your group is unable to solve a problem, talk to other groups or ask your recitation instructor.

You must write up each problem solution by yourself without assistance, however, even if you collaborate with others to solve the problem. You are asked on problem sets to identify your collaborators. If you did not work with anyone, you should write "Collaborators: none." If you obtain a solution through research (e.g., on the web), acknowledge your source, but write up the solution in your own words. It is a violation of this policy to submit a problem solution that you cannot orally explain to a member of the course staff.

No collaboration whatsoever is permitted on quizzes or exams. Plagiarism and other dishonest behavior cannot be tolerated in any academic environment that prides itself on individual accomplishment. If you have any questions about the collaboration policy, or if you feel that you may have violated the policy, please talk to one of the course staff. Although the course staff is obligated to deal with cheating appropriately, we are more understanding and lenient if we find out from the transgressor himself or herself rather than from a third party or discover it on our own.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare