Searching and Selection Workshop

P5. Duplicate boundaries

For [1,2,2,2,4], compute equal ranges for targets 0,2,3,5 and prove the two excluded-region invariants. Give empty and singleton cases. State indexed-read costs and why a per-call sortedness check changes total complexity.

P6. Search a feasibility boundary

Tasks [4,2,3,5] must stay in order and form at most two nonempty contiguous groups. Find the smallest permitted maximum group sum. Prove the feasibility predicate is monotone for nonnegative task sizes, state search bounds, and include the predicate's linear work in the total complexity. Explain why negative task sizes invalidate the greedy packing proof used here.

P7. One rank, many duplicates

Select zero-based rank 2 from [9,1,1,4,7], showing the regions for pivot 1. Give a phase-based expected-linear proof that charges bad pivot attempts. Explain what changes for fixed-seed, all-equal, and input-preserving versions.

P8. Choose an index

A static collection of n scores receives q exact rank queries. Compare sorting once with repeated selection. Then change to frequent updates and range output. Specify preprocessing, query, update and output costs; identify any tree augmentation required. Do not invent a numerical crossover from Big-O alone.

Attempt independently, then consult Practice Solutions. Submit a proof or counterexample as requested; code output alone is insufficient.