Introduction to algorithms

Lectures: 2 sessions / week, 1 hour / session

Recitations: 2 sessions / week, 1 hour / session

A strong understanding of programming in Python™ and a solid background in discrete mathematics are necessary prerequisites to this course.

You are expected to have taken 6.01 Introduction to EECS I 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 taking the course.

For those students pursing the new curriculum, 6.006 will serve as a Foundational Computer Science course. In Fall 2008, 6.046 will have 6.006 as a prerequisite, and 6.046 will serve as a Computer Science theory header.

Students pursuing the old curriculum may count 6.006 as their computer science theory header (i.e., as a substitute for 6.046). 6.046 can still be taken and counted as a theory elective, if it is taken Fall 2008 or later.

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

Students must attend 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 participation in recitation counts for a part of your grade, and your final grade will be assigned by your recitation instructor.

Six problem sets will be assigned during the semester. A large portion of each problem set will be a coding assignment to be done in Python. Any code for submission must upload to the class Web site, and the final submission will be graded.

There will be two evening quizzes, on the days of Ses #R9 and Ses #R16. The quizzes will be two hours long starting at 7:30PM. Recitations those days will be optional review sessions.

There will also be a final exam during finals week.

The final grade will be primarily based on 6 problem sets, two quizzes, and a final. The problem sets will together be worth 40 points, each quiz will be 15 points, and the final exam 25 points. Recitation participation will be worth 5 points.

The specifics of this grading policy are subject to change at the discretion of the course staff.

Code will be graded for correctness and for the algorithm used.

Correctness: You will be given a public set of unit tests to test your code. For grading purposes, we will run your code against a more thorough private set of unit tests. Your code must run within the time allotted (which will vary by assignment).

Algorithm: Your code must come well-commented describing the algorithm used. Your code must be readable so the TAs will believe that your code does what it claims to do. Your algorithm should be efficient.

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

Code you submit must also be written by yourself. You may receive help from your classmates during debugging. Don't spend hours trying to debug a problem in your code before asking for help. However, regardless of who is helping you, only you are allowed to make changes to your code. A suite of algorithms will be run to detect plagiarism in code.

No other 6.006 student may use your solutions; this includes your writing, code, tests, documentation, etc. It is a violation of the 6.006 collaboration policy to permit anyone other than 6.006 staff and yourself read-access to the location where you keep your code.

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.

The primary written reference for the course is the following textbook:

Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press, 2001. ISBN: 9780262032933.

We also recommend:

Miller, Bradley, and David Ranum. Problem Solving with Algorithms and Data Structures Using Python. Wilsonville, OR: Franklin, Beedle and Associates, 2005. ISBN: 9781590280539.

You should be as clear and precise as possible in your write-up of solutions. Understandability of your answer is as desirable as correctness, because communication of technical material is an important skill.

A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand. Sloppy answers will receive fewer points, even if they are correct, so make sure that your handwriting is legible. It is a good idea to copy over your solutions to hand in, which will make your work neater and give you a chance to do sanity checks and correct bugs.

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.

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