Algorithms & complexity worksheet with answers

An O(n²) algorithm takes 1 second for n = 1000. About how long does it take for n = 2000?

1. A1 second
2. B4 seconds
3. C2 seconds
4. D8 seconds

Which notation describes an upper bound on growth?

1. ALittle omega
2. BBig Omega
3. CBig O
4. DBig Theta

What is memoisation?

1. AConverting recursion into an equivalent loop automatically so no call stack is needed
2. BStoring the results of function calls so repeated calls are answered from memory
3. CWriting comments next to each line of code
4. DFreeing memory after a function returns

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. ADijkstra's algorithm
2. BDepth-first search
3. CBellman–Ford is required in all cases
4. DKruskal's algorithm

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

1. AO(n!)
2. BO(2^n²)
3. CO(n³)
4. DO(n² 2ⁿ)

To show that a new problem X is NP-hard, what must you do?

1. AShow that X can be verified in polynomial time
2. BReduce a known NP-hard problem to X in polynomial time
3. CShow that X has no polynomial algorithm for small inputs
4. DReduce X to a known NP-hard problem in polynomial time