Algorithms & complexity worksheet with answers

What is a brute-force algorithm?

1. AOne that tries all possible candidate solutions
2. BOne that runs on many processors
3. COne that always uses recursion
4. DOne that guesses an answer at random

An O(n) algorithm takes 3 seconds for n = 1 million. About how long does it take for n = 2 million?

1. A3 seconds
2. B6 seconds
3. C12 seconds
4. D9 seconds

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

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

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the activity that starts earliest
2. BPick the activity with the fewest overlaps first, then repeat with the compatible ones
3. CPick the shortest activity first
4. DPick the activity that finishes earliest, then repeat with the compatible ones

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

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

Which sorting algorithm is stable?

1. AQuicksort (typical in-place version)
2. BHeap sort
3. CSelection sort (typical version)
4. DMerge sort

Which statement about selecting the k-th smallest element of an unsorted array is correct?

1. AQuickselect runs in expected O(n), and median-of-medians guarantees O(n) worst case
2. BSelection is only possible in O(n²)
3. CSelection always needs Ω(n log n) because it requires sorting
4. DQuickselect runs in O(log n) worst case, because it recurses on only one side of the pivot

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

1. AO(V³)
2. BO(V + E)
3. CO((V + E) log V)
4. DO(V × E)