Introduction to algorithms

Lectures: 2 sessions / week, 1.5 hours / session

Recitations: 1 session / week, 1 hour / session

This course introduces students to the analysis and design of computer 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:

A strong understanding of programming and a solid background in discrete mathematics, including probability, are necessary prerequisites to this course.

For MIT Students, this course is the header course for the MIT/EECS Engineering Concentration of Theory of Computation. You are expected to have taken 6.001 Structure and Interpretation of Computer Programs and 6.042J / 18.062J Mathematics for Computer Science, and received a grade of C or higher in both classes. If you do not meet these requirements, you must talk to a TA before registering for the course.

Lectures will be held twice a week on Mondays and Wednesdays for 1.5 hours. You are responsible for material presented in lectures, including oral comments made by the lecturer.

Students must attend a one-hour recitation session each week. The course staff will schedule recitations. You are responsible for material presented in recitation. Attendance in recitation has been well correlated in the past with exam performance. Recitations also give you a more intimate opportunity to ask questions and interact with the course staff. Your recitation instructor will assign your final grade. Recitations will be taught by the teaching assistants on Fridays.

Most handouts will be made available on the server in formats suitable for printing. Students should download and print out the handouts from the server. You will be informed via the server and/or email where and when the few handouts that are not available from the server can be obtained.

Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848.

Each Teaching Assistant will post his or her weekly office hours on the server. As an experiment, we will offer homework labs during the term. The time and location will be on the specific problem set. A homework lab is a place where you can go to do your homework with others in the class. Teaching Assistants will be available at the homework lab to help if you have questions about the problem set.

In addition, as a free service to its students, the MIT Department of Electrical Engineering and Computer Science provides one-on-one peer assistance in many basic undergraduate Course VI classes. During the first nine weeks of the term, you may request a tutor who will meet with you for a few hours a week to aid in your understanding of course material. You and your tutor arrange the hours that you meet, for your mutual convenience. More information is available on the HKN Web page.

Tutoring is also available from the Tutorial Services Room (TSR) sponsored by the Office of Minority Education. The tutors are undergraduate and graduate students, and all tutoring sessions take place in the TSR or the nearby classrooms.

Please fill out a sign-up sheet on the course server. The information you provide will help the course staff to get to know you better and create a mailing list and a course directory. Signing up is a requirement of the course. You will find it difficult to pass the course if you aren't in the class! You should notify your TA immediately if you drop the course after having registered. Listeners should also register for the course in order to be on the mailing list.

You must register before Ses #1. We will email your recitation assignment to you one day after Ses #1.

Nine problem sets will be assigned during the semester. The course calendar shows the tentative schedule of assignments and due dates, but the actual due date will always be on the problem set itself.

You will often be called upon to "give an algorithm" to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your essay should provide the following:

Remember, your goal is to communicate. Graders will be instructed to take off points for convoluted and obtuse descriptions.

The final grade will be primarily based on problem sets, one in-class quiz (Q1), one take-home quiz (Q2), and a final. The problem sets will together be worth about 80 points, the in-class quiz about 80 points, the take-home quiz about 150 points, and the final exam about 180 points.

Although the problem sets account for only 80 points in your final grade, you must do them. The following table shows the impact of failing to do problems:

Please observe that this table is for problems skipped, not problem sets. The specifics of this grading policy are subject to change if the need arises.

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 exams. The course has a take-home exam for the second quiz which you must do entirely on your own, even though you will be permitted several days in which to do the exam. More details about the collaboration policy for the take-home exam will be forthcoming in lecture 20. Please note that this lecture constitutes part of the exam, and attendance is mandatory.

Plagiarism and other anti-intellectual 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.

This course has great material, so have fun!

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