Shtetl-Optimized

In the next-to-last GITCS installment, we cover some of the greatest hits of the 70’s and 80’s.

• Lecture 16: Private-Key Cryptography

• Lecture 17: Public-Key Cryptography

• Lecture 18: Cryptographic Protocols (including: how computer scientists date!)

• Lecture 19: Interactive Proofs / Machine Learning

(Something tells me Lecture 18 is going to get more hits than the other three combined…)

The course itself ended two weeks ago; last week was the final exam. Thanks so much to all of my students for signing up for a brand-new course, asking probing questions, enduring my excruciating jokes, and doing a fantastic job with the notes. (Of course, thanks also to my eagle-eyed readers for spotting errors.) Thanks above all to my TA, Yinmeng Zhang, who went way beyond her job description to work with students individually, tell me when I was being a doofus, etc. Because of the input of everyone who participated, this course will be better when I teach it the second time around.

Also, for anyone who might want to teach a similar course, the recipe is simple (much simpler than I expected, actually):

1. Start with a standard, off-the-shelf, undergraduate computability and complexity theory course.
2. Cut out the most boring parts, like pushdown automata, context-free grammars, and 10⁵⁰⁰⁰ NP-completeness reductions. (Yes, I know these things can be taught in a non-boring way, but why make it hard on yourself?)
3. Fill in the gaps with more interesting material, like zero-knowledge proofs, computational learning theory, or quantum computing.
4. Add a pinch (to taste) of mindblowing results that can’t be covered in detail, like the PCP Theorem, the independence of the Continuum Hypothesis, or cosmological limits on computation.

Serves 10-100.

Follow

Yeah, yeah, I know. Combination of the end of the semester and family matters. But I’m back with four more GITCS lectures:

• Lecture 12: Space Complexity and More

• Lecture 13: Randomness

• Lecture 14: Probabilistic Complexity Classes

• Lecture 15: Derandomization / Crypto Double Feature

Comments welcome as always.

Follow

A few more lectures, hot off the Turing machine tape:

• Lecture 8: Polynomial Time
• Lecture 9: P and NP
• Lecture 10: NP-completeness
• Lecture 11: NP-completeness in Practice

Yeah, it’s all standard material, but if you don’t know it … well, this is one more place you can learn.

Apropos of computer science education, some of you may have heard the sad news that the College Board is killing the AP Computer Science AB test [Slashdot] [Pontiff]. The reasons they gave were that (1) not enough students were taking it and (2) of those who were, not enough were underrepresented minorities.

I took the AB test in ’96, despite not having taken the course (my high school didn’t offer it) and not knowing Pascal (the language they still used, before they switched to C++ and then Java). I did read a book to prepare, and that’s where I got my first exposure to O-notation, linked lists, and other crumbs from the feast table of theory. I devoured it all like a hungry dog licking the floor.

It goes without saying that high school students (including underrepresented minorities) won’t take an AP course if it isn’t offered, or if their schools or the colleges they’re applying to don’t take it seriously. Computer science education is a threat to many people’s pet ideas about the world: that CS is not a real subject and is devoid of intellectual content. That everything having to do with computers is mundane and technical, and should (for that reason) be outsourced to China and India. That if we must teach CS, we should at least focus on applications, and get rid of any math or logical thought. That CS is passé, a 20^th-century relic that was long ago superseded by the life sciences (haven’t computer scientists gotten the message yet?). Against this backdrop, it’s not surprising that the AB test is being killed: what’s surprising is that it lasted so long.

Blogging will continue to be sporadic, as I have a cold.

Update (4/10): Lenore Blum just gave a talk here at MIT about the future of CS education, in which she echoed several themes of this post, but also argued (among other things) that the cancellation of APCSAB is good news given the course’s obsessive focus on the details of the programming language du jour, and given high schools’ refusal to treat it as a real academic subject, instead grouping it with “electives” like woodshop and metalworking. She held out hope that the US will someday develop a reasonable K-12 computer science curriculum, pointing to successful models from Israel and New Zealand. Needless to say, I have mixed feelings about canceling the mediocre (AB), keeping the truly bad (A), and hoping for the distant good.

Follow

For those who missed it on the sidebar, we now have six more GITCS lecture notes available:

Lecture 2: Logic

Lecture 3: Circuits and Finite Automata

Lecture 4: Turing Machines

Lecture 5: Reducibility and Gödel

Lecture 6: Minds and Machines

Lecture 7: Complexity

More are on the way — compared to the Democritus notes, it’s so much easier with others doing the writing! These notes were prepared almost entirely by the students, with only minor editing from me and Yinmeng. In general, I think the students have been doing a fantastic job. On the other hand, if you rely on these notes to build a Turing-machine-controlled jumbo jet which then crashes in the Himalayas, it’s entirely possible that it wasn’t my fault.

Follow

For those who’ve stopped following the Democritus series, there’s another train leaving the station today: the first lecture of my new undergraduate course (“Great Ideas In Theoretical Computer Science”) is now available.

After whetting the appetite by describing how theoretical computer science has finally let humankind achieve one of its noblest aspirations (playing roulette over the Internet), the lecture then goes back to antiquity, and covers the hottest results in the computing world circa 300BC: Euclid’s GCD algorithm and the “straightedge-and-compass” model of computation.

(One word of warning: the lecture notes were written by my teaching assistant, Yinmeng Zhang, and do not faithfully reflect what I said in class. They’re much better than what I said in class. She even had the gall to improve my jokes.)

To preempt the inevitable questions, two remarks about the course’s title:

1. I considered calling it just “Great Ideas In Computer Science,” but then I realized it would have to be a week longer. (Har har, just kidding! Cue cymbals.)
2. Any relation to the famous CMU course designed by Steven Rudich (“Great Theoretical Ideas In Computer Science”) is obviously a coincidence. The philosophies behind the two courses are every bit as different as their names.

Follow