Things a TCSer should have done at least once

There are many discussions about what things a TCS grad student should know. I thought it might be useful instead to list out some things a theoretician should have done at some point early in their career.

Rules of the game:

• You lose points if you do it as part of a class. If you decide to round an LP in a class on approximations, that's something you're being taught to do. But if you do it as part of solving a problem, then you've also done the difficult job of recognizing that an LP needs to be rounded. That latter skill demonstrates some mastery.
• The goal is not complete coverage of all of TCS; rather, it's coverage of techniques that will come up fairly often, no matter what kinds of problems you look at.
• This list is necessarily algorithms-biased. I doubt you'll need many of these if you're doing (say) structural complexity. 
• A similar caveat applies to classical vs quantum computing. While it seems more and more important even for classical computations that one knows a little quantumness, I don't know enough about quantum algorithm design to add the right elements. Comments ? 

With those caveats out of the way, here's my list:

• Show that a problem is NP-hard (for bonus points, from some flavor of SAT via gadgets)
• Show a hardness of approximation result (bonus points for going straight from a PCP)
• Prove a lower bound for a randomized algorithm
• Prove a lower bound via communication complexity or even information theory
• Round an LP (bonus points for not just doing the obvious rounding)
• Show an integrality gap for an LP
• Design a primal-dual algorithm
• Use projective duality to solve a problem (bonus points for using convex duality)
• Apply a Chernoff bound (bonus for using negative dependence, Janson's inequality, and an extra bonus for Talagrand's inequality)
• Design an FPT algorithm (maybe using treewidth, bonus for using bidimensionality or kernelization)
• Design a nontrivial exponential time algorithm (i.e an algorithm that doesn't just enumerate, but does something clever)
• Do an amortized analysis (for extra bonus get a log*n bound)
• use an advanced data structure - something beyond van emde Boas trees (extra bonus for exploiting word-size)
• invoke VC dimension to solve a problem 

What else ?