CS 5315, Final Exam, Tuesday, May 12, 2015


(Please do not forget to put your name on all extra sheets of paper)

1. Primitive recursive functions -- a formalization of for-loops:

2. Beyond primitive recursive functions:

3. Computable sets and functions:

4. Turing machines:

5. Feasible and not feasible: definitions

6. Reductions from the NP-hardness proof Reduce the satisfiability problem for the formula
(x1 \/ ~x2) & (~x1 \/ x3) & (x1 \/ x2 \/ ~x3) to:

7. Kolmogorov complexity:

8-9. Parallelization and beyond: A straightforward algorithm takes time O(n) to compute the sum of n numbers.

10. Projects: