Data Structures & Algorithms / Contracts, sequences, and search

Data Structures & Algorithms β€” Contracts, sequences, and search

Invariants, cost models, prefix sums, linked nodes, stacks, queues, hashing, and binary boundaries.

6 lessons Β· No account required

What you will learn

  • Invariants, cost models, prefix sums, linked nodes, stacks, queues, hashing, and binary boundaries.

  1. Contracts, invariants, and cost models

    Prove what a loop computes, count the work it performs, and state the assumptions behind asymptotic claims.

    Start learning

  2. Arrays, prefix sums, and range contracts

    Use half-open intervals to preprocess repeated sum queries and distinguish static queries from range updates.

    Start learning

  3. Linked nodes, ownership, and traversal

    Separate constant-time pointer changes from the search needed to find their location, and preserve reachability invariants.

    Start learning

  4. Stacks, queues, and ordering policies

    Choose removal order from the task and prove that the container preserves the unfinished work it represents.

    Start learning

  5. Hash maps, membership, and duplicates

    Use hashing for identity and counting while preserving duplicate semantics and qualifying expected-time claims.

    Start learning

  6. Binary search and boundary invariants

    Derive lower-bound search from a partition invariant and handle duplicates and absence without guessing midpoint rules.

    Start learning
Back to course