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 binary search require of its input?

  1. AThe array must contain only positive numbers
  2. BThe array must be sorted
  3. CThe array must have no more than 1000 elements
  4. DThe array length must be a power of two
2.Easy

What is the time complexity of depth-first search on a graph stored as adjacency lists?

  1. AO(V × E)
  2. BO(E log V)
  3. CO(V + E)
  4. DO(V²)
3.Easy

What is recursion?

  1. AA loop that never ends
  2. BA type of data structure
  3. CA function that calls itself on smaller inputs
  4. DA sorting method
4.Medium

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

  1. AO(log n)
  2. BO(1)
  3. CO(n)
  4. DO(n log n)
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 3
  2. BGreedy uses 2 coins; the optimum is 2
  3. CGreedy uses 3 coins; the optimum is 2
  4. DGreedy uses 4 coins; the optimum is 3
6.Medium

How does Prim's algorithm build a minimum spanning tree?

  1. AIt runs breadth-first search and keeps the BFS tree
  2. BIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree
  3. CIt removes the most expensive edge until no cycles remain
  4. DIt sorts all edges by weight and adds each one unless it would form a cycle in the forest
7.Hard

How is the travelling salesman problem classified?

  1. AThe decision version is in P but the optimisation version is NP-complete
  2. BIt is in P because Dijkstra's algorithm solves it by visiting every city once
  3. CThe decision version is NP-complete and the optimisation version is NP-hard
  4. DIt is undecidable
8.Hard

Why does binary search not give O(log n) time on a singly linked list?

  1. AComparisons on linked list nodes are slower
  2. BReaching the middle element takes O(n) steps, since there is no direct index access
  3. CBinary search needs at least twice the memory
  4. DLinked lists cannot be sorted

Answer key

  1. 1. B · The array must be sorted
  2. 2. C · O(V + E)
  3. 3. C · A function that calls itself on smaller inputs
  4. 4. A · O(log n)
  5. 5. C · Greedy uses 3 coins; the optimum is 2
  6. 6. B · It grows one tree from a start vertex, adding the cheapest edge that leaves the tree
  7. 7. C · The decision version is NP-complete and the optimisation version is NP-hard
  8. 8. B · Reaching the middle element takes O(n) steps, since there is no direct index access

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