Algorithms & complexity worksheet with answers

What are the three steps of a divide-and-conquer algorithm?

1. ADivide, conquer, combine
2. BRead, compute, write
3. CGuess, check, repeat
4. DSort, search, return

Space complexity measures:

1. AThe disk space of the program file once it is compiled
2. BThe physical size of the computer
3. CThe amount of memory an algorithm needs as input grows
4. DThe number of lines of code

An algorithm's running time is O(n). What is this growth called?

1. AConstant
2. BLogarithmic
3. CQuadratic
4. DLinear

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. ABellman–Ford is required in all cases
2. BKruskal's algorithm
3. CDijkstra's algorithm
4. DDepth-first search

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

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

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 shortest activity first
3. CPick the activity that starts earliest
4. DPick the activity with the fewest overlaps first, then repeat with the compatible ones

How is the travelling salesman problem classified?

1. AThe decision version is in P but the optimisation version is NP-complete
2. BThe decision version is NP-complete and the optimisation version is NP-hard
3. CIt is in P because Dijkstra's algorithm solves it by visiting every city once
4. DIt is undecidable

What does the recurrence T(n) = 2T(n/2) + n log n solve to?

1. AΘ(n)
2. BΘ(n log² n)
3. CΘ(n²)
4. DΘ(n log n)