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. B2 seconds
3. C8 seconds
4. D4 seconds

How does selection sort work?

1. AIt splits the array in halves and merges them
2. BIt inserts each element into a growing sorted part by shifting
3. CIt repeatedly finds the minimum of the unsorted part and swaps it to the front
4. DIt repeatedly swaps neighbouring elements that are in the wrong order

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

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

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

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

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

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

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

Which of these satisfiability problems is known to be solvable in polynomial time?

1. AGeneral SAT on formulas in conjunctive normal form
2. B3-SAT, where each clause has exactly three literals
3. C2-SAT, where each clause has at most two literals
4. DCircuit satisfiability

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

1. ANeither variant
2. BThe 0/1 knapsack, where items must always be taken whole
3. CBoth variants
4. DThe fractional knapsack, where items may be split