Description and Objective: This course is intended as an introduction to the theory of computation for senior level undergraduates and graduate students looking for background material in theory. The major topics within the course include: models of computation, undecidability, infeasibility, diagonilizations, nondeterminism, information theory, time vs space, complexity classes, regular languages, context free grammars.

Prerequisites: MATH/COMP 61 and COMP 15

Text: The textbook for the course is Introduction to the Theory of Computation (3rd edition). Michael Sipser, Thomson (2013) ISBN: 978-1-133-18779-0. The second edition should be fine as well.

Course Attendance: Attending class is mandatory. All students are responsible for the material covered in class. The homework and quizzes are directly related to the material discussed in class. If you miss a lecture come to office hours to discuss what material was covered. The class also has mandatory recitation sections. There are 5 sections and you should be signed up for one on SIS. Attendance will be taken in recitation.

Grade Calculation:
25% Homework Assignments
15% Quizzes
25% Midterm
30% Final
5% Class Participation

Homework: Homework will be assigned regularly in the course. In general, the homework will be given out on Tuesday and will be due the following Tuesday. The detailed dates are listed on the schedule page on the course website.

Homework Details: Each assignment will count for 25 points and consist of 5 questions. The scores for a problem range from 0-5, corresponding to Excellent, Very Good, Good, Fair, and Poor. A zero means no realistic attempt was made.

The lowest homework grade is dropped from the student grade calculation.

No homework will be accepted late in the course under any circumstances. Every assignment turned in after the due date will receive a 0.

All homework will be typed and turned in as PDF files through provide.

LaΤeΧ files will be given for each assignment. LaΤeΧ is probably the easiest way to type your assignments. Students may use other applications, but must generate PDF files when turing in the assignment.

NO handwritten assignments will be graded (exceptions for immaculate handwriting)

Every problem should a separate PDF file. For example, the provide command for the first assignment would be:

provide comp170 hw1 p1.pdf p2.pdf p3.pdf p4.pdf p5.pdf

Whenever possible please limit your answer to any one problem to one page.

Students are welcome and encouraged to work together and discuss homework verbally. Every homework assignment should be written up separately and individually. Do not search online for solutions.

Quizzes: There are five quizzes during the course. The dates for the quizzes are given on the schedule page. Each quiz is one problem. The problems will be similar to ones from the homework assignments. Quizzes can not be made up, a missed quiz results in a 0 for that quiz. The lowest quiz grade will be dropped from the grade calculation. Quizzes are given during the last part of the class. Quizzes will typically last 20 minutes.

Final Exam: There is a final exam in the course on December 14th at 12:00Noon. No makeup exams will be given.

Students with extreme special circumstances and only with prior approval by their academic dean must meet with the professor to make other arrangements to the scheduled homework and quizes. Emails regarding the situation must be initiated by the academic dean

Feedback: Your thoughts and concerns about this course are important. You are encouraged to give feedback to the instructors and teaching assistants throughout the term. As always students will be asked to fill out a course evaluation at the middle and end of the term.

Academic Misconduct: Students should read the Tufts handbook on academic integrity located on the judicial affairs website.

A few highlights are presented to emphasize importance:

Absolute adherence to the code of conduct is demanded of the instructors, teaching assistants, and students. This means that no matter the circumstance any misconduct will be reported to Tufts University.

Writing proofs and algorithms is a creative process. Individuals must reach their own understanding of problems and discover paths to their solutions. During this time, discussions with friends and colleagues are encouraged—you will do much better in the course, and at Tufts, if you find people with whom you regularly discuss problems. But those discussions should take place in English. If you share written work, you're breaking the rules.

When you begin wrtiting up your solutions, discussions are no longer appropriate. Each problem solution must be entirely your own work.

Do not, under any circumstances, permit any other student to see any part of your written solution, and do not permit yourself to see any part of another student's written solution.

If any student does not understand these terms or any material outlined in The Academic Code of Conduct it is his/her responsibility to talk to the professor.

Inclusive Class: Respect is demanded at all times throughout the course. In the classroom, not only is participation required, it is expected that everyone is treated with dignity and respect. We realize everyone comes from a different background with different experiences and abilities. Our knowledge will always be used to better everyone in the class.

Tufts University values the diversity of our students, staff, and faculty; recognizing the important contribution each student makes to our unique community. Tufts is committed to providing equal access and support to all qualified students through the provision of reasonable accommodations so that each student may fully participate in the Tufts experience. If you have a disability that requires reasonable accommodations, please contact the Student Accessibility Services office at or 617-627-4539 to make an appointment with an SAS representative to determine appropriate accommodations. Please be aware that accommodations cannot be enacted retroactively, making timeliness a critical aspect for their provision.

Tufts and the teaching staff of Comp170 strive to create a learning environment that is welcoming to students of all backgrounds. If you feel unwelcome for any reason, please let us know so we can work to make things better. You can let us know by talking to anyone on the teaching staff. If you feel uncomfortable talking to members of the teaching staff, consider reaching out to your academic advisor, the department chair, or your dean.