Semester 2 Exam

This cumulative exam tests synthesis after the five module gates. Allow 3–4 hours for an initial written attempt, with breaks/accommodations recorded. It is an author estimate, not a calibrated speed requirement. Close the worked key and old solutions; record any approved formula sheet or assistance. Code execution may be used after the first preserved attempt to check calculations.

The six tasks total 100 diagnostic points. Passing is determined by S1–S6 competency gates, module evidence, project and fresh rechecks; there is no compensating average or weak pass that hides a critical error. Use the worked key afterward. If already familiar with this paper, ask a reviewer to change inputs and assumptions for scored assessment.

Task	Focus	Points
E1	Tight bounds, recurrences and input model	15
E2	Stable order, boundaries and structure choice	15
E3	Graph readiness and certificates	15
E4	Budgeted interval state, proof and witness	25
E5	Amortized costs, historical isolation and exact membership	20
E6	Probability, measurement and unsafe pruning	10

E1: derive the work

For integer n≥1, run i from 1 through n; for each i, initialize k=1 and double k while k <= i, doing one counted action per inner iteration. Give the exact action count at n=8 and a tight asymptotic bound, including a lower-bound argument. Then solve T(n)=2T(n/2)+n*log2(n), T(1)=1, for powers of two. Give either the exact expression or a matching tight bound with level/leaf reasoning. Finally explain why O(mB) scheduling work is not necessarily polynomial in the binary input length and state the arithmetic model.

E2: make ordering semantics visible

Stable-sort records [(3,A),(1,B),(3,C),(2,D)] by numeric key. Give the result and zero-based lower/upper bounds for key 3. State the half-open search invariant and termination measure. Explain the merge tie rule that preserves stability and distinguish stability from merely returning sorted keys.

A workload now requires insert/replace, exact lookup and sorted range output. Compare a hash map and an augmented balanced search tree, including construction, output size and guarantee assumptions. Reject the statement “hash lookup always takes O(1)” without claiming a universal speed ranking between implementations.

E3: earliest readiness is not hop count

Preparation nodes have durations 0:2, 1:3, 2:1, 3:2 and edges 0→1, 0→2, 1→3, 2→3. With unlimited parallel preparation, compute each earliest finish and a valid topological order. State certificate checks and the recurrence. Explain why BFS levels are insufficient. If edge 3→0 is added, give a concrete cycle and state the service's result. Include isolated nodes and the cost of checking all vertices/edges in your reasoning.

E4: couple readiness to exact optimization

Use E3's original acyclic graph and budget 5 with these jobs:

ID	Interval	Cost	Value	Required node
10	[2,4)	2	5	0
11	[4,6)	2	6	2
12	[6,8)	2	6	1
13	[2,6)	3	10	0
14	[7,9)	2	8	3
15	[6,7)	0	2	3

Intervals are half-open; jobs are optional and have no selection dependencies. Give eligible jobs in stable finish order and their compatible-prefix counts. Define the DP state, recurrence, base cases, evaluation order and witness recovery. Give optimal values for budgets 0..5 and a valid budget-5 witness with cost. Prove the skip/include cases and give a counterexample to earliest-finish greedy using this input. Explain zero-cost/negative-value handling, table/bit costs, and why adding arbitrary dependencies between selected jobs invalidates the state.

E5: mutation, sequences and history

Under the copy/write model, an empty doubling array grows 0→1→2→4→8. Give actual costs and potential charges for its first five appends using Phi=2*size-capacity. Include initial potential and distinguish an amortized sequence bound from a per-call latency guarantee.

For E4's catalogue, version 0 is unchanged; version 1 deletes job 13 from version 0; version 2 independently deletes job 14 from version 0. Give each optimum and one witness. Describe a test for accidental use of the latest version and for caller mutation of a returned job. A present job with value zero must remain distinguishable from an absent job.

Explain why rebuilding a shared Bloom negative shortcut from version 1 alone is unsafe for version-0 lookups, and why positives still require exact confirmation. State the cost of a copied snapshot and why persistent range sums alone do not make optimal schedule recomputation logarithmic.

E6: defend the evidence boundary

For 1024 fixed keys with independent skiplist promotion probability 1/2, bound the probability that any tower reaches level 20 (base level is zero). Explain what this does and does not prove about search time or an adaptive adversary.

A DP implementation wins one timing run against brute force. Specify the missing measurement controls and why that result does not prove a complexity bound. Finally reject this search rule: “discard a partial schedule whenever its current value is below the incumbent.” Give a small counterexample and state the kind of bound needed for sound pruning in a maximization problem. Connect this to heuristic search without claiming that a beam search returns an exact optimum.

After the attempt

Record points, competency levels, critical errors and assistance separately. Repair an incorrect model with a fresh case and explanation, not only a corrected number. Store raw answers as checkpoint evidence; publish original project reasoning only if desired. The checkpoint governs final progression.

Automata and computability evidence

Reuse the Module 6 bridge packet for S6: AC1–AC4 each require level 2 alongside CA1–CA6. Preserve the state invariant, language-boundary proof, impossibility/reduction argument and fresh transfer. A timeout called infeasible, or NP-completeness called undecidability, requires repair. This is module assessment evidence, not an additional timed exam or planner feature. Its 20–30 hours are counted in Module 6 (45–65 total), making the semester 465–660 hours.