Skip to main content

Independent Advanced Structures Assessment

Allow 3–4 hours for the initial written attempt; implementation review and remediation use the remaining assessment allocation. Close examples and keys, preserve an attempt and record assistance. Use syntax documentation during code work if needed, then explain the invariant unaided on a fresh sequence. Open solutions and scoring afterward.

A1: ordered map and metadata​

Insert keys 4,2,3 with values 40,20,30 into an AVL map, replace key 2 with value 99, then delete 4. Trace rotations, ordering, height and size. Give rank(3), select(0) and all items. Propose independent checks that reject a tree with correct lookup answers but stale subtree sizes. Explain how red-black color/black-height invariants give a different deterministic height guarantee.

A2: partition and permitted events​

Initialize seven vertices. Union (0,1),(2,3),(1,2),(4,5),(0,3) and report change flags, partitions, counts and sizes. Prove the smaller-component depth bound and distinguish it from the alpha theorem with compression. Explain what happens if the underlying graph later deletes edge 1-2, then also deletes edge 0-3. Treat every union request as an inserted graph edge, including requests that do not change the partition. Explain why parent pointers cannot serve as a graph path witness.

A3: heap structure and ownership​

Meld heaps of sizes 7 and 1 and show all carries. Specify donor behavior, duplicate keys, empty pop and self-meld. Give a sequence that detects shared nodes after a destructive meld. Explain why constant local work in a pairing heap does not establish Fibonacci-heap decrease-key bounds.

A4: amortized costs with units​

Derive actual and potential charges for the first five doubling-array appends. Use the lab copy/write model and Phi=2*size-capacity. Prove the general prefix bound and include initial allocation. For a two-stack queue using unit push/pop costs, derive a suitable potential and the actual cost of transferring k items during a dequeue. Explain what the proofs do not guarantee about latency.

A5: range-update algebra​

For [2,0,-1,5], assign 4 to [1,4), then add -2 to [0,3). Give the final array, total and sum [1,3). Derive general sum action and new-after-old tag composition. Show how assignment-zero differs from no pending update. Explain which of these operations the core Fenwick API supports directly.

A6: historical versions​

Version 0 is [2,4,6,8]. Fork it to set index 1 to 10; separately fork version 0 to set index 2 to -2. Give all version sums and specify which subtrees share. Derive time/new-node/retained-root costs. Propose a test that catches use of the latest root instead of the requested old version.

A7: approximate filter, exact service​

Size a standard Bloom filter for n=1000 and target p=0.01 under the ideal approximation. State rounding, byte payload and model limits. An exact store contains only A, and a one-bit filter has been populated with A. Explain the correct service result for B. Then describe a false-negative failure caused by stale publication and a safe single-threaded update order.

A8: guarantees and a changed requirement​

For a fixed set of 1024 keys and independent promotion 1/2, bound the probability any skip-list tower reaches level 20. Contrast expected, amortized and worst-call costs. A current-value range service now needs old-version queries: propose a structure/API change and testing strategy. Explain why tree-shape bits and ideal-cache bounds do not include all payload/runtime costs.

Each task maps to one competency. Arithmetic, memorized names and a passing fixture cannot compensate for a broken invariant or changed contract.