Computer Science Education (part 0 of N)

Besides my usual semesters of computer science courses and research, this fall I'm cross-enrolled at a neighboring university that offers education classes. Last night had some very interesting conversations. We are starting to prepare syllabi for the course we'd either ideally teach or want to be prepared to teach. I was in a group with two education PhDs (most of the class are). They consented to consider an introductory computer science course and answer two questions.

What are common naive theories that students have entering the course?
How might the course be designed to encourage students to reconstruct their theories?

So what naive theories do students have?

First, computers are magical. No, computers do exactly what a programmer tells them to do. (More advanced students learn about race conditions, compiler influence on correctness, etc). Which, unfortunately, means that if a computer is not doing what you want it to do, then you instructed it incorrectly (c.f., The rat is always right).

Second, I'm going to be a game programmer. No, most computer scientists do not write games (or at least, aren't paid to). But we find many other interesting parts to the field. Besides, many game programmers are treated little better than grad students.

Do you know other naive theories?

Then after class, I spent some time discussing more "advanced" theories in computer science.

Functional versus imperative programming. Does one paradigm exist to rule them all? Is one class of programming languages sufficient? Do students gain by learning about both paradigms? I discussed this briefly in Is versus ought, and have been regularly reading a strong function view in Existential Type.

Big 'O' notation and algorithm / data structure selection. I previously discussed this some in Know your N. And was co-author on a paper, "Brainy: effective selection of data structures", that demonstrated actual data structure selection for a program is not always best from the "Big 'O'" point of view.

Language equivalence. Related to functional versus imperative and one of my first posts, "Problem Solving via Programming", programming languages are theoretically equivalent (i.e., turning complete). But in practice languages should be selected for particular problems. What problems are best for specific languages?

What are some other major theories about computer science that students should know?

Repost: Programmer Jargon

I'd like to highlight a few of the new programmer jargons.

1 - I'm thrilled to learn of the "Yoda condition", so now I have something to call this silly way of writing the condition. Can anyone tell me why you'd write the condition this way?

8 - Heisenbugs are something I've been referring to for over 10 years.

20 - I'll need to inform students that "ninja comments" are not acceptable documentation.

Meta Post

It took 677 days, but I've now received 1000 views. Just over 50% of views are from the United States and 60% of views are from machines running Windows. Now, I'd say that I'm going to get back to research, but I'm taking today off to run errands with my wife.

Know your "N"

I once was working on some performance analysis and came to the developers asking how their code was consuming a disproportionate amount of time. At low load, the code was say 5% of non-idle CPU usage, but at high load, the code was now 50%. The developers noted that the code contained an algorithm that was O(n^2), but they had only run n=1,2,...10. My high load was n=1000, which exposed the scaling issues of their code. The developers had done everything right, except knowing the scope of the problem (and to be fair, their code was originally for desktops and I was testing servers).

Another time a developer came and discussed memory limitations, due to using 64-bit counters. I asked about how large the input was and learned it was under a billion elements. Well, a billion fits into 32-bit counters and now the memory consumption is cut by half. (Maybe I need more stories, as this was also in Bit Packing.)

The first step to any good performance analysis is selecting an algorithm, based on the problem (including its size). Bubble sort an array of 10 elements, but not 10,000. In fact, ask whether the problem really requires sorting at all.

I will continue to strongly urge developers to measure the performance of their code, before trying to tune their code. But part of this measurement is knowing the "size" of the inputs.

The Minimum of Computer Science

The NY Times ran an article at the start of last month on what CS education is required for non-majors, Computer Science for Non-Majors. Is the knowledge of how to write a (simple) program so vital to modern work that it should rank with multiplication tables, English grammar, etc? And if so, how much knowledge and in what language(s) should this be taught?

Should someone learn the basics of javascript, so they can add to webpages? Perhaps a little python to do simple processing of data? But probably not C, as the language expresses what the computer is to do and not what the computer should do.

Edit: A strong response to this general question here.

Rules of Computer Science

As I've spent these many years learning and practicing computer science, I've come to have a couple of "rules" (i.e. guidelines) of programming.

1) If a computer can execute something, you can write it in C. (aka Turing-completeness)

1a) Still, it is probably faster to write the program in a high-level language.

2) The computer does what it is told to do. There is no magic.

2a) If a behavior is not what you expect, then you don't know what you told the computer to do.

I am sure there are other such "rules", so please share if you have other maxims from your time and experience.

Usage of NULL

I read an argument recently about whether a test for NULL should be:

if (ptr)

- or -

if (ptr != NULL)

Do you know that the assembly for these two sequences is the same? So the first has not optimized the running time of the program. But it does save 8 characters, which mattered long ago. But now we have plenty of disk space. So always write the test for NULL by actually testing against NULL. Or I'll come take off style points the next time I'm grading. (If you are writing one-use code, which no one will see then go ahead.)

Separately, the operating system provides explicit support for NULL. It sets up every process's virtual memory so that virtual addresses 0x0 - 0x3ff (and possibly more) have no mapping so any access to NULL will never be valid.