Algorithms & complexity worksheet with answers

What does binary search require of its input?

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

What is a brute-force algorithm?

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

Which design strategy does merge sort use?

1. ADivide and conquer
2. BGreedy choice
3. CBrute force
4. DDynamic programming

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 log n)
3. CO(n³)
4. DO(n)

What is the worst-case time complexity of quicksort?

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

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

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

To show that a new problem X is NP-hard, what must you do?

1. AShow that X can be verified in polynomial time
2. BReduce a known NP-hard problem to X in polynomial time
3. CReduce X to a known NP-hard problem in polynomial time
4. DShow that X has no polynomial algorithm for small inputs

Which definition of the class NP is correct?

1. AProblems that are not polynomial
2. BDecision problems whose yes-answers can be verified in polynomial time given a certificate
3. CProblems that cannot be solved in polynomial time
4. DProblems that no algorithm can solve