Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

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

Space complexity measures:

1. AThe disk space of the program file once it is compiled
2. BThe physical size of the computer
3. CThe number of lines of code
4. DThe amount of memory an algorithm needs as input grows

What is the worst-case time complexity of merge sort?

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

What is the worst-case time complexity of quicksort?

1. AO(log n)
2. BO(n log n)
3. CO(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 activity that finishes earliest, then repeat with the compatible ones
3. CPick the activity with the fewest overlaps first, then repeat with the compatible ones
4. DPick the shortest activity first

What does the Floyd–Warshall algorithm compute, and how fast?

1. AA minimum spanning tree in O(E log V)
2. BShortest paths between all pairs of vertices in O(V³)
3. CShortest paths from one source vertex to all others in O(V + E)
4. DA topological order in O(V²)

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX is in NP, and a known NP-complete problem reduces to X in polynomial time
2. BX is in P, and X reduces to SAT
3. CX reduces to a problem in P, and X is in NP
4. DX has no polynomial algorithm, and X is decidable

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

1. AOnly that one problem would move into P
2. BAll exponential-time algorithms would immediately run in linear time
3. CEvery problem in NP could be solved in polynomial time, so P = NP
4. DThe halting problem would become decidable