Algorithms & complexity worksheet with answers

Which design strategy does merge sort use?

1. ADivide and conquer
2. BBrute force
3. CDynamic programming
4. DGreedy choice

How does selection sort work?

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

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

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

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

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

How does Prim's algorithm build a minimum spanning tree?

1. AIt sorts all edges by weight and adds each one unless it would form a cycle in the forest
2. BIt removes the most expensive edge until no cycles remain
3. CIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree
4. DIt runs breadth-first search and keeps the BFS tree

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

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

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

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. AChoosing the pivot uniformly at random
2. BUsing recursion only on the left side
3. CSorting the input before running quicksort
4. DAlways choosing the first element