===The Adjacency Matrix of Love===|
Prof. Ran had just finished a long lecture at the Pasadena Institue of Technology and was walking down the hallway when his archrival Prof. I. Lai burst forth from his office, which Prof. Ran routinely mistook for a broom closet. Prof. Lai beamed at Prof. Ran with great excitement, his eyes and bowtie forming a proper subset of things that were bulging.
“Prof. Ran,” said Prof. Lai, breathlessly, “I have discovered an important result about,” - Prof. Lai paused for dramatic effect - “insertion sort.” Prof. Ran rolled his eyes at his spurious colleague. He knew that even if there was something interesting to be proven about insertion sort, a hack like Prof. Lai could never have discovered it. Yet Prof. Lai did occasionally produce illustrative misconceptions that he could use in his algorithms class, so Prof. Ran walked through the door that Prof. Lai was so dramatically holding open for him to inspect what his colleague had to show him.
Upon entering the office Prof. Ran realized that he had never been there before. He typically debunked Prof. Lai on a classroom whiteboard, he had never done it at his desk before. Prof. Lai thrust some papers into Prof. Ran’s hands.
“Here,” said Prof. Lai huskily, “I’ve shown that insertion sort can run in log n time!” Prof. Ran perused his colleague’s work and quickly realized that the algorithm in question simply sorted the list with mergesort and then pretended to run an insertion sort. He was about to vigorously disrobe Prof. Lai’s proof, but all of a sudden he noticed something truly shocking. At the back of Prof. Lai’s desk was a lovingly framed diploma from Harvey Mudd College. Prof. Ran froze in shock. How could such an incompetent, dishonest academic have come from such a noble institution as HMC? Intrigued, Prof. Ran scanned his mysterious rival’s desk. He spied a draft of a paper on efficiently multiplying matrices. He quickly examined it, and immediately saw that this was not at all like any work Prof. Lai had shown him before. He turned to Prof. Lai, brandishing the paper.
“Did you write this?” asked Prof. Ran aggressively.
“Well,” Prof. Lai answered reluctantly, “yes.”
“But how?” responded Ran incredulously, “this is brilliant work! Why do you always bring me ridiculous results when you can do things like this? And did you really go to Harvey Mudd?”
“Yes, I did,” answered Lai sheepishly.
“Then why all the lies?” Ran inquired. Prof. Lai reached tentatively toward Prof. Ran’s cheek.
“I just wanted you to notice me,” he said plaintively, and then added, “senpai.” In that moment, Prof. Ran saw Prof. Lai in a whole new light. He had always wanted to be someone’s senpai. In the Adjacency Matrix of Love, the Ran, Lai cell switched from a 0 to a 1.
“I have a proof that I’d like you to review,” said Prof. Ran softly, “Claim: you’re really hot. Proof: by inspection.” At this he pulled Prof. Lai into his arms, and his hands began executing a breadth first search of his erstwhile rival’s body. They kissed greedily, and their passion grew at a rate of n cubed. When Ran could barely restrain himself from executing a depth first search of his colleague, Prof. Lai reached down and grasped Prof. Ran’s one-eyed alien.
“My god!” said Prof. Lai, “it’s so hard!”
“Yes,” Ran smiled, “it’s NP hard.” And right there, on Prof. Lai’s desk, they merged in O(n^5) time. Prof. Ran knew he could have been more efficient, but he was enjoying himself. Efficiency wasn’t everything. Finally, both Professors reached their optimal solution.
The rivals-turned-lovers sat back on the desk, breathing heavily. After a little while, Prof. Ran turned to Prof. Lai, smiling.
“Now,” he said, “you play the role of the malicious adversary.” They were at it again. Prof. Lai was a crafty adversary, but Prof. Ran wielded his log n skillfully, and his colleague couldn’t prevent him from reaching an optimal solution once more. Reduced to exhaustion, the two lay back on Prof. Lai’s desk, fingers intertwined.
“Next time,” said Prof. Ran, “we’ll have to try the Four Russians Method.”