Top Five Ideas from Every Class

Dec 2022

When in an MIT semester so dearly we work to glean insight into the world, decency toward the remembrance of the future self impels us to enumerate the top ideas from each field.

6.106 Performance Engineering

1. Bithacks are magic.
2. Profile to see the real bottlenecks.
3. Lesson in software engineering: interfaces enable beautiful, clean abstraction.
4. Lesson in leadership: estimate how long things will take and what benefit they will confer. Take on tasks the team can finish. (Otherwise, no endgame table or parallelism.)
5. Heuristics for perspective and life: in Leiserchess, tuning the heuristics let the top team demolish the competition. We all viewed heuristic tuning as a maximization problem with the hugely expensive evaluation of 1000-game tournaments. The top team instead viewed heuristic weights as aiming to predict who will win the game; then they plugged 10M labeled games into least squares. Perspective. Let it stand as a lesson for life: know what you want, and the search will become easier.

6.122 Design and Analysis of Algorithms

1. Median of an unsorted array in O(n) time: split into blocks of 5, find median of medians recursively, partition on it, repeat. Median of medians is guaranteed close to middle.
2. Union find: MAKE-SET(x), UNION(x, y), FIND(x) in O(\alpha(n)) amortized time per operation: n is the number of MAKE-SET and \alpha is the inverse Ackerman function.
3. Minimum spanning trees: lightest edge on a cut is in some MST; heaviest edge on a cycle is in no MST; Kruskal’s finds MST in O(|E| \log |V|) time.
4. Max flow: the unexpected hero. It solves questions you wouldn’t expect.
5. Select uniformly random element from stream of unknown length with O(1) memory: set r = r_1, then at step j with probability 1/j set r = r_j. When the stream closes, return r.

18.675 Theory of Probability

1. If two measures agree on a pi-system with a sequence converging to the whole space, then the two measures agree everywhere. Proof: pi-lambda theorem.
2. Fatou’s Lemma: E[\liminf f] \leq \liminf E[f]. Exercise: derive the Dominated Convergence Theorem, stating if f_n \to f and f_n \leq g for integrable g, then E[f_n] \to E[f].
3. Conditional expectation Y = E[X | G] is G-measurable s.t. E[Y 1_H] = E[X 1_H] for all H \subset G. Another perspective: project X on to the subspace of G-measurable maps. If G is the trivial sigma algebra, then E[X | G] = E[X]. If G is the whole sigma algebra, then E[X | G] = X. Remember that sigma algebras tell us the amount of information we know.
4. Characteristic function E[exp(itX)] determines the distribution of a random variable X.
5. Optional Stopping Theorem: in expectation, a stopped martingale ends where it starts. Condition is \tau finite and {X_i} bounded, or E[\tau] finite and |X_i - X_{i-1}| bounded.

11.011 The Art and Science of Negotiation

1. Moves and turns: add deft perspective to name, interrupt, or reframe (Kolb and Porter).
2. Body language: feet are honest; they point and bounce. Torso leans away from the unpleasant. Steepled hands project confidence.
3. Spoilers: look out for them in important settings. Notice the signs: chameleon interests, too quiet, or too loud. Still, trust first.
4. Big picture: look to the best for the company at large. As the manager, give affiliation, status, appreciation. Learn the real story.
5. Inner Yes: the most powerful No has roots in a Yes to something bigger. Our faces leak our true feelings, so feel magnanimously.
6. Implementability: overcome motivated blindness. Everyone loses if the deal is founded on even the sweetest lies.

Miscellaneous thoughts: