CSE 4115 F 2009 - Some practice exercises


from Sipser, M., Introduction to the theory of computation ,
7.11, 7.16, 7.17, 7.21, 7.22, 8.6, 8.11, 9.1, 9.6, 9.12
from Arora and Barak, Computational Complexity,
2.7, 2.8, 2.9, 2.14, 5.9a,b