Algorithms & complexity worksheet with answers

Space complexity measures:

1. AThe physical size of the computer
2. BThe amount of memory an algorithm needs as input grows
3. CThe number of lines of code
4. DThe disk space of the program file once it is compiled

An algorithm's running time is O(n). What is this growth called?

1. ALinear
2. BQuadratic
3. CConstant
4. DLogarithmic

What is memoisation?

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

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

About how many comparisons does binary search need in the worst case on a sorted array of 1,000,000 elements?

1. AAbout 1,000
2. BAbout 100
3. CAbout 20
4. DAbout 500,000

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

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

How is the travelling salesman problem classified?

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

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt is undecidable
2. BIt is NP-hard
3. CIt can be solved by Dijkstra's algorithm with negated weights
4. DIt is always solvable in O(V + E)