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. AThe call that uses the most memory
  2. BA case that is answered directly without making another recursive call
  3. CThe case with the largest input, which is handled before any recursive calls
  4. DThe first line of the function
2.Easy

What does the average-case running time describe?

  1. AThe expected time over a given distribution of inputs of size n
  2. BThe middle value between the best-case and worst-case running times
  3. CThe time for an input of average length
  4. DThe time on the most common computer
3.Easy

What is an algorithm?

  1. AA data structure that stores numbers
  2. BA finite sequence of well-defined steps that solves a problem
  3. CAny computer program that has a graphical interface
  4. DA programming language designed for writing mathematical formulas
4.Medium

Dynamic programming is useful when a problem has:

  1. AOnly random inputs
  2. BOverlapping subproblems and optimal substructure
  3. CNo subproblems at all, so it can be solved in one step
  4. DA single loop
5.Medium

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

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

What is the running time of LSD radix sort on n integers with d digits in base k?

  1. AO(d(n + k))
  2. BO(dn log k)
  3. CO(n²)
  4. DO(n log n)
7.Hard

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

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

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

  1. ABecause the algorithm is randomised and its running time varies with each input
  2. BBecause it only works for W = 0
  3. CW is a number, so the time is exponential in the number of bits used to write W
  4. DBecause n is always small

Answer key

  1. 1. B · A case that is answered directly without making another recursive call
  2. 2. A · The expected time over a given distribution of inputs of size n
  3. 3. B · A finite sequence of well-defined steps that solves a problem
  4. 4. B · Overlapping subproblems and optimal substructure
  5. 5. A · Yes, because Big O is an upper bound and n² grows no faster than n³
  6. 6. A · O(d(n + k))
  7. 7. D · At most twice the size of a minimum vertex cover
  8. 8. C · W is a number, so the time is exponential in the number of bits used to write W

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