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.
