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.

computer_science_major.PNG

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

  never-trust-a-smiling-cat-garfield-9018428-0-1408634746000.jpg

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?

dibujo20090905_p_versus_np_in_the_simpsons_tv_series.jpg

[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
Sept 3

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
Sept 8

1.1 Finite automata

Thurs
Sept 10

1.2 Non-determinism

3

 

Tues
Sept 15

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
Sept 22

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
Sept 29

2.3  Equivalence of CFGs and PDAs

Thurs
Oct 1

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
Oct 6

3.1 Turing machines

Thurs
Oct 8

3.2 Turing machine variants

Week#

Topic

Assignment

7

Tues
Oct 13

3.2-3.3

HW7

Reading:  the rest of chapter 3

Exercises:  3.6, 3.7, 3.18, 3.21

Thurs
Oct 15

3.3

Week#

Topic

Assignment

8

 

Tues
Oct 20

Fall Break

Due on Thurs Oct 29

Take-home, open-book, open-note Midterm Exam on chapters 1-3.

Thurs
Oct 22

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
Oct 27

4.2  Undecidability

Thurs
Oct 29

5.1  The halting problem and other undecidable problems

10

Reducibility

 

Tues
Nov 3

More 5.1 and 5.2

HW9

Reading:  all of chapter 5

Exercises:  5.1, 5.3, 5.9, 5.17

Thurs
Nov 5

5.3  Mapping reducibility

Week#

Topic

Assignment

11

 

Tues
Nov 10

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
Nov 12

7.2 The class P

12

 

Tues
Nov 17

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
Nov 19

7.4 NP-completeness, SAT is NP-complete

13

 

Tues
Nov 24

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

Thurs
Nov 26

Thanksgiving Break

14

 

Tues
Dec 1

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:

http://moodle.conncoll.edu/

Thurs
Dec 3

Space Complexity

 15

8.1  Savitch’s Theorem

Tues
Dec 8

8.2  PSPACE

Thurs
Dec 10

8.3  PSPACE-completeness

Tues
Dec 15

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.