Algorithms & complexity worksheet with answers

A loop starts with i = 1 and doubles i each iteration until i > n. How many iterations does it run?

1. AAbout n²
2. BAbout n
3. CAbout n / 2
4. DAbout log₂ n

What does the worst-case running time of an algorithm describe?

1. AThe time it takes on the smallest input
2. BThe time it takes on a slow computer
3. CThe expected time it takes on a random input of size n
4. DThe maximum time it takes over all inputs of size n

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

1. A2 seconds
2. B1 second
3. C4 seconds
4. D8 seconds

What does amortised analysis measure?

1. AThe average cost per operation over a worst-case sequence of operations
2. BThe expected cost over random inputs
3. CThe cost of an algorithm on the best input
4. DThe cost of the single most expensive operation anywhere in the sequence

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

1. AGreedy uses 2 coins; the optimum is 2
2. BGreedy uses 4 coins; the optimum is 3
3. CGreedy uses 3 coins; the optimum is 3
4. DGreedy uses 3 coins; the optimum is 2

Dynamic programming is useful when a problem has:

1. AOnly random inputs
2. BOverlapping subproblems and optimal substructure
3. CNo subproblems at all, so it can be solved in one step
4. DA single loop

How is the travelling salesman problem classified?

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

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

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