Project: audit phrase codes, active intervals, prefix bits, and routes

Acceptance trace

Encode cabacabacaba into seven phrase tokens and decode it exactly. Store M-19 over [19,61) and M-47 over [47,83); at time 50 both are active, at 83 neither is. A Huffman codebook trained on dispatch dispatch urgent encodes dispatch urgent to 57 bits in this deterministic trace and restores the phrase. A seven-depot directed graph condenses to four components; depot one reaches five, but depot five cannot return to one. Record the snapshot or codebook that makes each answer valid.

Failure and cost review

Generate short strings over small alphabets and verify LZ78 encode/decode round trips, empty input, and invalid forward phrase references. Fuzz interval additions and removals against a direct task-to-range map at every coordinate. For randomly generated symbol frequencies, verify Huffman round trips and that no codeword prefixes another. Compare every condensed-graph path answer against breadth-first search in random directed graphs with cycles. Reject an incomplete Huffman final code, out-of-universe interval, and old reachability rows after an edge update. Do not count Python character strings as packed compressed bytes.

Common Mistakes

• Do not invent a symbol for an LZ78 final known phrase.
• Do not include half-open right endpoints in stabbing results.
• Do not decode Huffman bits with a different tree.
• Do not keep condensation reachability after graph edits.

Connected lessons

• LZ78 phrase tries: emit dictionary index and next symbol
• Segment-tree stabbing indexes: list intervals active at one point
• Huffman trees: assign prefix codes from symbol frequencies
• Condensation DAGs: compress directed cycles before path queries
• Projects
• Quizzes
• Data Structures