Log in

Previous Entry | Next Entry

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.



( 4 comments — Leave a comment )
Oct. 25th, 2005 04:34 am (UTC)
This may be slightly off-topic, but it wouldn't hurt to have a little more of Information theory and statistics incorporated into the CompSci curriculum, considering it shows up in a lotta places like AI for example.
Oct. 25th, 2005 04:49 am (UTC)
Good call. I've been recommending information theory to lots of people. In fact, I was just recommending the EECE Noise Theory course to a CE grad, as preparation for IT.

As for fundamental prerequisits for IT: I start with the concepts of cardinality, Kolmogorov complexity, greedy algorithms (Huffman coding), and constructive derivation (block coding) - all of which were in the previous list.

Oct. 25th, 2005 04:54 am (UTC)

1. Proper understanding of big-O, omega, theta and when to use them. As in, never making the mistake of saying something like "this problem requires at least O(n^2) storage..."; also, keeping in mind that constant factors do matter.

2. Understanding the complexity classes; able to give examples of problems in P and NP; familiarity with how to do problem reductions; some intuition about when a strange new encountered problem is likely to be "hard" (in P or not).

3. Proper methods of algorithm development that focus on being able to show proofs of correctness and running-time, not just the hacky "just write code that works" style that was ok in high school programming.

4. Strong mathematical foundations would be nice; it seems strangely contradictory that mathematics majors tend to do significantly better on theoretical CS classes than CS majors, but that does seem like the trend these days!

5. Knowing that CS is not hard. CS is not baffling. CS is full of massively useful ideas where developments happen amazingly quickly and so things are always very exciting.
Oct. 28th, 2005 01:27 am (UTC)
Your list is very CS theory-centric. I might include other things like understanding some basics of computer architecture, databases, operating systems, and networks.
( 4 comments — Leave a comment )

Latest Month

December 2008

KSU Genetic and Evolutionary Computation (GEC) Lab



Science, Technology, Engineering, Math (STEM) Communities

Fresh Pages


Powered by LiveJournal.com
Designed by Naoto Kishi