Invariants in Computing

event: klcamp speaker: Wong Limsoon

[Gambling] red bean, green bean (green’s parity is invariant) [Card trick] 21 cards tricks (invariant is reducing the position of the chosen card) [Origin of polynesians] mutations are maintained in future generations [Sorting by bubble sort] invariant of sorted sequences, removing violations to get sorted list [DB design] FDs, BCNF, removing violations of invariant to get BCNF [Diagnosing leukemia] gene expression profile of patient is invariant, sorting rows/cols of gene expression matrix to get patterns [Fast exponentiation] skipped [Rootkit] identify rootkit by specifying invariants of correct behavior (KHIVE software, integrated in Windows update) [Document restoration] invariants in document restoration (take home) [Others] loops, recursion, induction (classic examples)