Algorithms & complexity worksheet with answers

Space complexity measures:

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

A problem is usually called tractable if:

1. AIt can be solved in polynomial time
2. BIt can be solved in constant time
3. CIt has no solution
4. DIt can only be solved by trying every possibility

What does it mean if an operation runs in O(1) time?

1. AIt always takes exactly one second
2. BIts running time does not grow with the input size
3. CIt processes exactly one element per second of running time
4. DIt can only be run once

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

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array that is already sorted
2. BAn array of length 2
3. CAn array in random order
4. DAn array whose elements are all different

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

Why does any comparison-based search in a sorted array need Ω(log n) comparisons in the worst case?

1. AEvery element must be compared at least once
2. BA decision tree with n possible outcomes must have depth at least log₂ n
3. CComparisons take logarithmic time each
4. DBinary search is the only possible algorithm, and it needs log₂ n comparisons

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

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