Algorithms & complexity worksheet with answers

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

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

Which complexity class grows fastest for large n?

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

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

1. A8 seconds
2. B2 seconds
3. C1 second
4. D4 seconds

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

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

Breadth-first search on an unweighted graph finds:

1. AThe minimum spanning tree
2. BShortest paths in graphs that contain negative edge weights
3. CA topological order in all graphs
4. DShortest paths in number of edges from the start node

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

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

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

1. AKruskal's algorithm
2. BDijkstra's algorithm
3. CFloyd–Warshall
4. DPrim's algorithm starting from one node

Taking both endpoints of every edge in a maximal matching gives a vertex cover. How good is this cover?

1. AOf unknown quality compared to the optimum
2. BAlways a minimum vertex cover
3. CAt most twice the size of a minimum vertex cover
4. DAt most log n times the minimum