My fairly standard computer science education covered amortized complexity. You can't analyze the time complexity of a sensible vector type (i.e. "one step above raw array") without it.

Invariants are admittedly undersold in the curricula I've seen, but the idea comes up in many places. Most people ought to have at least encountered the idea in databases, where foreign key references provide basic invariants about referencing existing rows no matter what SQL you fling at them, for instance.