Final exam

The exam was printed in color. Partly this was to make the diagrams pretty, partly this was as a hint that students should be thinking about colors. Adjacent to some colored text, a student wrote "LOVED THIS HINT, THANK YOU!" which is a very positive piece of exam-writing feedback to me. In a proof for this problem, another student wrote "The hint of coloring the 4 houses the different colors further solidifies [claim they were making]."

Down the margins of the final, one student entered a philosophical reverie: "What is 'correct'? Can approx algs ever even get there"

When asked to give an example, one student wrote "I can't fight the urge to say ∅". This was, in fact, a correct example.

I offered students the opportunity to write a joke. I am not sure these all make sense?

• Solving NP-complete algorithms is like finding a CS prof that doesn't wear khakis. Theoretically possible, but in practice it's too hard.
• The biggest dream for an NPC is to become P(layable).
• Why did the NP-complete problem become a therapist?
  It thought it had a lot of experience with unsolvable isues.
• "That's NPC behavior."
  Normal person interpretation: someone is acting funky like a Non-Player Character.
  Theoretical Computer Scientist interpretation: How did they figure out how to live non-deterministically?
• Why buy cereal from the NP-hard aisle of NP store?
  It's part of an NP-complete breakfast.
• I went to the doctor for my (N)ose (P)ain Problem. He took way too long to find a solution.
• This joke is NP-complete, reducible to everyone else's, hard to understand, and has a polytime verifier. Verifier: print("HAHAHAHAHAHA")
• Why did NP not cross the road?
  Because it wasn't efficient to do so.
• What did NP-complete say to NP-hard?
  Don't worry, your polynomial time is coming!
• What did Vertex Cover say to Independent Set?
  You NP-complete me <3
• Why did the NP-complete problem go to the party?
  It thought it would be a clique-free environment.
• Once NP-complete is verified on tiktok, it has its own verifier.
• A: Did you hear Neal Patrick Harris found his long lost brother, of the same name, Neil Patrick Harris?
  B: Oh wow, how nice!
  A: I know, right! They said now that they found each other, they both feel Neil Patrick-complete!
• Why was Lila late for the CS41 final (theoretically)?
  Because she was stuck in traffic and navigating it was NP-complete!
• Teacher: Prove this problem is NP-complete.
  Student: I just "completed" a solution, so it must be NP-complete.
• Q: What do you call a math-inspired, environmentally-minded tap-dancing group?"
  A: "Al Gore Rhythms: An Inconvenient Troupe"
• Q: Why did the programmer break up with NP-completeness?
  A: Because NP-completeness took too long to solve their relationship problems; she wasn't efficient enough.
• It is verifiable that I will complete my homeworks for ALGO but it can not be done in polynomial time. ALGO TO SCHEDULE ALGO Homework is NP-complete.
• Why did the algorithms problem not talk?
  It was NPC(omplete).
  idk if this makes sense, i don't play video games

I take issue with

• P=NP only if N=1

And indeed, another (more pedantic) student wrote:

• P=NP
  (N-1)P = 0
  N=1 or P=0

I was offered some non-jokes:

• I like to imagine that all of the NP-complete problems are friends with one another, because they can't feel complete without being reducible to one another.
• I am Not Proud of this exam, but it is Completed.
• I'm NP-complete with this test.
• Ironic for it to be NP-complete but we don't know if P=NP.
• I wish you were NP-complete so that all of our problems could be reduced to you.
• I can decide in polynomial time whether a graph is 3-colorable.

That last student is powerful in a troubling way.

When prompted, "Write a joke about NP-completeness." the most wry student in the class wrote:

• I would tell you one, but once you've heard one you've heard them all.
• I would write a joke about NP-completeness, but once you've heard one you've hard them all!
• I once heard an NP-complete joke but once you've heard one, you've heard them all.
• My verifier could assess a good joke if it saw one, but I don't think this problem can be done in deterministic polynomial time. :)

This post's theme word is lexiphanic (adj), "using pretentious words and language." Very few students attempted lexiphanic answers to test questions.

What social convention baffles you?

 I take attendance by having students answer a question.

What social convention baffles you? (previously)

Some people chose physical customs:

• handshakes
• giving someone a hug
• any convention with physical touch

... but overall many people chose social conventions that persist even in a pandemic era:

• small talk
• introductions
• ice breakers
• hi to strangers
• salutations on emails
• texting greetings before th emessage

Some people chose known-to-be-irritating social conventions:

• bachelor/bachelorette parties
• gender reveal parties
• working 5 days a week
• the 9-5 work day

My favorite is the choice to criticize conventions in favor of absolute chaos:

• waking up in the morning

This post's theme word is diachrony (n), "change occurring over a period of time." The social convention diachrony means that handshakes might shift to elbow bumps, or subtle head nods, or nothing at all.

If This Book Exists, You're in the Wrong Universe

If This Book Exists, You're in the Wrong Universe is a fantasy (?) horror (?) comedy novel by Jason Pargin, who also wrote John Dies at the End.

Like John Dies at the End -- as well as Pargin's other self-descriptive novels titled This Book is Full of Spiders, and What the Hell Did I Just Read -- this novel's title completely gives away the tone and contents of the book, while still preserving enough wacky mystery that the book can surprise. In this case, I vaguely remembered that John Dies at the End was sort of gonzo-humor and so my surprise came mostly from the graphic horror elements of If This Book Exists, You're in the Wrong Universe. I wasn't expecting those, didn't want them, and don't usually seek out that particular genre for my pleasure reading.

The comedy was suitably wacky, the mystery of the book was indeed clued variously throughout the book but readers would not ever have guessed the actual way it would resolve, and as the title declares, the book does attempt to describe its own provenance and the issues that it causes.

Overall this was a fine book --- a quick read at 432 pages, although I had to stop reading it before bed because the graphic horror scenes were not good pre-sleep brain fodder for dreams. The cover is an electric green-yellow and the cover art is great; the color, art, and title probably mostly explain why I picked this up and read it. It also was a good brain puzzle.

Recommended if you like horror or ghastly comedy. Pretty gorey and dark, plus I'm pretty sure almost every character is described in the depths of depression and various other mental illnesses, as well as everyone suffering under wretched capitalism and societal decline.

This post's theme word is penultimatum (n), "the demand made before an ultimatum." Climactic scenes should feature an explicitly-identified penultimatum, so that all readers can appropriately ratchet their anticipation.

SIROCCO 2023

Some quotes from SIROCCO 2023, a CS conference earlier this month.

"Everything's computation. Any process evolving and solving problems over time is computation." - Yuval Emek. An expression of the "computation is a metaphor for everything" that I hadn't heard framed this way before.

"Artificial neural nets use all kinds of swanky functions." - Frederik Mallman-Trenn

"... so first we need to understand what a human is. I'm oversimplifying a lot, but a human has a head and a body..." - Frederik Mallman-Trenn taking the physicists' approach to framing a problem

"This is the tapas version of the talk... I'm going to be going over a lot of topics to give you a taste of them." - Joshua Daymude

"There's so many dimensions here that we have not yet found one algorithm to rule them all." - Joshua Daymude, expressing an unscripted pervasiveness of Tolkien in popular culture

"This is a crowd that lies proofs, so I don't want to show off my simulations and offend anybody." - Joshua Daymude

"Roger is going to be talking about 'swarm intelligence', if that even exists." - Andréa Richa, introducing the next speaker's talk about swarm intelligence with a devastating level of objectivity

"I don't know how to solve this and I'm afraid to go back and tell them this, so you should help me! I want to hear your ideas." - Roger Wattenhofer, with an earnest appeal to the crowd that I can only imagine comes from unassailable tenure-granted confidence and seniority

[many inscrutable self-notes about the legibility of different presenters' slides, diagrams, and presentation styles]

The mildest possible theory praise: "I think you're touching upon the challenges of this area." - Michael Schapira

"Deep learning is voodoo. We can't debug it, we don't know how it works..." - Michael Schapira

"How do I know in real time that my decisions are no longer sound?" - Michael Schapira, expressing a CS question but also a question which suits intoxicated people

"The nice thing about this algorithm is... but the very horrible thing is, it uses infinite memory." - Bernadette Charron-Bost, expressing a truly beautiful "theory person has found a tradeoff" provable fact

The phrase "we need to use more elbow oil" was mentioned and my brain took a minute to figure out that the non-native English-speaking presenter probably meant the idiom "elbow grease", which on further inspection is a bizarre and faintly disgusting idiom.

Discussing the topic of algorithmic recommendation systems: "It's maybe something questionable from the moral point of view. But it's certainly interesting and I will not talk about it." - Boaz Patt-Shamir

This post's theme word is: craic (n), "good times involving pleasant company, enjoyable conversation, etc." Many speakers reminded us that SIROCCO is the 'fun' conference and is full of craic and jollity.