Skip to main content

Prerequisite Diagnostic

Attempt these without the new concept pages. This checks previously taught skills; knowing heaps, stability, or hash-table deletion is not an entry requirement.

  1. Trace lo=0, hi=7, then mid=(lo+hi)//2, then hi=mid. What is the new half-open interval length, and why does it shrink when lo<hi?
  2. State initialization, maintenance, and termination obligations for a loop invariant. Explain why a decreasing nonnegative integer proves termination.
  3. For powers of two, solve T(n)=2T(n/2)+n with T(1)=1. Count levels and leaf work.
  4. Distinguish worst-case cost of one append, amortized cost across appends, and expected cost over a random experiment. Does any one imply the others?
  5. If three indicators have expectations 1/4, 1/2, and 1/4, what is the expected sum? Must they be independent for this calculation?
  6. Given records (2,A),(1,B),(2,C), write their key sequence and their payload sequence. Why would moving only the keys damage the records?

Feedback and repair​

  1. mid=3, interval [0,3), length 3. For an active integer interval, mid<hi; either hi=mid or lo=mid+1 strictly reduces its length. Review Module 1's search invariant if the endpoints are unclear.
  2. Prove the invariant initially, preserve it through a step, and combine it with the exit condition. A strictly decreasing nonnegative integer cannot decrease forever. Return to Module 1 correctness lessons if either proof is missing.
  3. n log2 n + n: log2 n internal levels each contribute n and leaves contribute n. Revisit recurrence analysis if the combine work was counted only once.
  4. These quantify different things. A dynamic-array append can take linear time on a resize while a sequence has constant amortized cost per append; no random input assumption is required for that example.
  5. Expected sum is 1; linearity needs no independence. Review probability's indicator-variable lesson before the hashing cluster if this is unfamiliar.
  6. Keys [2,1,2], payloads [A,B,C]. Records must travel together; a key-only rearrangement can associate the wrong payload with a key.

Do not use a total score to bypass a missing prerequisite. Repair each failed item, then explain a fresh example. A mentor can change numbers and record order. Prior module: Algorithm Analysis & Design.