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.