Algorithms & complexity worksheet with answers

What is a brute-force algorithm?

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

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)

What is O(2ⁿ) growth called?

1. ALogarithmic
2. BPolynomial
3. CExponential
4. DLinear

A greedy algorithm:

1. AAlways gives the optimal solution
2. BUses only recursion
3. CMakes the locally best choice at each step
4. DTries every possible solution

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. ABellman–Ford is required in all cases
2. BDijkstra's algorithm
3. CDepth-first search
4. DKruskal's algorithm

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. ANo, because n³ is smaller than n² for large n
2. BYes, but only if n is smaller than 100
3. CYes, because Big O is an upper bound and n² grows no faster than n³
4. DNo, because Big O must always state the exact growth rate of the function

Which bound is correct for log(n!)?

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

Which definition of the class P is correct?

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