Algorithms & complexity worksheet with answers

How much extra memory does a standard array-based merge sort use?

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

What is the time complexity of binary search on a sorted array?

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

Why does dynamic programming give no real speed-up for merge sort?

1. AIts subproblems do not overlap, so there is nothing to reuse
2. BMerge sort has no recursive structure
3. CDynamic programming only works on graph problems, not on arrays
4. DMerge sort is already O(n)

What is the running time of LSD radix sort on n integers with d digits in base k?

1. AO(n log n)
2. BO(dn log k)
3. CO(n²)
4. DO(d(n + k))

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. BDepth-first search
3. CDijkstra's algorithm
4. DKruskal's algorithm

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

1. AΘ(n²)
2. BΘ(n^{log₂ 7}), about n^2.81
3. CΘ(n² log n)
4. DΘ(n³)

Which definition of the class P is correct?

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