Algorithms & complexity worksheet with answers

What does binary search require of its input?

1. AThe array length must be a power of two
2. BThe array must be sorted
3. CThe array must have no more than 1000 elements
4. DThe array must contain only positive numbers

What is the base case of a recursive function?

1. AThe first line of the function
2. BA case that is answered directly without making another recursive call
3. CThe case with the largest input, which is handled before any recursive calls
4. DThe call that uses the most memory

Which of these running times is polynomial?

1. AO(n³)
2. BO(2ⁿ)
3. CO(nⁿ)
4. DO(n!)

Dynamic programming is useful when a problem has:

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

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

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

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

1. AKeys must be sorted first
2. BHash functions are slow
3. CMany keys may collide into the same bucket
4. DArrays have O(n) access

A problem is NP-complete if it is:

1. AIn NP and every NP problem reduces to it in polynomial time
2. BImpossible to solve
3. COutside NP but harder than all NP problems, such as the halting problem
4. DSolvable in polynomial time