Syllabus: MAT/COM323 Theory of Computation Fall 2015

MATH/COM 323 - Theory of Computation - Fall '15

Instructor: Perry Susskind Office Hours: Tues, Thurs 9:15 – 10:00 AM, and by appointment. | Office: 409 Fanning Phone: 439-2025 (office), 444-1086 (home) e-mail: pdsus@conncoll.edu |

Instructor: Christine Chung Office Hours: Mon, Wed 9:30-11 AM (tentative). Sign up for a slot here. Or email for an appointment. | Office: 220 New London Hall Phone: 439-2074 (office) e-mail: cchung@conncoll.edu |

Texts: "Introduction to the Theory of Computation," by Michael Sipser, Second Edition, Thomson 2006 (required).

Prerequisites: MAT210 or permission of the instructor.

We shall study topics in chapters 1 – 8 of the text. These are: Finite Automata, Context Free Languages, Turing machines, Church's Thesis, Uncomputability, Computational Complexity.

[Stolen shamelessly from a similar class at Univ of Pitt]

Course Mechanics:

There will be weekly problem sets for homework. These will be graded and returned to you. Attendance in class is required. You will also be expected to present problems and their solutions in class from time to time. There will be a midterm and a final exam. Your grade will be based on a weighted average of homework grades, test grades, and classroom performance. Numerical averages of your grades will not supersede the judgment of your instructor. If there is time we will also discuss recent applications of the theory.

Description:

What is a computation? Are there fundamental problems for which no computer algorithm will ever produce a solution? Are there computational problems which in principle can be solved but which are impracticable by virtue of the amount of time they take to solve?

In the theory of computation, these important questions in contemporary philosophy and mathematics are attacked by investigating the abstract theory of computing machines including the theory of deterministic and nondeterministic finite automata, formal languages, computability by Turing machines, uncomputability and computational complexity. The approach is mathematical and the subject matter is related to the incompleteness (Gödel) theorems of mathematical logic.

However, the viewpoint and motivation come from concerns in computer science; for instance, the theory of parsing, graph algorithms and many problems of a practical nature are studied. The course is a bridge between ideas in linguistics, logic, computer science, abstract mathematics, philosophy and more recently, physics; it culminates in a discussion of a most pressing open problem in current mathematical research: Does P = NP?

[Images from actual episodes of the Simpsons and Futurama]

Schedule (tentative)

[Note: All readings and exercises refer to the Sipser text.]

Week# | Topic | Assignment | |

1 |
| ||

Thurs | Intro | HW1 due Thurs, Sept 10 Reading: all of chapter 0 and 1.1 Exercises: 0.1, 0.2, 0.4, 0.5, 0.7, 0.11, 1.1, 1.3, 1.6 a,b | |

2 | Regular Languages | HW2 due Thursday Sept 17 Reading: HW1 grading notes and solutions, Sipser 1.2 and 1.3 Exercises: 1.4 g, 1.5 g, 1.6 a, c, f, j, 1.8 b, 1.10 b, 1.12, 1.14 a, b, 1.16, 1.18 a, c, f, j | |

Tues | 1.1 Finite automata | ||

Thurs | 1.2 Non-determinism | ||

3 |
| ||

Tues | 1.3 Regular expressions | HW3 due Thursday Sept 24 Reading: HW 2 grading notes and solutions, and the rest of chapter 1 Exercises: 1.19, 1.21, 1.29 b, 1.31, 1.30, 1.32, 1.46 a, c, 1.48 (Hint: write D as the union of two regular expressions), 1.57. | |

Thurs Sept 17 | 1.4 The pumping lemma | ||

Week# | Topic | Assignment | |

4 | Context-Free Languages | HW4 Reading: HW2 and HW3 solutions, Sipser 2.1, 2.2 Exercises: 2.1, 2.4b,e,f, 2.5b,e,f, 2.11, 2.14, 2.16, 2.26, 2.27 | |

Tues | 2.1 Context free grammars | ||

Thurs Sept 24 | 2.2 Pushdown automata | ||

5 | HW 5 Reading: the rest of chapter 2 and HW 4 solutions Exercises: 2.2, 2.25, 2.30a, 2.35, *Show that the complement of the language (from Example 2.38) is a context free language. Note, this example provides another proof that CFLs are not closed under complementation. | ||

Tues | 2.3 Equivalence of CFGs and PDAs | ||

Thurs | 2.3 The pumping lemma for context-free languages | ||

Week# | Topic | Assignment | |

6 | The Church Turing Thesis | HW6 Reading: HW 5 solutions, 3.1 and 3.2 Exercises: 3.1a,c, 3.2b, 3.9, 3.13, 3.15d,e, 3.16d | |

Tue s | 3.1 Turing machines | ||

Thurs | 3.2 Turing machine variants | ||

Week# | Topic | Assignment | |

7 | |||

Tues | 3.2-3.3 | HW7 Reading: the rest of chapter 3 Exercises: 3.6, 3.7, 3.18, 3.21 | |

Thurs | 3.3 | ||

Week# | Topic | Assignment | |

8 |
| ||

Tues | Fall Break | Due on Thurs Oct 29 Take-home, open-book, open-note Midterm Exam on chapters 1-3. | |

Thurs | 4.1 Decidable languages | ||

Week# | Topic | Assignment | |

9 | HW 8 Reading: all of chapter 4 Exercises: 4.3, 4.6, 4.12, 4.16, 4.19, 4.22 | ||

Tues | 4.2 Undecidability | ||

Thurs | 5.1 The halting problem and other undecidable problems | ||

10 | Reducibility |
| |

Tues | More 5.1 and 5.2 | HW9 Reading: all of chapter 5 Exercises: 5.1, 5.3, 5.9, 5.17 | |

Thurs | 5.3 Mapping reducibility | ||

Week# | Topic | Assignment | |

11 |
| ||

Tues | 7.1 Measuring complexity | HW10 Reading: chapters 7.1 and 7.2 Exercises: 7.1a,b,e, (show how each True answer satisfies def of big-O) 7.2a,b,e,f, (show how each True answer satisfies def of little-o) 7.3a,b, 7.4, 7.6, 7.10 | |

Thurs | 7.2 The class P | ||

12 |
| ||

Tues | 7.3 The class NP | HW11 (due Dec 3) Reading: chapters 7.3, 7.4 and 7.5 Exercises: 7.5, 7.7, 7.11, 7.17, 7.19, 7.26
| |

Thurs | 7.4 NP-completeness, SAT is NP-complete | ||

13 |
| ||

Tues | 7.5 SAT is NP-complete continued, additional NP-complete problems | ||

Thurs | Thanksgiving Break | ||

14 |
| ||

Tues | 7.5 Additional NP-complete problems cont’d (e.g., VC, Ham Path, Subset Sum) | HW12 (due Dec 10) Exercises: 7.27, 7.29, 7.34 See hints posted to moodle! Please complete a course evaluation here: | |

Thurs | Space Complexity | ||

15 | 8.1 Savitch’s Theorem | ||

Tues | 8.2 PSPACE | ||

Thurs | 8.3 PSPACE-completeness | ||

Tues | The Poly-time Hierarchy Wrap-up | Take-home Final Exam due by noon on Dec 22. | |

The Connecticut College Honor Code

Academic integrity is of the utmost importance in maintaining the high standards of scholarship in our community. Academic dishonesty is considered to be a serious offense against the community and represents a significant breach of trust between the professor, the classmates, and the student. There are many forms of academic dishonesty including plagiarism, submitting the same work in two courses without prior approval, unauthorized discussion or distribution of exams or assignments, and offering or receiving unauthorized aid on exams or graded assignments. Students violating the Honor Code may be referred to the college's Honor Council for resolution.

Title IX Statement

As a faculty member, I am deeply invested in the well-being of each student I teach. I am here to assist you with your work in this course. If you come to me with other non-course-related concerns, I will do my best to help.

It is important for you to know that all faculty members are mandated reporters of any incidents of gender-based discrimination. This means that I cannot keep information confidential about sexual misconduct, intimate partner violence, stalking, or other forms of gender-based discrimination. Darcie Folsom, the Director of Sexual Violence Prevention and Advocacy, can advise you confidentially as can Counseling Services and any of the College chaplains. Darcie can also help you access other resources on campus and in the local community. You can reach Darcie at 860-439-2219 or darcie.folsom@conncoll.edu, and her office is in Cro 222.

The student sexual misconduct, intimate partner violence, stalking, and non-discrimination policies are in the Student Handbook, which can be found on Camelweb, in the “Documents/Policies” section, under the Student Life section. There you will find the policies, definitions, procedures and resources.

Academic Resource Center

The Academic Resource Center (ARC) offers services to support your academic work such as study skills workshops, time management, coaching and tutoring. Our offices are located on the second floor of Shain Library. Please visit us or call 860-439-5294 for more information or to schedule an appointment.

Writing Center

The Roth Writing Center provides one-to-one peer tutoring (free of charge) to help student writers of all abilities during all stages of the writing process. To make an appointment, call 860-439-2173 or stop by the Writing Center at 214 Blaustein. If you're a confident, experienced writer we can help you to push your ideas and polish your style; if you're a relatively inexperienced and not-so-confident writer we can also help you, by working on grammar or organization or whatever you need. Writing Center tutors are trained to help you to discover what you think through writing. Working with a tutor gives you the opportunity to share your work-in-progress with an actual reader, so that you can get useful feedback on that work before you have to turn it in for a final grade. For further information, visit the Writing Center web page at http://write.conncoll.edu/.

Office of Student Accessibility Services

If you have a physical, mental or learning disability, either hidden or visible, which may require classroom, test-taking, or other reasonable modifications, please see me as soon as possible. If you have not already done so, please be sure to register with the Office of Student Accessibility Services. You can do so by going to the Office of Student Accessibility Services, which is located in the Academic Resource Center (ARC) on the second floor of Shain Library in Room 236, or by contacting the Office at 860-439-5240 or 860-439-5428, or by email to sas@conncoll.edu.