Syllabus

Description and Objective: This course is intended as an introduction to the theory of computation for senior level undergraduates and graduate students. 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.

Grade Calculation:
30% Homework
30% Quizzes
35% Final Exam
5% Class Participation

Homework

Homework will be assigned regularly in the course. The homework release and due dates are listed on the schedule page, but in general, homework will be given out on Tuesday and will be due the following Tuesday. No homework will be accepted late in the course under any circumstances. Every assignment turned in after the due date will receive a 0.

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

Each assignment will count for 15 points and consist of 3 questions. The scores for a problem range from 0-5. A score of 0 means that no realistic attempt was made to solve the problem. A score of 5 means that the submission was both correct and well-formatted (i.e easily comprehendible).

All homework must be typed and turned in as PDF files through Gradescope. NO handwritten assignments will be graded. LaΤeΧ is probably the best application for generating PDF submissions, but students may use other applications if they'd like. LaΤeΧ files will be given for every assignment after HW1.

Whenever possible please limit your answer to each problem to a single page. When this is not possible, a page break should be inserted between problems. There is no need to include the original problem or your name in your solution.

Students are welcome and encouraged to work together and discuss homework verbally. Every homework assignment should be written up separately and individually (please review the section on academic miscondect below). Do not search online for solutions.

Regrade requests for all homeworks must be submitted within a week of the grades being released.

Quizzes

There are six quizzes during the course. The dates for the quizzes are given on the schedule page. The quiz problems will be similar to problems from the homework assignments. Quizzes can not be made up, a missed quiz results in a 0 for that quiz. Quizzes are given during the last part of the class and will typically last 20-30 minutes.

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

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 quizzes. Emails regarding the situation must be initiated by the academic dean.

Regrade requests for all quizzes must be submitted within a week of the grades being released.

Final Exam

The final exam will take place during the university-scheduled time slot. 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 final. Emails regarding the situation must be initiated by the academic dean.

The final exam will not be handed back. Students may review their results by scheduling an appointment with the professor.

Class Participation

Attending class is mandatory. All students are responsible for the material covered in class, which directly relates to the homework and quizzes problems. The class also has mandatory recitation sections. You should be signed up for a recitation section on SIS. Attendance will be taken in recitation.

The default grade for class participation is a 4 out 5. Students can raise this grade to a 5 with either perfect recitation attendence or constructive participation in lecture and/or recitation. Students who do not attend recitation, or who partipate in a disruptive manner will receive a score of 3 or lower.

Academic Misconduct

Students should read the Tufts handbook on academic integrity located on the judicial affairs website. If a student does not understand these terms or any of the material listed on this page, it is his/her responsibility to talk to the professor. 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.

Inclusivity

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 Accessibility@tufts.edu 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 COMP 170 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.

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.