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 n
3. CAbout log₂ n
4. DAbout n / 2

What is O(2ⁿ) growth called?

1. ALinear
2. BExponential
3. CLogarithmic
4. DPolynomial

What is the base case of a recursive function?

1. AThe case with the largest input, which is handled before any recursive calls
2. BThe first line of the function
3. CA case that is answered directly without making another recursive call
4. DThe call that uses the most memory

How many levels does the recursion of merge sort have for an array of n elements?

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

Breadth-first search on an unweighted graph finds:

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

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

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

Topological sorting is possible only for:

1. AGraphs with negative weights
2. BComplete graphs
3. CUndirected graphs
4. DDirected acyclic graphs

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

1. AIt counts the cycles with depth-first search
2. BIt runs Dijkstra's algorithm twice and compares the two distance results
3. CIt checks whether any edge has a negative weight
4. DAfter V − 1 rounds, it checks whether any edge can still be relaxed