Algorithms & complexity worksheet with answers

What is memoisation?

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

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

1. A4 seconds
2. B1 second
3. C8 seconds
4. D2 seconds

What is the Big O of 3n² + 5n + 2?

1. AO(n²)
2. BO(5n)
3. CO(3n²)
4. DO(n³)

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

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

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. ANo, because n³ is smaller than n² for large n
2. BNo, because Big O must always state the exact growth rate of the function
3. CYes, but only if n is smaller than 100
4. DYes, because Big O is an upper bound and n² grows no faster than n³

What does the Floyd–Warshall algorithm compute, and how fast?

1. AShortest paths from one source vertex to all others in O(V + E)
2. BA minimum spanning tree in O(E log V)
3. CA topological order in O(V²)
4. DShortest paths between all pairs of vertices in O(V³)

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

1. ANegative numbers cannot be stored in a priority queue
2. BIt goes into an infinite loop on every negative edge
3. CA vertex is finalised when extracted, but a later negative edge could still give it a shorter path
4. DIt only works on undirected graphs

A problem is NP-complete if it is:

1. AIn NP and every NP problem reduces to it in polynomial time
2. BImpossible to solve
3. COutside NP but harder than all NP problems, such as the halting problem
4. DSolvable in polynomial time