Foundations of Computer Science
Fall 2007

For today you should have:

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

2) Chosen a topic for your two-week module.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Enjoy the break.


A little foreshadowing
----------------------

1) Write a Python function that evaluates F, where F(0)=1,
   F(1)=1, and F(n) = F(n-1) + F(n-2).

   Start with a naive recursive version.  What is the run time
   of this algorithm as a function of n?

   How many times does it evaluate F(0)?

   There are two standard ways to improve this solution.

2) Write an iterative version of your function that uses a list
   or dictionary to store F(i) for i from 0 up to n.

   How many times does each entry get read?

   This is a one dimensional version of a technique called
   "dynamic programming" that we will return to after break.


3) Write a recursive version of your function using a global
   list or dictiory to store previously-computed results.

   This technique is called "memoization".

   A couple of stupid Python tricks: 
   
   a) use an optional parameter to store the "hints"
   
   b) use try..except to check for hints


4) What are the pros and cons of dynamic programming and memoization?


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

Sipser, pages 256-270.


1) What is Sipser's explanation for the decision to draw a bright
   line between polynomial time algorithms and non-polynomial time algs?



2) Why does Sipser say that a brute force search for the factors
   of n is exponential time?  Isn't it linear in n?



3) Why is unary an "unreasonable" encoding?



4) What is dynamic programming?



5) If we have not been able to find a polynomial time algorithm
   for a problem, what can we conclude about the intrinsic difficulty
   of the problem?



6) Why is NP considered a class of problems rather than just a bunch
   of problems that don't have polynomial time algorithms yet?



7) What is polynomial verifiability?  What is a certificate?



8) What does NP stand for?



9) What proof technique is used to prove Theorem 7.20?



10) In general how do you prove that a problem is in NP?



11) P = NP?