Algorithms & complexity worksheet with answers

A problem is usually called tractable if:

1. AIt has no solution
2. BIt can only be solved by trying every possibility
3. CIt can be solved in constant time
4. DIt can be solved in polynomial time

What is a brute-force algorithm?

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

What does the worst-case running time of an algorithm describe?

1. AThe maximum time it takes over all inputs of size n
2. BThe time it takes on a slow computer
3. CThe time it takes on the smallest input
4. DThe expected time it takes on a random input of size n

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

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

Dynamic programming is useful when a problem has:

1. ANo subproblems at all, so it can be solved in one step
2. BOverlapping subproblems and optimal substructure
3. COnly random inputs
4. DA single loop

What is the time complexity of: for i = 1 to n: for j = 1 to i: do O(1) work?

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

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

1. AAfter V − 1 rounds, it checks whether any edge can still be relaxed
2. BIt checks whether any edge has a negative weight
3. CIt counts the cycles with depth-first search
4. DIt runs Dijkstra's algorithm twice and compares the two distance results

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

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