Algorithms & complexity worksheet with answers

Which design strategy does merge sort use?

1. ABrute force
2. BDynamic programming
3. CDivide and conquer
4. DGreedy choice

What is the time complexity of depth-first search on a graph stored as adjacency lists?

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

Which notation describes a lower bound on growth?

1. AΩ (Big Omega)
2. BO (Big O)
3. CΘ (Big Theta)
4. Do (little o)

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array whose elements are all different
2. BAn array of length 2
3. CAn array in random order
4. DAn array that is already sorted

Breadth-first search on an unweighted graph finds:

1. AShortest paths in graphs that contain negative edge weights
2. BThe minimum spanning tree
3. CShortest paths in number of edges from the start node
4. DA topological order in all graphs

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

1. AExponential
2. BLogarithmic
3. CLinear
4. DConstant

How is the travelling salesman problem classified?

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

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n³)