Algorithms & complexity worksheet with answers

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

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

What is an algorithm?

1. AAny computer program that has a graphical interface
2. BA finite sequence of well-defined steps that solves a problem
3. CA data structure that stores numbers
4. DA programming language designed for writing mathematical formulas

What is the running time of counting sort for n integers in the range 0 to k?

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

A greedy algorithm:

1. AUses only recursion
2. BMakes the locally best choice at each step
3. CTries every possible solution
4. DAlways gives the optimal solution

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

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

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the activity that starts earliest
2. BPick the shortest activity first
3. CPick the activity that finishes earliest, then repeat with the compatible ones
4. DPick the activity with the fewest overlaps first, then repeat with the compatible ones

What would follow if someone found a polynomial-time algorithm for one NP-complete problem?

1. AAll exponential-time algorithms would immediately run in linear time
2. BOnly that one problem would move into P
3. CThe halting problem would become decidable
4. DEvery problem in NP could be solved in polynomial time, so P = NP

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

1. ABecause the algorithm is randomised and its running time varies with each input
2. BBecause n is always small
3. CW is a number, so the time is exponential in the number of bits used to write W
4. DBecause it only works for W = 0