Algorithms & complexity worksheet with answers

What is an algorithm?

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

What does the worst-case running time of an algorithm describe?

1. AThe expected time it takes on a random input of size n
2. BThe maximum time it takes over all inputs of size n
3. CThe time it takes on a slow computer
4. DThe time it takes on the smallest input

What is the base case of a recursive function?

1. AThe call that uses the most memory
2. BThe case with the largest input, which is handled before any recursive calls
3. CA case that is answered directly without making another recursive call
4. DThe first line of the function

Breadth-first search on an unweighted graph finds:

1. AShortest paths in number of edges from the start node
2. BThe minimum spanning tree
3. CA topological order in all graphs
4. DShortest paths in graphs that contain negative edge weights

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

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n log n)