Foundations of Computer Science
Fall 2007

For today you should have:

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

2) Worked on your two-week module.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Work on your CYK parser.

3) Work on your two-week module.


More dynamic programming
------------------------

1) Read the wikipedia page on "dynamic programming"

2) As an example, let's implement the Cocke-Younger-Kasami (CYK)
   algorithm for recognizing a CFL.

   Read the wikipedia page on "CYK algorithm"

   Does this algorithm remind you of anything we've seen?

   Can you convince yourself that this algorithm is n^3?

3) Write a Python program that implements CYK for the CFG of
   your choice.

   (Note that you will have to convert to CNF.  To start, choose
   a language that does not include the empty string.)

   You might want to start with my (or your) parzzer:

   http://wb/focs/code/parzzer.py

   A couple of Python tricks that might be helpful:

   a) If your implementation of P is a dictionary that maps
      to a boolean, you could use a set instead, where being
      in the set means it maps to True.

   b) Or you could use a "default dictionary" which returns
      a default value if you ask for a non-existent key:

      class ddict(dict):
          def __missing__(self, key):
	      return False

4) Test your parser with a few strings that you know are in
   or out of the language.

5) (Optional) Extend your implementation to handle the case
   where the start symbol can generate the empty string.

6) (Optional) Extend your implementation to build a parse tree.

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

Sipser, pages 270-283.


1) Why is NP-completeness a useful concept?



2) If A is poly-time reducible to B, does that mean that if we can
   solve A in poly-time, then we can solve B in poly-time?



3) If 3SAT is poly-time reducible to CLIQUE, what does the function
   f(w) take as a parameter and what does it produce?



4) What are the two requirements for NP-completeness?



5) What's the hard way to prove that a problem is NP-complete?
   What's the easy (ok, easier :) way?



6) What do the rows of a tableau represent?  What is an "accepting"
   tableau?  What does it mean if there is an accepting tableau
   for machine N and input w?



7) If any NP machine can be reduced to SAT, what does the function
   f take as a parameter and what does it return?



8) What are the requirements of a legal tableau?



9) How does the generated formula (phi) check that the tableau
   is accepting?



10) Do exercise 7.5 on page 294, "Is the following formula satisfiable?"



11) Do exercise 7.6 on page 294, "Show that P is closed..."



12) Do problem 7.15 on page 295, "Show that NP is closed..."

    [Feel free to read the answer, but think about it first!]