Department of Computer Science
Comprehensive Core Examination
Fall 2004  
CSCI 356


1.
a) Explain the "divide and conquer" algorithm design strategy
b) Explain how Strassen applied it to the matrix problem.  (You don't have to remember the specific equations involved, but just their important properties.)
c) What is the asymptotic time complexity of the classical matrix multiplication algorithm?
d) Of Strassen's algorithm?

2.
a) Explain the difference between the algorithmic types of the greedy method and dynamic programming.

3. 
a) Define NP completeness
b) State Cook's Theorem
c) List 3 NP complete problems

4.
a) Let L1 and L2 be two decision problems.  What does it mean to say that L1 reduces to L2 in deterministic polynomial time?
b) How would you use the concept of reduction to add to the set of known NP-complete problems?