Algorithms & complexity worksheet with answers

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. AHeap sort
2. BQuicksort
3. CMerge sort
4. DBubble sort

What is the base case of a recursive function?

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

What is the running time of counting sort for n integers in the range 0 to k?

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

What does it mean that a problem has optimal substructure?

1. AThe problem has exactly one optimal solution, which every subproblem shares
2. BEvery subproblem has the same size
3. CThe problem can be solved in constant time
4. DAn optimal solution can be built from optimal solutions of its subproblems

Breadth-first search on an unweighted graph finds:

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

What does the recurrence T(n) = T(n − 1) + O(1) solve to?

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

What would follow if someone found a polynomial-time algorithm for one NP-complete problem?

1. AEvery problem in NP could be solved in polynomial time, so P = NP
2. BAll exponential-time algorithms would immediately run in linear time
3. CThe halting problem would become decidable
4. DOnly that one problem would move into P

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(n log n) per increment
3. CO(1) per increment
4. DO(log n) per increment