Summing up computer science
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.
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.
posted by Jacob Matthews at
22:15
2 Comments:
I know some about building NAND from transistors and from there others and then a computer, by building an ALU, some memories, etc (all that from reading Structure Computer Organization by Andrew S. Tanenbaum, a book I really enjoyed and that I am currently re-reading).
But can you tell us, for those of us less literate, who never went to college, what is the Halting Problem ?
Thanks.
By
Anonymous, at 00:35
shapr: sure, I've put up my lecture notes online now.
pupeno: check out the end of those lecture notes, and also the Wikipedia page about it, which is pretty good.
By
Jacob Matthews, at 23:16
Post a Comment
<< Home