CSE 409 ( Theory of Computation)

Spring 2008

When and where	Tue, Thr, & 1:10 pm - 2:25 pm, Room  Christmas Saucon XS 303
Instructor	Héctor Muñoz-Avila, munoz@cse.lehigh.edu
Instructor's office hours	Wed, 4:00PM-5:00PM, Room 252 Packard Lab

Texts

Required:

Michael Sipser Introduction to the Theory of Computation (Second Edition)

Announcements

** We covered part of Chapter 7 only:

• Section 7.1 excluding Definition 7.5, Turing machine M2 and follow-up discussion, and Theorem 7.8
• Section 7.2 excluding all of "Examples of Problems in P"
• Section 7.3. We used the result of Theorem 7.20 as the definition for a language being in NP (i.e., a language L is in NP if there is a non-deterministic Turing machine N that decides L and N runs in polynomial time) instead of the Definition 7.18. We covered neither Definition 7.18 nor the proof of Theorem 7.20. We didn't covered any of the "Examples of Problems in NP".
• Section 7.4 excluding Theorem 7.27, Theorem 7.32, Theorem 7.37 and the rest of that section
• Section 7.5 was not covered.

** OPTIONAL Homework (April 24):

• The following problems have short proofs. Please write these proofs carefully.
  • Show that P is a subset of NP
  • Show that P is closed under union and concatenation
  • Show that NP is closed under union and concatenation
  • Show that if A is polynomial-time reducible into B, and B is in P, then A must be in P.
  • Show that if one is able to show that an NP-complete problem (e.g., SAT) is not in P, then every other NP-complete problem is also not in P
  • Show that the Hamiltonian cycle can be polynomial-time reduced into the Hamiltonian path. What is the difficulty of doing the polynomial-time reduction the other way around? (note: both are defined in the book).

** Note about the final exam: It will cover all of the topics covered in the course. At least 35% of the test will be about topics covered after Test # 2: Reducability (Chapter 5) and Computational Complexity (Chapter 7).

** Extra credit: At the time of the final exam and once you have completed the final exam and turned it in, you will have the option to request that I hand to you 2 extra questions; the first question will be on the topic of regular and context-free languages (Chapters 1 and 2). The second question will be on the topic of Turing machines, decidability and undecidability (Chapters 3 and 4). Note that you have to prepare for these topics anyway for the final exam. You will be given the opportunity to answer these 2 extra questions and be given extra time for this. Each of these questions can give up to 8/80 extra points for the grades of Test # 1 and Test # 2 respectively. However, these extra points will be added only if the score of your final exam is at least 70/100.

Topics covered so far

• Introduction
• Math background (Chapter 0)
• Finite Automata (Section 1.1)
• Nondeterminism (section 1.2)
• Regular expressions and non-regular languages (Sections 1.3 and 1.4)
• Context-free languages (Section 2.1)
• Pushdown automata (Section 2.2)
• Non context-free languages (Section 2.3)
• Turing machines (Section 3.1)
• Extensions to Turing machines (Section 3.2)
• Notion of algorithm (Section 3.3)
• Decidable and undecidable languages (Chapter 4)
• Undecidable problems from language theory (Section 5.1)
• Section 5.2: Discussion preceeding Theorem 5.15 but not actual proof of Theorem 5.15
• Mapping reducibility (Section 5.3)
• We covered part of Chapter 7 only:
  • Section 7.1 excluding Definition 7.5, Turing machine M2 and follow-up discussion, and Theorem 7.8
  • Section 7.2 excluding all of "Examples of Problems in P"
  • Section 7.3. We used the result of Theorem 7.20 as the definition for a language being in NP (i.e., a language L is in NP if there is a non-deterministic Turing machine N that decides L and N runs in polynomial time) instead of the Definition 7.18. We covered neither Definition 7.18 nor the proof of Theorem 7.20. We didn't covered any of the "Examples of Problems in NP".
  • Section 7.4 excluding Theorem 7.27, Theorem 7.32, Theorem 7.37 and the rest of that section
  • Section 7.5 was not covered.

Communication

All announcements, handouts, etc. will be posted in this web site:

www.cse.lehigh.edu/~munoz/CSE409

Homework

There will be written homework assignments.  These are to be handed to the instructor at the beginning of the class.

We will follow an Active Learning approach; homework will be due before the material is covered in class.

Volunteers will be seeked to solve the homework assignement. This will always give extra-credit.

Attendance

Attendance to classes is required.

Exams

There will be two tests and a final exam.

Exams will not be repeated. Unless an extreme situation occur, failure to present a test will result in 0 points. If an extreme situation does occur causing a person not to present an exam, the average of the score in the other two exams will be assigned as score for the missing exam.

Exams will be with open book but no other notes are allowed. The best preparation for the exam (aside from actively following the material) is to try to do each of the exercises/problems in the book for which an answer is provided in the book.

Cheating

You're responsible for doing your own work on all assignments and exams. Copying other people's work is cheating, and if I catch you doing it I'll report it to the honors council.

Grading

Exams:                    80% (Test # 1: 25%, Test # 2: 25%, Final Exam: 30%)
Homework:   20%
 

Last update: Thur. Feb. 7 18:17:57 EDT 2007