Algorithms & complexity worksheet with answers

How does selection sort work?

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

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(E log V)
4. DO(V²)

A loop starts with i = 1 and doubles i each iteration until i > n. How many iterations does it run?

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

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

Dynamic programming is useful when a problem has:

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

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(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt is undecidable
2. BIt is NP-hard
3. CIt can be solved by Dijkstra's algorithm with negated weights
4. DIt is always solvable in O(V + E)

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AHash functions are slow
2. BArrays have O(n) access
3. CKeys must be sorted first
4. DMany keys may collide into the same bucket