Practice Solutions

Open after an attempt. Mark copied or assisted solutions as guided work, then solve changed inputs independently.

Complexity

A1: Each inner loop runs ceil(log2(n)) times, including zero at n=1. Total n*ceil(log2(n)), Theta(n log n) as n grows. Count overhead separately if required.

A2: Three-way tree has log3(n) internal levels each costing n and n unit leaves: n log3(n)+n. The decrement recurrence sums1..n, giving n(n+1)/2.

A3: With n=2^m, internal work is n*(1/m+...+1/2), plus n/2 leaves. Harmonic growth gives Theta(n log log n). f lies only logarithmically below the critical n; it is neither polynomially smaller nor in the stated k>=0 equal-exponent case.

A4: Doubling copies 31,total 48,max17,final capacity 32 and Phi=3. Additive copies 136,total 153,max17. Equal maxima at this prefix do not imply equal sequence cost. Empty initial state and one write per append are part of the calculation.

A5: W=2^b has b+1 binary digits. O(nW) is O(n*2^b) for this family, exponential in b. Polynomial in a numeric parameter is not necessarily polynomial in input length.

Correctness

B1: Below lo values are below target; at/above hi values are at least target. Sortedness preserves both statements under lo=mid+1 or hi=mid. Variant hi-lo strictly shrinks to zero. [2,2],target 2: mid1 equality moves hi to1; mid0 equality moves hi to0; return0. Immediate return at the first equality would incorrectly return1.

B2: [1],target 2 gives lo=0,hi=1,mid=0 repeatedly with lo=mid. Set lo=mid+1. The singleton interval then becomes empty and returns1, meaning no qualifying element.

B3: For length1 the element is its maximum. For larger input assume both strictly shorter nonempty halves return their respective maxima. The larger of those maxima dominates every element and belongs to the input, proving the result. Length strictly decreases. Reject empty input or define a distinct sentinel contract; neither follows from this proof automatically.

B4: Yes: the first coordinate decreases, so the later coordinate can rise. The first differing coordinate determines lexicographic order. Positive reals can decrease forever (1,1/2,1/4,...); a lower bound alone is insufficient without a well-founded ordering or another termination argument.

B5: Target3, selected5, remaining[-2] reaches3 despite temporary overshoot. With nonnegative remaining values, an overshoot can never be repaired, so pruning is safe. The undershoot bound also needs a justified upper bound on attainable additional sum.

Design

C1: Count3 at indices 0,1,3; value 10 at 2,3. Earliest-finish exchange preserves feasibility and cardinality, not arbitrary weight. Closed endpoints change compatibility: count optimum becomes2 and weighted optimum becomes9 (the long job conflicts with the final job at time4).

C2: Sorted indices 0,2,1,3; prefix counts0,0,1,3; D=[0,2,9,9,10]. From state4 take index 3, jump to3; skip index 1, take index 2. Reverse to2,3. Storing a length-O(n) witness in O(n) cells can cost O(n²); store scalar decisions and reconstruct once.

C3: D[0]=0. For t>0, D[t]=1+min(D[t-c]) over positive c<=t, with unreachable states infinity. D[5] is infinity; D[6]=2 via3+3. Greedy takes4 then cannot complete 2. Unlimited use and positive denomination are essential assumptions.

C4: Top-down keys must include the remaining amount and a fixed denomination set (or isolate each cache per problem). Bottom-up processes increasing amounts because every dependency is smaller. Strong induction gives identical values: same base and same minimum over already-correct smaller results. A chain of many unit decrements can exhaust a language's call stack; tabulation avoids that call-depth cost. Both use O(target*number_of_coins) unit-cost transitions when all states are evaluated.

C5: There are2^n subsets. Extracting indices and summing weights costs O(n) per subset; sorting each selected schedule adds O(n log n), as in the supplied oracle. Thus its safe bound is O(n log n*2^n), with small-input-only use. Presorting once can reduce checking costs. Agreement is finite evidence and can miss shared specification errors; it is not a universal proof.