Algorithms & complexity worksheet with answers

What is memoisation?

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

A problem is usually called tractable if:

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

What is the base case of a recursive function?

1. AThe case with the largest input, which is handled before any recursive calls
2. BThe call that uses the most memory
3. CThe first line of the function
4. DA case that is answered directly without making another recursive call

Why does dynamic programming give no real speed-up for merge sort?

1. AIts subproblems do not overlap, so there is nothing to reuse
2. BMerge sort has no recursive structure
3. CDynamic programming only works on graph problems, not on arrays
4. DMerge sort is already O(n)

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

The time complexity of naive recursive Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. ALogarithmic
2. BExponential
3. CLinear
4. DConstant

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

1. AThe 0/1 knapsack, where items must always be taken whole
2. BBoth variants
3. CThe fractional knapsack, where items may be split
4. DNeither variant

Which statement about P and NP is correct?

1. AIt has been proven that P ≠ NP
2. BNP means "not polynomial"
3. CEvery problem in P is also in NP
4. DNP problems cannot be verified quickly