Data Structures & Algorithms / Optimization proofs and maintained aggregates

Data Structures & Algorithms β€” Optimization proofs and maintained aggregates

Dynamic programming, greedy exchanges, disjoint sets, spanning forests, range structures, string matching, and amortization.

6 lessons Β· No account required

What you will learn

  • Dynamic programming, greedy exchanges, disjoint sets, spanning forests, range structures, string matching, and amortization.

  1. Dynamic programming: state, order, and reconstruction

    Define reusable subproblems and a valid dependency order before compressing storage or reconstructing a solution.

    Start learning

  2. Greedy exchange arguments and counterexamples

    Prove a local choice preserves an optimum and recognize when changing the objective destroys that proof.

    Start learning

  3. Disjoint sets and minimum spanning forests

    Maintain component representatives and use a cut-based greedy rule without confusing connectivity with shortest paths.

    Start learning

  4. Fenwick and segment range structures

    Preserve a public half-open contract while maintaining logarithmic point updates and range aggregation.

    Start learning

  5. Prefix functions and overlapping string matches

    Reuse proven pattern borders rather than rescanning text and preserve overlapping matches with explicit Unicode semantics.

    Start learning

  6. Amortized costs and algorithm selection

    Bound operation sequences without confusing amortization, randomness, worst-case latency, or measured implementation behavior.

    Start learning
Back to course