Algorithms & complexity worksheet with answers

What does the average-case running time describe?

1. AThe expected time over a given distribution of inputs of size n
2. BThe middle value between the best-case and worst-case running times
3. CThe time for an input of average length
4. DThe time on the most common computer

An algorithm with two nested loops, each running n times, typically has which complexity?

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

Space complexity measures:

1. AThe disk space of the program file once it is compiled
2. BThe number of lines of code
3. CThe physical size of the computer
4. DThe amount of memory an algorithm needs as input grows

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(mn)

How many levels does the recursion of merge sort have for an array of n elements?

1. AAbout log₂ n
2. BAbout n / 2
3. CAbout n
4. DAbout √n

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

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

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

1. ANegative numbers cannot be stored in a priority queue
2. BA vertex is finalised when extracted, but a later negative edge could still give it a shorter path
3. CIt only works on undirected graphs
4. DIt goes into an infinite loop on every negative edge

Topological sorting is possible only for:

1. AGraphs with negative weights
2. BComplete graphs
3. CUndirected graphs
4. DDirected acyclic graphs