In November 30, 2022, ChatGPT was released. Actually, this has nothing to do with the topic of today’s post. For that, we need to go back three weeks.
6.854, now known as 6.5210, is MIT’s Advanced Algorithms class taught by Professor David Karger, known for being a great but tough class. Back in November 2022, some friends and I were taking the class, and fortunately, none of the assignments involve writing a rap about algorithms, but we decided to write one anyways for fun and perform it in-class. (We also orchestrated a live performance of a splay tree with humans representing the nodes, but it ended up being too hectic.)
Now this was back before ChatGPT (I think we performed it on 11-30 which is the same day ChatGPT came out), so all we had was RhymeZone and our brains. Fortunately, we had a total of four brains among us, so it wasn’t too difficult to come up with something:
How to be smart: be lazy
It's actually not that crazy
Pick the right potential
For the proof it's essential
decrease key in time n logarithm
too slow is this algorithm
kill child 1, mark parent
kill child 2, cut preserve invariant
---
Don't like manually adjusting your search trees?
We're going to help you make it a breeze
Here comes Tarjan
The data structure superman
To save the day
With operation splay
The best kind of trees
Cooler than antifreeze
Zig zig-zig zig-zag
More powerful than a big bag
$\sum \log r_i= \phi$
Static optimality, static finger
Working set, dynamic finger
Your homework after today's lecture:
Prove the dynamic optimality conjecture!
---
Each edge has a capacity,
no more flow can be pushed, you see.
The flow must satisfy conservation,
For flow at any node, zero is the summation.
Find a feasible flow at the start,
then you can augment paths if you're smart.
do not just look at the graph,
of what you should consider that is just half.
there are also residuals created by flow,
if you push more, its capacity will grow.
you stop when no more paths exist,
for the ford fulkerson algorithm, that is the gist.
min cut: the smallest set of edges removing the link
between the source and the sink.
If you want to assert flow optimality,
It must equal the min cut, by duality.
If even shortest augmenting paths are too slow,
Consider using Dinic's blocking flow.
implement link cut trees,
they can find blocking flows with ease.
Want it even faster? Use push relabel
But its time complexity is a fishy fable
---
a very good hash table
expected O(1) query enable
don't like number of collisions randomized?
perfect hashing analyzed
hash family is 2-universal independent
in terms of space it is transcendent
use binary heap priority queue for integer Dijkstra
the expense is a bit extra
---
In a linear program statement
you have variables and constraints
Each assignment has an objective
and of the optimal your solution must be selective.
In standard form, we have Ax=b,
this representation is useful, you will see.
If A is square, the solution is terse
Just calculate A inverse.
When seeing a LP your first reflex
might be to use the simplex
But then comes a Klee-Minty cube
Your performance goes down the tube
Want weakly polynomial?
Ellipsoid is mostly ceremonial
Humanoid, you should be paranoid
About the slowly shrinking ellipsoid
For truly fast worst case,
interior point will win the race
Don't believe strong duality?
Learn physics to learn the reality.
Nash equilibrium, min-cut-max-flow,
Are all things strong duality can show
Tryna check if vertex cover is NP
But I get blocked by NB
---
Dijkstra, karger and kruskall,
tarjan, floyd, and warshall
Wall sit, pset submit,
Jumping, situps, diamond pushups
Karger! Larger brain charger!
Now of course, anyone these days can simply ask a large language model to write a rap about splay trees or linear programming, but the LLM-generated raps have a very different feel or vibe to them. LLMs are great at picking the “right” word, whereas we often picked weird words like “The best kind of trees / Cooler than antifreeze” or “Want it even faster? Use push relabel / But its time complexity is a fishy fable”. (I’m mainly picking on those lines because I remember I was the one who wrote them.)
And it turned out the 854 rap wasn’t just fun, it was also helpful for finding a research project to join. Last year, I emailed Professor Karger about research opportunities and mentioned the 854 rap. As silly as it sounds, it worked and I quickly received a reply!