6.006: Introduction to Algorithms

Lectures will be held on Tuesdays and Thursdays from 11:00 AM to 12:00 PM in 32-123. You are responsible for material presented in lectures, including oral comments made by the lecturer (or other information that may not be present in the slides), as well as in recitations:

WF10 – Nicholas Zehender – 36-153
WF11 – Nicholas Zehender – 36-153
WF12 – Tianren Qi – 36-156
WF1 – David Wen – 26-142
WF2 – Joseph Laurendi – 36-156
WF3a – Joseph Laurendi – 36-156
WF3b – Michael Kuo – 36-153

A firm grasp of Python and a solid background in discrete mathematics are necessary prerequisites to this course. You are expected to have mastered the material presented in 6.01 (Introduction to EECS I) and 6.042J/18.062J (Mathematics for Computer Science).

If you have not taken and been successful in each of these subjects, please speak with a TA or professor before enrolling. We do allow students who have equivalent, other experience with the material described above to enroll, but with the firm understanding that mastery of this material is assumed and that course staff will not feel obligated to cover it or to help students who are struggling with it.

6.006 is a 12-unit (4-0-8) subject and serves as a Foundational Computer Science subject under the new curriculum. It is a direct prerequisite for 6.046 (Design and Analysis of Algorithms), the theory header.

One-hour recitations are held on Wednesdays and Fridays. You are responsible for the material presented in recitation, which may include new material not presented in lectures. Recitation attendance has been well-correlated with quiz performance in past semesters. Recitations also give you a more intimate opportunity to ask questions of and to interact with the course staff. Your recitation instructor is responsible for determining your final grade.

We do not use the recitation assignments made by the scheduling office. We will communicate your assignment to you before the first recitation meeting.

We will assign seven problem sets during the course of the semester. For dates, check the course calendar. Each problem set will consist of a programming assignment, to be completed in Python, and a theory assignment, to be typeset in LaTeX and compiled to PDF. (We will, however, accept scanned, hand-drawn diagrams turned in with your PDF.)

If you collaborate with others in any fashion, you must list their names as collaborators. For details, please see the section on our collaboration policy; we take this very seriously.

Late assignments will be severely penalized. (This penalty is currently a 1% deducation every six minutes or part thereof until the end of the tenth hour after the deadline, after which submissions will receive no credit.) To avoid penalties, contact us in advance to make arrangements. Otherwise, we will require a note from the appropriate dean advising us of your situation.

We will give two evening quizzes during the semester; these will each be two hours in duration. Check the course calendar for dates. Each will begin at 7:30 PM; room assignments will be announced in advance. There will also be a final exam during finals week.

Your final grade will be determined by the grades you recieve on problem sets, on quizzes, and on the final. The problem sets will together be worth approximately 30% of your grade; the quizzes, 20% each; and the final, 30%. The particulars of this policy are subject to the discretion of the course staff.

The code that you hand in will be graded based on its correctness, its quality, and the details of the algorithm that it implements.

Correctness — We will provide a set of public unit tests with each problem to help you test your work. However, we will often use additional unit tests in grading; we reserve the right to test any behavior specified by or following from the problem statement. Submissions that run for excessive amounts of time may be scored as incorrect.

Quality — Code should follow Python conventions. It should be neat, contain an appropriate quantity of helpful comments, use appropriate variable names, and so forth. Other implementation characteristics that affect readability, maintainability, or organization may also be graded.

Theory — Code should represent an implementation of an appropriately designed algorithm. While we do not necessarily expect you to achieve any lower bounds that may exist for a particular problem, submissions should not be overly inefficient in either time or space.

Responses to theory assignments must be typeset using LaTeX and then compiled to PDF. If you need to learn how to do this, check the resources section or your favorite search engine. Templates for student solutions are provided along with each problem set.. (We will, however, accept scanned, hand-drawn diagrams turned in with your PDF.)

The best responses will be concise, correct, and complete. Failing to answer part of the question, being overly verbose, missing special or edge cases, and answering mistakenly will each reduce your score.

When you are called upon to "give an algorithm," you must provide (1) a textual description of the algorithm, and, if helpful, pseudocode; (2) at least one worked example or diagram to illustrate how your algorithm works; (3) a proof (or other indication) of the correctness of the algorithm; and (4) an analysis of the time complexity (and, if relevant, the space complexity) of the algorithm.

Remember that, above all else, your goal is to communicate. After all, if a grader cannot understand your solution, they cannot give you any credit for it.

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, try asking questions via Piazzza so that other groups and the course staff can be helpful.

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 deugging. 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. Both manual and automatic mechanisms will be employed to detect plagiarism in code.

No other 6.006 student may use your solutions; this includes your writing, code, tests, docu- mentation, etc. It is a violation of the 6.006 collaboration policy to permit anyone other than 6.006 staff and yourself to see your solutions to either theory or code questions.

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 often have the ability to be more understanding and lenient if we find out from the transgressor himself or herself rather than from a third party.

The required textbook for the course is Introduction to Algorithms (3rd Ed.) by Cormen, Leiserson, Rivest, and Stein (Amazon). It is available wherever fine academic texts are sold.

For the student who finds books helpful, we also suggest Problem Solving With Algorithms and Data Structures Using Python by Miller and Ranum (Amazon).