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

Which notation describes an upper bound on growth?

  1. ABig Theta
  2. BLittle omega
  3. CBig Omega
  4. DBig O
2.Easy

What is O(2ⁿ) growth called?

  1. APolynomial
  2. BLogarithmic
  3. CExponential
  4. DLinear
3.Easy

A problem is usually called tractable if:

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

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

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

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

  1. AO(2m+n)
  2. BO(mn)
  3. CO(mn log n)
  4. DO(m + n)
6.Medium

Which sorting algorithm is stable?

  1. AQuicksort (typical in-place version)
  2. BMerge sort
  3. CSelection sort (typical version)
  4. DHeap sort
7.Hard

Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

  1. APrim's algorithm starting from one node
  2. BKruskal's algorithm
  3. CDijkstra's algorithm
  4. DFloyd–Warshall
8.Hard

Taking both endpoints of every edge in a maximal matching gives a vertex cover. How good is this cover?

  1. AAt most twice the size of a minimum vertex cover
  2. BAt most log n times the minimum
  3. CAlways a minimum vertex cover
  4. DOf unknown quality compared to the optimum

Answer key

  1. 1. D · Big O
  2. 2. C · Exponential
  3. 3. D · It can be solved in polynomial time
  4. 4. D · O(n)
  5. 5. B · O(mn)
  6. 6. B · Merge sort
  7. 7. B · Kruskal's algorithm
  8. 8. A · At most twice the size of a minimum vertex cover

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