Foundations of Computer Science
Fall 2007

For today you should have:

1) Recovered from the exam :)


For next time, you should:

1) Read from Sipser and answer the questions below.



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

Sipser, pages 247-256.


1) What are all the simplications and approximations used to
   formulate algorithmic analysis?



2) What are the practical consequences of these simplications?



4) In the statement f(n) = O(g(n)), what type is the thing on
   the left side?  What type is the thing on the right side?
   Is this relationship symmetric?



5) What is the difference between TIME(t(n)) and O(t(n))?



6) On page 253, how do we know that we can't decide A any faster
   than n log n?



7) What is a computational model?  Give a few examples?  Why does
   the choice of a model matter?  Why does it not matter?



8) What kind of proof is used to prove Theorem 7.8?



9) Do exercise 7.1 on page 294, "Answer each part TRUE or FALSE:"