Learn Specify state transitions, discover sufficient invariants, prove total correctness and derive operation costs with integer rounding. Compare finite traces with proofs that cover every allowed input.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
Safety and progress are separate proof obligations.
No. A transition that leaves the entire state unchanged preserves every state invariant but can repeat forever. Termination needs a separate argument such as strict descent in a well-founded order.
Operation counts require an explicit cost model and fixed constants.
For nonnegative costs, f(n)=O(g(n)) means f(n)≤C g(n) for all n≥n₀ with fixed C and n₀. It does not state elapsed seconds, exact equality or a lower bound.
Loading saved mathematics work…
Correctness and cost on changed processes
The mixed assessment has separate response history and review criteria; it does not change lesson participation records.
Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.
Specify a nondeterministic process, repair a weak invariant and prove safety for every permitted transition.
8 practice tasks.
Separate safety from termination, prove a two-counter process stops, and derive a rank that counts its remaining transitions exactly.
6 practice tasks.
Derive a divide-and-conquer cost from a real partition, prove all-integer bounds and contrast balanced splitting with a quadratic alternative.
6 practice tasks.