Foundations of Computer Science
Fall 2007

For today you should have:

1) Read from Sipser and answered the questions in notes21.

2) Worked on your CYK parser.

3) Worked on your two-week module.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Prepare for a quiz on time complexity.

3) Work on your two-week module.


Reading questions
-----------------

Sipser, pages 283-295 and some of Chapter 5.

1) What's a gadget?




[Read the proof of Theorem 7.44 carefully, then skim the other
proofs in Section 7.5.]


2) Make a list of the problems in Chapter 7 that are shown to be
   NP-complete.  For each problem write a short description of
   what the problem is and the technique used to prove its
   NP-completeness.


3) Do exercise 7.10 on page 295, "Show that ALL_{DFA} is in P."




[Go back to page 197 and read the proof that ALL_{CFG} is undecidable.]

3) Do exercise 5.1 on page 211, "Show that EQ_{CFG} is undecidable."



4) Do problem 5.16 on page 212, (The busy beaver function).