So I've been pretty busy working on an ECOOP paper recently — more about after it's actually done — but I thought I'd report on my class, now that I've done all the lectures and I'm just waiting for people's final projects. I got through all the material I had wanted to cover with a spare lecture to go, so I made a lecture that I've wanted to do for a long time: build up all of computer science from transistors all the way up to the Halting Problem.
I had an hour and a half to get through that, so obviously I had to, err, summarize
large portions of that material, but I still covered some of my favorite topics in a fair amount of detail. I showed how you'd build a NAND gate out of transistors (skipping the messy electrical bits like resistance because I'm an electricity imbecile), then built up NOT, AND, OR, and XOR from that, and from there did latches and briefly touched on clocks and timing. From there we quickly got to compilers and operating systems (both of which were just glanced upon), and from there applications like networking and databases.
After that I pointed out there are a lot of things that are the same between all these areas, and that database writers and operating systems writers and so on shouldn't have to independently figure out how fast their algorithms are or how to verify they work. That let me start talking about algorithms and big-Oh notation. From there you can ask whether there are any problems that require
a certain amount of time, and that let me skim the proof that it takes big-theta(n*log n) to sort a list of numbers given only a comparison function. From there I was able to explain P vs. NP (though I think I sort of botched this part) and then ask whether there might be programs that you can't solve at all, no matter how much time you had. That led me to the Halting Problem, and that's where I left it.
I think these sorts of big-picture lectures are really important to an intro class, particularly when it's about a subject like computer science where the discipline isn't obvious to outsiders. I'm sure the students only got a very superficial understanding of the subjects I was talking about, but that's what the rest of the major is for.