Algorithms & complexity worksheet with answers

How does selection sort work?

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

What is the best-case time complexity of insertion sort, on an already sorted array?

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

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

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

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 2 coins; the optimum is 2
2. BGreedy uses 3 coins; the optimum is 2
3. CGreedy uses 4 coins; the optimum is 3
4. DGreedy uses 3 coins; the optimum is 3

The time complexity of naive recursive Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. ALogarithmic
2. BExponential
3. CLinear
4. DConstant

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

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

Topological sorting is possible only for:

1. AUndirected graphs
2. BGraphs with negative weights
3. CDirected acyclic graphs
4. DComplete graphs

Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

1. AFloyd–Warshall
2. BPrim's algorithm starting from one node
3. CDijkstra's algorithm
4. DKruskal's algorithm