Algorithms & complexity worksheet with answers

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. CA case that is answered directly without making another recursive call
4. DThe call that uses the most memory

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

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

What is O(2ⁿ) growth called?

1. AExponential
2. BLogarithmic
3. CLinear
4. DPolynomial

The lower bound for comparison-based sorting in the worst case is:

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

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

1. AO(n)
2. BO(n²)
3. CO(2ⁿ)
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 with the fewest overlaps first, then repeat with the compatible ones
2. BPick the activity that finishes earliest, then repeat with the compatible ones
3. CPick the activity that starts earliest
4. DPick the shortest activity first

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. AChoosing the pivot uniformly at random
2. BUsing recursion only on the left side
3. CAlways choosing the first element
4. DSorting the input before running quicksort

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX has no polynomial algorithm, and X is decidable
2. BX is in P, and X reduces to SAT
3. CX is in NP, and a known NP-complete problem reduces to X in polynomial time
4. DX reduces to a problem in P, and X is in NP