Algorithms & complexity worksheet with answers

An algorithm's running time is O(n). What is this growth called?

1. AQuadratic
2. BLinear
3. CLogarithmic
4. DConstant

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 time it takes on the smallest input
3. CThe maximum time it takes over all inputs of size n
4. DThe time it takes on a slow computer

How does selection sort work?

1. AIt repeatedly finds the minimum of the unsorted part and swaps it to the front
2. BIt splits the array in halves and merges them
3. CIt repeatedly swaps neighbouring elements that are in the wrong order
4. DIt inserts each element into a growing sorted part by shifting

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

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

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

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

What does the Floyd–Warshall algorithm compute, and how fast?

1. AShortest paths between all pairs of vertices in O(V³)
2. BA minimum spanning tree in O(E log V)
3. CA topological order in O(V²)
4. DShortest paths from one source vertex to all others in O(V + E)

Which definition of the class P is correct?

1. AProblems that need exponential time on every computer
2. BProblems that can be solved in parallel
3. CProblems whose solutions can be checked but never found in polynomial time
4. DDecision problems solvable by a deterministic algorithm in polynomial time

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 × E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V + E)