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!
Comment #15 March 31st, 2026 at 9:31 am
Albert R Meyer #13: [forehead slap] Thanks for pointing out! I’ll take a look and correct as needed as soon as I have time.
Comment #16 March 31st, 2026 at 9:32 am
SK #14: That’s so nice to hear! I’m grateful for these camps as well. And if your kid is the one I think he is, it was an absolute privilege and delight to be able to teach him.
Comment #17 March 31st, 2026 at 10:27 am
Glassmind Quattro #8
Neat stuff and really like the portrayal using form and function.
Comment #18 March 31st, 2026 at 5:24 pm
Scott, did you get any questions regarding modern LLMs and AIs in general from the kids? I probably would have been extremely curious to know how these systems actually work, if I had known anything remotely like modern LLMs existed on earth, even at that age.
Another slightly tangentially related question to QM, which I couldn’t really find a clear answer to, would be great if I could get an answer to this:
Is there any interpretation of QM, that takes the wave function to be objectively real, in the sense that something surely is there whatever may it be (at least as real as atoms, black holes, humans, EM fields etc.) and yet is not a version of many worlds?
So the wave function as described is completely real with all its mathematically irreducible parts and “branches” and whatnot. And yet somehow you look at those “branches”, mathematical features and are able to say, no there is no one there. I guess the Bohmian interpretation maybe one, but if we discard that, (for issues with contexuality or spin or QFT) is there any such interpretation that accepts every bit of the wave function and all the degrees of freedom needed to describe it to be real, objective and yet is far from a many worlds type interpretation.
Basically, am I forced into considering other branches as equally real and hence forced into many worlds, if I say the wave function is objective, or is there another middle way?
Comment #19 April 1st, 2026 at 1:32 am
I used to teach summer math and theoretical computer science courses to junior high school and high school students in summer camp. Not as good as yours though. You have a great talent to explain things in a fun and interesting way. It was really fun, but I have got too old for dealing with teens. Dealing with 20 teens needs a level of patience that I no longer possess.
Comment #20 April 1st, 2026 at 12:53 pm
David #11: Sorry I missed that. Yes, when I have time, I’ll clarify that the constants 0 and 1 are assumed to be free.
Comment #21 April 2nd, 2026 at 11:12 am
PS to comment #13. There is a simple fix to your 3-color (a OR B OR c) gadget, namely, remove the brown lines touching the unlabeled nodes. I would also suggest removing the two node labels “a OR b” and “a OR B OR c”, which I found misleading. Actually, your node labeled “a OR B OR c” could just be replaced by the green T-node for a further simplification.
You don’t need the OR-gadget linked in my previous comment #13. This OR-gadget serves nicely in a general SAT to 3-color reduction, but is more complicated than needed for a 3-SAT to 3-color reduction.
Comment #22 April 2nd, 2026 at 2:42 pm
Wonderful notes! I’m stealing some insights for my own ones!
There might be another typo on page 8: you write OR = x+y+xy but I would write x+y-xy .
The two expressions might be equivalent in mod2 but I’m not 100% sure.
I know I’m late but I hope you had a peaceful Passover with your dear ones.
Best,
K.
Comment #23 April 3rd, 2026 at 12:30 am
notGPT #18: Yes, I’m sure there was conversation about LLMs (when isn’t there?), although I can’t remember the details.
As world-changingly important and exciting as generative AI is, I’d say it actually doesn’t lend itself all that well to a math camp, because no one really understands why it works, and to the extent we have theorems about it at all, they’re very hard to explain and motivate to 11-year-olds. And more prosaically, of course, if you get into the habit of using AI to solve math puzzles then you’ll never learn how to solve them yourself.
The two best-known interpretations of quantum mechanics that are unabashedly realist about the wavefunction are, indeed, Bohmian mechanics and many-worlds.
Comment #24 April 3rd, 2026 at 12:32 am
LK2 #22: Yes, + and – are equivalent in mod 2 arithmetic (but I should point that out explicitly, if I don’t already!).
Comment #25 April 3rd, 2026 at 1:27 pm
OK, all the corrections above should now be applied—let me know if you see any additional problems!
Comment #26 April 3rd, 2026 at 4:34 pm
Hi Scott, I’ve been enjoying these notes and the explanations are fantastic! While going through the section on binary arithmetic on Page 3, I noticed a small typo in the addition example.
The image shows the sum of 21+7=28 resulting in 11000
However, while the carries are marked correctly, the final binary sum should be 11100
Just wanted to flag it so it could be corrected for future readers. Thanks for making these resources available!
Comment #27 April 3rd, 2026 at 4:40 pm
Keshav Bhateja #26: [forehead slap] thanks, fixed now!
Comment #28 April 15th, 2026 at 4:33 pm
This is amazing! Previously ACSL and CMIMC were the only other things that come to mind for me for “CS with paper and pencil” resources. I will definitely be referencing your notes in the future.
I have one tiny pedagogical suggestion, which is that I think an intro class like this could benefit from a couple more homework questions/examples with different formats that focus on working through algorithms. I’m thinking of something like the tracing table exercises from ACSL’s “what does this program do?” questions.
Also, a question for the people here who’ve been around kids recently: where do you think they learn about something like Diffie-Hellman from? Are there new series of books or other STEM content for kids to look out for?
Comment #29 April 20th, 2026 at 4:58 am
Thank you and everyone involved for the notes. I might use them if I ever end up telling kids about comp. sci.
Comment #30 June 20th, 2026 at 8:26 am
[…] the Trevisan Prize and give an after-dinner speech, then to Epsilon Camp where I’ll again teach theoretical computer science to 11- and […]
Comment #31 July 18th, 2026 at 3:38 pm
[…] plane to Utah now, for the next iteration of the wonderful Epsilon Camp, where I’ll again be teaching theoretical computer science to 11- and 12-year-olds. But feel free to discuss in the comments! Nothing about world affairs in this thread please, just […]
Comment #32 August 7th, 2026 at 5:42 pm
[…] been teaching theoretical computer science to 11- and 12-year-olds at Epsilon Camp, something I blogged about last summer (here are my lecture notes). This has become a highlight of my year. The kids are a joy to teach, […]