Algorithmic Efficiency FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

List L has 6 sorted numbers. Algorithm Scan checks items from left to right. Algorithm Halve repeatedly discards half of a contiguous remaining region (assume perfect halves: 6→3→2→1 counting region sizes after each check decision). (a) How many checks does Scan need in the worst case? (b) Count the region-size steps 6, 3, 2, 1 and state how many reductions occurred. (c) Which algorithm uses fewer checks on this n as described?

Question 2 of 5

Algorithm R uses n steps. Algorithm S uses n^2 steps. (a) Compute both for n = 4. (b) Compute both for n = 8. (c) Explain which grows faster as n increases using your counts.

Question 3 of 5

A problem asks for the shortest delivery route among many warehouses. An exact algorithm would try every ordering (factorial growth). A heuristic builds a route by always visiting the nearest unused warehouse next. (a) Why might the heuristic be preferred for large numbers of warehouses? (b) State one limitation of the heuristic. (c) Explain the difference between an optimization problem and a yes/no decision problem using this setting.

Question 4 of 5

Algorithm Pair compares every pair of n students (about n*(n-1)/2 comparisons). For n = 5: (a) Compute the number of comparisons. (b) For n = 10, compute the number. (c) Compare those two counts and explain what happens to step counts when n doubles.

Question 5 of 5

Informally, algorithms with polynomial step growth (like n or n^2) are called reasonable-time, while exponential like 2^n are unreasonable for large n. (a) Classify an algorithm with about n^2 steps for large n using that informal rule. (b) Classify an algorithm with about 2^n steps. (c) Give one reason unreasonable-time algorithms become impractical as n grows, using n = 5 vs n = 20 for 2^n as a counting argument.