Algorithms & complexity worksheet with answers

What is the running time of counting sort for n integers in the range 0 to k?

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

What is a brute-force algorithm?

1. AOne that guesses an answer at random
2. BOne that always uses recursion
3. COne that runs on many processors
4. DOne that tries all possible candidate solutions

What is the base case of a recursive function?

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

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(V × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V³ × E)

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

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

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

1. AΘ(n³)
2. BΘ(n^{log₂ 3}), about n^1.585
3. CΘ(n log n)
4. DΘ(n²)

How is the travelling salesman problem classified?

1. AIt is in P because Dijkstra's algorithm solves it by visiting every city once
2. BThe decision version is NP-complete and the optimisation version is NP-hard
3. CIt is undecidable
4. DThe decision version is in P but the optimisation version is NP-complete