Algorithms & complexity worksheet with answers

Space complexity measures:

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

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

What is O(2ⁿ) growth called?

1. ALinear
2. BLogarithmic
3. CPolynomial
4. DExponential

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms are always rounded to integers
2. BThe base only matters for small n
3. CAll logarithms in computer science have base 10, so it is implied
4. DLogarithms with different bases differ only by a constant factor

What is the running time of LSD radix sort on n integers with d digits in base k?

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

What does it mean that a problem has optimal substructure?

1. AThe problem can be solved in constant time
2. BThe problem has exactly one optimal solution, which every subproblem shares
3. CAn optimal solution can be built from optimal solutions of its subproblems
4. DEvery subproblem has the same size

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX reduces to a problem in P, and X is in NP
2. BX has no polynomial algorithm, and X is decidable
3. CX is in NP, and a known NP-complete problem reduces to X in polynomial time
4. DX is in P, and X reduces to SAT

Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

1. ADijkstra's algorithm
2. BFloyd–Warshall
3. CPrim's algorithm starting from one node
4. DKruskal's algorithm