My theoretical computer science notes from Epsilon Camp
Last summer, I was privileged to teach a two-week course on theoretical computer science to exceptional 11- and 12-year-olds at Epsilon Camp, held at Washington University in St. Louis. The course was basically a shorter version of the 6.045 course that I used to teach to undergrads at MIT.
I was at Epsilon Camp to accompany my son Daniel, who attended a different course there, for the 7- and 8-year-olds. So they got me to teach while I was there.
Teaching at Epsilon was some of the hardest work I’ve done in years: I taught two classes, held office hours, and interacted with or supervised students for 6-7 hours per day (compared to ~4 hours per week as a professor), on top of being Daniel’s sole caregiver, on top of email and all my other normal responsibilities. But it was also perhaps the most extraordinary teaching I’ve ever done: during “lecture,” the kids were throwing paper planes, talking over and interrupting me every ten seconds, and sometimes getting in physical fights with each other. In my ~20 years as a professor, this was the first time that I ever needed to worry about classroom discipline (!). It gave me newfound respect for what elementary school teachers handle every day.
But then, when I did have the kids’ attention, they would often ask questions or make observations that I would’ve been thrilled to hear from undergrads at UT Austin or MIT. Some of these kids, I felt certain, can grow up if they want to be world-leading mathematicians and physicists and computer scientists, Terry Taos and Ed Wittens of their generation. Or at least, that’ll be true if AI isn’t soon going to outperform the top human scientists at their own game, a prospect that of course casts a giant shadow not only over Epsilon Camp but over our entire enterprise. But enough about the future. For now I can say: it was a privilege of a lifetime to teach these kids, to be the one who first introduced them to theoretical computer science.
Or at least, the one who first systematically introduced them. As I soon realized, there was no topic I could mention—not the halting problem or the Busy Beaver function, not NP-completeness or Diffie-Hellman encryption—that some of these 11-year-olds hadn’t previously seen, and that they didn’t want to interrupt me to share everything they already knew about. Rather than fighting that tendency, I smiled and let them do this. While their knowledge was stunningly precocious, it was also fragmentary and disjointed and weirdly overindexed on examples rather than general principles. So fine, I still had something to teach them!
Coming to Epsilon Camp was also an emotional experience for me. When I was 15, I attended Canada/USA Mathcamp 1996, the first year that that camp operated. I might not have gone into research otherwise. Coming from a public high school—from the world of English teachers who mainly cared whether you adhered to the Five Paragraph Format, and chemistry teachers who’d give 0 on right answers if you didn’t write “1 mol / 1 mol” and then cross off both of the moles—I was suddenly thrust, sink or swim, into a course on elliptic curves taught by Ken Ribet, who’d played a major role in the proof of Fermat’s Last Theorem that had just been completed, and a talk on algorithms and complexity by Richard Karp himself, and lectures on number theory by Richard Guy, who had stories from when he knew G. H. Hardy.
Back when I was 15, I got to know George Rubin Thomas, the founding director of Mathcamp … and then, after 29 years, there he was again at Epsilon Camp—the patriarch of a whole ecosystem of math camps—and not only there, but sitting in on my course. Also at Epsilon Camp, unexpectedly, was a woman who I knew well back when we were undergrads at Cornell, both of took taking the theoretical computer science graduate sequence, but who I’d barely seen since. She, as it turned out, was accompanying her 8-year-old son, who got to know my 8-year-old. They played together every day and traded math facts.
It occurred to me that the course I taught, on theoretical computer science, was one of the most accessible I’ve ever done, and therefore more people might be interested. So I advertised on this blog for someone to help me LaTeX up the notes for wider distribution. I was thrilled to find a talented student to volunteer. Alas, because of where that student lives, he needs to stay anonymous for now. I thank him, pray for his safety, and hope to be able to reveal his name in the future. I’m also thrilled to have gotten three great high school students—Ian Ko, Tzak Lau, and Sunetra Rao—to help with the figures. Thanks to them as well.
You can read the notes here [59 pages, PDF]
If you’re curious, here’s the table of contents:
- Lecture 1: Bits
- Lecture 2: Gates
- Lecture 3: Finite Automata
- Lecture 4: Turing Machines
- Lecture 5: Big Numbers
- Lecture 6: Complexity, or Number of Operations
- Lecture 7: Polynomial vs. Exponential
- Lecture 8: The P vs. NP Problem
- Lecture 9: NP-completeness
- Lecture 10: Foundations of Cryptography
- Lecture 11: Public-Key Cryptography and Quantum Computing
Happy as always to receive comments and corrections. Enjoy!
Follow
Comment #1 March 29th, 2026 at 1:51 am
typo on pg 13: “01* means {𝜖, 01, 0101, 010101, . . .}” should be “(01)* means {𝜖, 01, 0101, 010101, . . .}”
Comment #2 March 29th, 2026 at 3:31 am
Based on your own personal history, these kids might benefit if camp included a course on social interactions, dating, and dealing with the opposite sex. Although maybe AI will take that over as well 🙂 Speaking of which, were there many, or any, girls in your class?
Have you seen the new movie, The AI Doc: Or How I Became an Apocaloptimist? As you know, I’m what the movie calls an “accelerationist” rather than a “doomer”, but I found the movie to be very well done and reasonably balanced, and it features interviews with tons of high-level people involved in AI. One thing I found depressing in the film were the people who seriously think that AI doom is a reason not to have children. (Both the filmmaker and Sam Altman were expectant fathers during its making.)
Comment #3 March 29th, 2026 at 3:38 am
There is a typo on page 3: 1 1 0 0 0 -> 1 1 1 0 0
Comment #4 March 29th, 2026 at 8:04 am
Hyman Rosen #2: I had one class that was all boys, but another class with four girls who sat together. Naturally the all-boys class tended to be rowdier. The girls were quieter but superb students—they didn’t randomly blurt stuff out, but when they did volunteer something there was usually deep thought behind it. They loved playing the card game Set with each other before and after class.
I’m not sure that lessons on “dating and dealing with the opposite sex” would be appropriate for the 7-12 age group. But I’m sure that being among like-minded peers was great for many of the kids’ social development (note that many of these kids are homeschooled, a privilege I never had).
A review of “The AI Doc” will be my very next post.
Comment #5 March 29th, 2026 at 9:38 am
Scott #0,
>I advertised on this blog for someone to help me LaTeX up the notes for wider distribution. I was thrilled to find a talented student to volunteer
I’m curious about this. Was this a clever move to involve talented students, or was it more indicative of the moment—last summer—when using AI for this kind of task wasn’t yet the default?
*from copilot
Two minor spelling mistakes and one numerical error should be noted in these lecture notes. In Lecture 3 (page 12), the word “enought” should read “enough” in the sentence stating that AND, OR, and NOT gates are sufficient to compute any Boolean function. In Lecture 5 (page 23), the word “exponentation” should be corrected to “exponentiation” in the discussion comparing addition, multiplication, and exponentiation. Finally, also in Lecture 5 (page 28), the numerical value of Euler’s constant is misstated: the text gives e ≈ 2.17828, whereas the correct value is e ≈ 2.71828.
*more from Claude
1. Typo in Lecture 7 (Stable Marriage section): “Who does he propose to? Hist first choice, Alice.” — “Hist” should be “His.”
2. Encoding inconsistency in Lecture 1: the letter-to-binary table assigns A = 00000 (i.e., 0-based indexing), which would make E = 00100, I = 01000, O = 01110, and so on. However, the encoding of “EPSILON CAMP RULEZ” uses 1-based values instead (E = 00101, I = 01001, O = 01111, etc.). The two are inconsistent with each other — it would be worth either shifting the table so that A = 00001, or correcting the encoded example to match the 0-based table.
*(on this task gemini pro was useless and awfull, as if there were some problem with uploading the pdf)
None find the typo finelli #3 correctly identified. 👍
Comment #6 March 29th, 2026 at 12:01 pm
Glassmind Quattro #5: I have so many students emailing me asking to do stuff, that honestly it’s almost as easy as using AI when I have a well-defined task that needs doing! But also, while AI can (and did) help with this job, I don’t think it can do it entirely on its own yet. Maybe soon.
Comment #7 March 29th, 2026 at 1:08 pm
I have written about my torture chamber of a school that was a.small K-12. At some point prior to graduation the career objectives coalesced considerably into two main groups. The coalesced objectives were 1) Have my own methlab and 2) Work in the massage therapy field. Different world and yours is better.
The teachers would tell me to be quiet and put me in the back of the room and give me something to read. In Biology one year it was Grey’s Anatomy. Tough read when you have little interest in Anatomy.
I know it sounds cliche and hard to believe but the HS math teacher was also a rabble rouser Evangelical minister who’s main interest in mathematics was to determine how many angels could fit on the head of a pin (don’t ask). I am so very lucky to have escaped that milieu. Thank you standardized tests, you were truly a life saver.
My daughter that attends a gifted school tells me about the bad behavior of the boys. I was shocked at the start because I thought that bright kids so fortunate to be in that situation would be well behaved. I eventually recognized my preposterous naïveté about boys. The smartest boy in her class though does sound courteous and well behaved.
Comment #8 March 29th, 2026 at 10:01 pm
Scott #6,
I spent about half an hour this evening asking Claude to make sense of these mixed results and the experience turned out to be more interesting than I expected — both for what it found and for how it found it.
To recap, I started by simply asking Claude to read the document and flag any typos or mathematical errors. It caught some things but missed others, and the results were inconsistent across tools (Copilot and Gemini each found different subsets of the same errors, and Gemini produced a large number of false positives that appeared to stem from PDF parsing issues rather than actual mistakes in the text).
When I pointed this out to Claude and asked why. Claude gave a lucid explanation: LLMs are optimized to understand meaning, so they tend to mentally “correct” surface errors as they read, much like a human proofreader who is too familiar with the text. A traditional spell-checker, by contrast, is blind to meaning but very sensitive to form — exactly the opposite profile.
That led naturally to the question: why not write a program then? So Claude proceeded to do just that. It extracted the raw text from the PDF using pdftotext, built a spell-checker using Levenshtein edit distance against a built-in vocabulary, and added targeted mathematical checks for things like binary arithmetic, the value of e, and the letter-encoding consistency. The first version had a bug (a “seen words” filter was suppressing valid detections), Claude caught the bug itself, fixed it, and reran.
The final consolidated list of confirmed errors is:
1. p. 4 — Binary addition: 10101₂ + 111₂ is given as 11000₂, but the correct result is 11100₂ (= 28 in decimal, which matches the decimal answer already shown).
2. p. 4 — Encoding inconsistency: the table assigns A = 00000 (0-based), but the encoding of “EPSILON CAMP RULEZ” uses 1-based values (E = 00101 instead of 00100, I = 01001 instead of 01000, etc.).
3. p. 12 — Typo: “enought” should be “enough”.
4. p. 23 — Typo: “exponentation” should be “exponentiation” (appears twice).
5. p. 28 — Numerical error: e ≈ 2.17828 should be e ≈ 2.71828.
6. p. 38 — Typo: “Hist first choice” should be “His first choice”.
What actually impressed me most was the precision of the program Claude wrote — the choice of Levenshtein distance, the page-by-page extraction, the targeted mathematical checks, its choice entirely.
So I guess we’re there yet, iff we know how to ask.
Comment #9 March 29th, 2026 at 11:11 pm
=(v)( ‘)> #1: Thanks, sorry, fixed now!
finelli #3: Thanks, also fixed now! I think at some point a transcriber switched from starting the count at 1 to starting it at 0.
Glassmind Quattro #5: Thanks (and thanks to Claude), all of those are fixed now as well!
Comment #10 March 30th, 2026 at 10:39 am
Stirling formula p.37 l.-1
(n/2)^n should be (n/e)^n
Comment #11 March 30th, 2026 at 12:59 pm
A real technical issue I noticed: Homework 2.2 says, “Show that using the AND and OR gates, you can express any monotone Boolean function.” As stated, that’s false.
Reason: formulas/circuits built only from input variables using AND and OR, with no constants allowed, can’t express the constant-0 or constant-1 functions. On the all-0 input, any such formula evaluates to 0; on the all-1 input, it evaluates to 1. So neither constant function is representable. But both constant functions are monotone Boolean functions.
So the statement needs a qualification, e.g. either:
“using AND, OR, and constants 0 and 1, you can express any monotone Boolean function,”
or
“using only AND and OR, you can express any nonconstant monotone Boolean function.”
That seems like a genuine technical correction rather than just a typo.
Comment #12 March 30th, 2026 at 4:22 pm
Pascal Ochem #10: Sorry about that! Just fixed.
Comment #13 March 30th, 2026 at 7:24 pm
Figure 2 showing 3-SAT 3-color gadget looks wrong: if a, b have the same truth-value color then the 2 vertices black-line adjacent to a,b also have to have the same (opposite) truth value and therefore can’t be 3-colored since they are adjacent to each other. Also the caption says all vertices are connected to N by brown lines, so the line from the (a or b or c) node needs to be brown, not black.
FYI, the simplest 3-color OR-gadget I know of appears in my slides at https://www.youtube.com/watch?v=B5_m8lKULlI
Comment #14 March 31st, 2026 at 12:16 am
Hi Scott, my kid was in your class at Epsilon and was probably the one who talked about busy beaver and the halting problem, and unfortunately was also probably the same kid who interrupted and talked over you (he’s unfortunately been doing that to everyone since he learned to talk).
For what it’s worth he absolutely loved your class and when he came home he wouldn’t stop talking about time complexity and the other things you taught like P, NP, etc. A lot of his interest came when he was much younger from youtube (like videos on Graham’s number and Busy Beaver) as well as books like Murderous Maths. We are grateful for camps like Epsilon and Mathpath where he can not only feed his voracious appetite for different topics in math that he can’t find anywhere else at his age but also for access to like-minded kids who love math as much as he does!