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 a brute-force algorithm?

  1. AOne that runs on many processors
  2. BOne that tries all possible candidate solutions
  3. COne that guesses an answer at random
  4. DOne that always uses recursion
2.Easy

What is the running time of counting sort for n integers in the range 0 to k?

  1. AO(n²)
  2. BO(n log n)
  3. CO(k log n)
  4. DO(n + k)
3.Easy

What is the worst-case time complexity of insertion sort?

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

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

Dynamic programming is useful when a problem has:

  1. ANo subproblems at all, so it can be solved in one step
  2. BOnly random inputs
  3. COverlapping subproblems and optimal substructure
  4. DA single loop
7.Hard

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

  1. AO(V³)
  2. BO((V + E) log V)
  3. CO(V × E)
  4. DO(V + E)
8.Hard

What did the Cook–Levin theorem establish?

  1. AP is not equal to NP
  2. BEvery NP problem can be solved in exponential time
  3. CThe halting problem is undecidable
  4. DThe Boolean satisfiability problem (SAT) is NP-complete

Answer key

  1. 1. B · One that tries all possible candidate solutions
  2. 2. D · O(n + k)
  3. 3. C · O(n²)
  4. 4. C · O(n)
  5. 5. A · O(n log n)
  6. 6. C · Overlapping subproblems and optimal substructure
  7. 7. B · O((V + E) log V)
  8. 8. D · The Boolean satisfiability problem (SAT) is NP-complete

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