Algorithms & complexity worksheet with answers

Free printable Algorithms & complexity worksheet: 8 problems from easy to exam level, with an answer key. Print it or save it as a PDF.

New worksheetPractise online with hints

For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.

Name: ____________________   Date: ____________

1.Easy

What is the base case of a recursive function?

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

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

  1. AMerge sort
  2. BQuicksort
  3. CInsertion sort
  4. DBubble sort
3.Easy

A problem is usually called tractable if:

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

What does amortised analysis measure?

  1. AThe expected cost over random inputs
  2. BThe cost of an algorithm on the best input
  3. CThe average cost per operation over a worst-case sequence of operations
  4. DThe cost of the single most expensive operation anywhere in the sequence
5.Medium

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

  1. AGreedy uses 3 coins; the optimum is 2
  2. BGreedy uses 3 coins; the optimum is 3
  3. CGreedy uses 4 coins; the optimum is 3
  4. DGreedy uses 2 coins; the optimum is 2
6.Medium

Is it correct to say that an O(n²) algorithm is also O(n³)?

  1. ANo, because n³ is smaller than n² for large n
  2. BYes, because Big O is an upper bound and n² grows no faster than n³
  3. CNo, because Big O must always state the exact growth rate of the function
  4. DYes, but only if n is smaller than 100
7.Hard

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

  1. AYes, the lower bound is therefore wrong
  2. BNo, the lower bound applies to the worst case over all inputs, not to every input
  3. CYes, but only for arrays shorter than 100
  4. DNo, because insertion sort is not a comparison sort
8.Hard

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

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

Answer key

  1. 1. A · A case that is answered directly without making another recursive call
  2. 2. B · Quicksort
  3. 3. A · It can be solved in polynomial time
  4. 4. C · The average cost per operation over a worst-case sequence of operations
  5. 5. A · Greedy uses 3 coins; the optimum is 2
  6. 6. B · Yes, because Big O is an upper bound and n² grows no faster than n³
  7. 7. B · No, the lower bound applies to the worst case over all inputs, not to every input
  8. 8. D · X is in NP, and a known NP-complete problem reduces to X in polynomial time

Full step-by-step solutions: practise this topic on examproblems.com.