Algorithms & complexity worksheet with answers

What does binary search require of its input?

1. AThe array must be sorted
2. BThe array must have no more than 1000 elements
3. CThe array length must be a power of two
4. DThe array must contain only positive numbers

What does it mean if an operation runs in O(1) time?

1. AIt always takes exactly one second
2. BIt can only be run once
3. CIts running time does not grow with the input size
4. DIt processes exactly one element per second of running time

A problem is usually called tractable if:

1. AIt can only be solved by trying every possibility
2. BIt can be solved in polynomial time
3. CIt can be solved in constant time
4. DIt has no solution

What does it mean that a problem has optimal substructure?

1. AEvery subproblem has the same size
2. BThe problem has exactly one optimal solution, which every subproblem shares
3. CThe problem can be solved in constant time
4. DAn optimal solution can be built from optimal solutions of its subproblems

What is the worst-case time complexity of quicksort?

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(log n)

What does the recurrence T(n) = 2T(n − 1) + O(1) solve to?

1. AO(2ⁿ)
2. BO(n log n)
3. CO(n²)
4. DO(n)

What is the difference between an undecidable problem and an intractable one?

1. AUndecidable problems are in NP, while intractable problems are in P
2. BAn undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow
3. CIntractable problems cannot be solved by any algorithm, while undecidable ones only need exponential time
4. DBoth mean the problem has no algorithm at all

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX is in NP, and a known NP-complete problem reduces to X in polynomial time
2. BX has no polynomial algorithm, and X is decidable
3. CX is in P, and X reduces to SAT
4. DX reduces to a problem in P, and X is in NP