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 does f(n) = Θ(g(n)) mean?

  1. Af grows strictly slower than g
  2. Bf grows strictly faster than g
  3. Cf is always smaller than g for every n, so g bounds it from above but never from below
  4. Df grows at the same rate as g, bounded above and below by constant multiples of g
2.Easy

What is memoisation?

  1. AStoring the results of function calls so repeated calls are answered from memory
  2. BFreeing memory after a function returns
  3. CWriting comments next to each line of code
  4. DConverting recursion into an equivalent loop automatically so no call stack is needed
3.Easy

What does the average-case running time describe?

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

What is the worst-case time complexity of quicksort?

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

A greedy algorithm:

  1. AAlways gives the optimal solution
  2. BUses only recursion
  3. CTries every possible solution
  4. DMakes the locally best choice at each step
6.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 3
  2. BGreedy uses 4 coins; the optimum is 3
  3. CGreedy uses 3 coins; the optimum is 2
  4. DGreedy uses 2 coins; the optimum is 2
7.Hard

The halting problem shows that:

  1. ALoops should be avoided
  2. BEvery program eventually halts
  3. CNo algorithm can decide for every program and input whether it halts
  4. DSome programs run faster on faster computers, so halting depends on hardware
8.Hard

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

  1. AIt counts the cycles with depth-first search
  2. BIt checks whether any edge has a negative weight
  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

Answer key

  1. 1. D · f grows at the same rate as g, bounded above and below by constant multiples of g
  2. 2. A · Storing the results of function calls so repeated calls are answered from memory
  3. 3. C · The expected time over a given distribution of inputs of size n
  4. 4. D · O(n²)
  5. 5. D · Makes the locally best choice at each step
  6. 6. C · Greedy uses 3 coins; the optimum is 2
  7. 7. C · No algorithm can decide for every program and input whether it halts
  8. 8. C · After V − 1 rounds, it checks whether any edge can still be relaxed

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