October 22nd, 2005


Computer Science Meme

If you are a computer scientist, or have something to do with CS, reply here, and post this in your LJ:
Name five principles of computer science that you think everyone with a CS degree should understand.

Here are some from yesterday's post and a new one:

1. Forms of recursion: linear, tree, tail
2. Inductive theorem proving and the relationship among weak, strong, and structural induction
3. How to derive and write a constructive proof, understanding the dialogue aspects of a proof
4. Proving the cardinality of sets: specifically, diagonal arguments and their ramifications
5. "We are not here to program computers; computers are here to run our programs." -E.W. Dijkstra

That's one of the ultimate garbage in, garbage out statements, delivered in the pithy style that was uniquely Dijkstra's. There's an even better quote from his article "On the cruelty of really teaching computer science":
It really helps to view a program as a formula. Firstly, it puts the programmer's task in the proper perspective: he has to derive that formula... the programmer's task is not just to write down a program... his main task is to give a formal proof that the program he proposes meets the equally formal functional specification.