Adversarial Algorithms and AI Search
This strand supplies evidence for S6 and the existing AL-ALGORITHMS-001 competency. Its work is included in the semester project's 24–36 hours. The revised overall workload is stated in the semester overview; this is not a promise that extra requirements fit the former ten-week allocation.
Required evidence inside the planner
| Evidence | Bounded task | Acceptance |
|---|---|---|
| Adversarial inputs | Equal endpoints, zero costs, negative values, old branches, failed batches and graph cycles | Correct results/rejection and one real failure minimized if a bug occurs |
| Worst-case resource contract | Derive graph/sort/table/copy costs; enforce an admission rule before large allocations | Over-limit work is declined explicitly, never silently labeled optimal |
| Probabilistic comparison | Explain skiplist expected bounds or a Bloom experiment from Module 5 | State randomness/population assumptions and separate observation from guarantee |
| Search/optimization transfer | Compare exact DP with brute-force search and a proposed heuristic/pruning rule | A concrete unsafe-pruning counterexample; a sound bound or explicit approximate status |
Reuse the Module 5 probability artifact; an additional randomized project feature is unnecessary. A repeated seed aids reproducibility, not a proof of adversarial robustness. A numeric budget with few input bits can still trigger a huge DP allocation; admission control is an engineering requirement beyond asymptotic notation.
AI-search connection with explicit limits
A search state encodes what future actions can depend on. DP merges histories only when that state preserves all relevant future choices and value. A heuristic ranks promising states but need not justify discarding alternatives. In maximization, pruning for exact value needs a valid upper bound on any completion; current value alone is usually a lower bound from work already chosen.
Write a one-page transfer memo with one counterexample and the assumptions under which your replacement is safe. You do not need to build an AI agent, prove a new search theorem or claim general guarantees for beam search. Assess the memo through E6, the project defense and a changed requirement at the checkpoint.
Assistance and sources
Record books/tools/models used, material output accepted, suggestions rejected and independent verification. Generated tests that repeat the implementation are not an independent oracle. Start with module proof, graph, DP and probability lessons; use their selective reading guides for Skiena/CLRS and primary depth references. Record missing evidence honestly; no fabricated timings, review or learner outcomes.