Algorithms & complexity worksheet with answers

How much extra memory does a standard array-based merge sort use?

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

What is memoisation?

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

How does selection sort work?

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

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

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

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. ARecursive algorithms cannot handle arrays below 10 elements
2. BInsertion sort uses less memory than any other sorting algorithm on large inputs
3. CInsertion sort is O(n log n) in the worst case
4. DInsertion sort has little overhead and is fast on small or nearly sorted inputs

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

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

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

What is the amortised cost of incrementing a binary counter, given that one increment may flip many bits?

1. AO(n) per increment
2. BO(log n) per increment
3. CO(n log n) per increment
4. DO(1) per increment