[Edited slightly from original posting]

From time to time, we observe that some students appear to be spending vast amounts of time on CS lab assignments. Sometimes the time appears to be spent willingly; sometimes not. Sometimes the time takes the form of an addiction, and it's hard to say whether that's willing or not. The same comment applies to time spent due to competitiveness and peer pressure. At one level, this is willing, at another, it is not.

Do CS labs take a long time? There is a huge variance in the amount of time individuals take to accomplish any task, like riding a bicycle, learning to play a musical instrument, and so on. Some tasks require a reasonably high level of basic skill essentially before they can be done at all. Only once a certain level of competence in the basic skills is achieved can the skills be built upon to acquire new meta-skills. Computer programming appears to be a skill for which the basic level of skill is acquired by some in a couple of hundred hours, while many spend literally thousands. Also, of our students, some have acquired hundreds or thousands of hours of practice before coming to UW.

For the most part, I believe, the purpose of CS at UW is to teach various meta-concepts, not programming. However, I am not of the opinion that these concepts can be taught adequately without core competence in programming. I guess my Piagetian bias is showing; I think it is naive to suggest that the two can be interleaved to any great degree. Yet that is what we try to do. There is really no way around it, given the institutional structure into which we fit. One of the problems is that CS professors are an atypical bunch: some acquired core competence in programming in a few tens of hours; some acquired the meta-concepts while bypassing core competence in programming.

If we accept that one requires core competence, how is it to be achieved? One approach might be to require high-school CS or equivalent as a prerequisite to CS at UW. But the CS department, rightly or wrongly, is not particularly impressed with the OAC computer science curriculum, and has not necessarily found students with high-school CS to be better prepared. Also, students often acquire the attitude that because they have become extremely skilled, or so they think, at the core competence level, that there are already expert computer scientists. Finally, UW does not want to exclude those who can acquire the skills in a reasonable time and do not take CS in high school. It is my personal opinion that this view is correct - certainly doing a bit of programming before coming to UW is an advantage, but in the long run, taking some more physics, or philosophy, or languages, etc. may well be more useful than formal training in CS.

I couldn't print "hello world" on a computer when I started university - indeed, I intended to major in physics - but I caught the bug during my first CS course. There was CS in my high school (How many of you have actually used a card or paper-tape punch?), but I had acquired the not-uncommon attitude at that time that programming was a menial task. It's not clear to me that doing CS in high school would have changed my opinion at that time. CS at university did. The purpose of this paragraph is to disclose one of my biases - I don't want to exclude the potential "me"s from CS at UW. On the other chance, I'll freely admit that I'm one of that atypical bunch of CS faculty I mentioned earlier.

So much for core competence. Why might students spend a long time at the computer? Because the standards ar higher. These are not standards imposed by some sadistic professor that stays up all night thinking of trickier and trickier assignments, they are standards imposed by the compiler. Any program submitted (to the compiler) by a student is subjected to a rigorous and formal analysis, and given a grade of 0 for even the most trivial mistake! Such absolutely unforgiving and unhelpful behaviour would get a tenured faculty member fired, yet we revere it in a computer system. And every CS assignment first gets marked by this draconian TA. Even once the compiler gives the submission the nod, it doesn't even give the student a hint of all the screw-ups it noticed in their program; it just hands the work back for the student to submit for execution; yet another uncaring and unfeeling organization with impossibly high standards.

What does a student do when confronted with such a daunting task? Some regard it as a challenge to snatch victory from a system obviously designed to engender defeat. Some take a systematic approach to understanding the enemy, and to accomplish as much as possible in spite of it. Some are Machiavellian enough to get the enemy to work for them without it even knowing. Some tiptoe around ever so carefully so as not to wake the sleeping monster. Some develop learned helplessness and repeatedly whack the paddle labelled "electric shock." The simple fact is that the computer is the gatekeeper and unless a student figures out an effective way of dealing with it they are lost.

Students and instructors alike must be aware of the modes of approaching the system and be aware of advantages, problems, and remedies for each. For example, my first group, the monster-baiters, may find that poking the the monster and running for cover, fun and challenging though it may be, does not improve life expectancy. The last group, the paddle-whackers, obviously need to be recognized and offered help to cure their state. Yet entering into one or more of these states is not necessarily a bad thing; it can be a valuable part of an education as to what computers are all about. I do not advocate the construction of huge dies to stamp out students in the second category (or whatever the "right" category is). I do advocate trying to recognize the various states of being and to ensure that none is terminal.

Taming the monster is but one "problem-solving" skill. In general, when presented with a problem, we hope that students will take a systematic approach to it. In the touchy-feely faculties, they study things like problem-solving skills. The trouble with studying problem-solving skills is that to lean them (Piaget again) you have to do them. So unless you solve some problems that you heretofore could not solve, what do you learn? Please don't misinterpret me. Problem-solving skills as formalized are tremendously valuable; I just don't see them as a subject of study in their own right, and I don't see that they can be learned by talking about solving problems, or by outlining half-assed solutions to problems that would take a professional months. To bring this back to CS, I don't believe one can learn to program without programming, to build a compiler without building one, methodologies for programming-in-the-large without programming-in- the-large, and so on. To bring this back to problem-solving, I think it behooves us to present to students a toolkit of problem-solving skills and to show students how to apply the standard approaches to taming the various monsters that they encounter in our curriculum.

I illustrate this point with an example. A significant fraction of my current CS241 class wants to roast me because I required them to draw a graph with some 30 vertices and 200 edges. It turns out that the number of edges in the graph was quadratic in the number of nodes, and that solving a significant subset of the problem required about 10 vertices and 25 edges. From this smaller solution, some regularity could be observed that made the full solution congnitively much smaller, even if still the same physical size. Once the solution was understood, it was possible to use brute force to draw the graph, or to develop a shorthand notation for the solution. I invited the class to use shorthand notations, in the hope that would suggest the problem-solving skill of starting small and looking for patterns. Apparently not. But was the assignment a failure? I don't know. In terms of lessons learned per unit of student's time (and per unit of my time and the dean's time handling flak), maybe so. But I hope that at least some students acquired some new problem-solving skills via live-ammunition experience.

I intentionally chose as my first example one that was not programming. But it illustrates some of the problem solving skills that are absolutely key to programming. It is necessary to understand the problem and to understand the solution before trying to implement the solution. Understanding the problem involves asking questions, doing experiments and sending up trial balloons (can I find the libraries; do I know how to used the compiler, etc.). It is necessary to formulate a number of possible solutions. This involves brainstorming, and, after identifying a short list of alternatives, prototyping or otherwise evaluating candidate solutions to the problem. Once a single candidate is chosen, prototyping continues to yield a proof-of-concept. (When NASA went to the moon, they did a huge number of proofs-of-concept, although I read a 1964 Scientific American article that would lead you to believe they knew all the answers at that time). Proofs-of-concept are extremely important in lulling the monster to sleep - the monster-baiting approach can often be used to get a foot in the door. Compilers have a fatal flaw in their gatekeeping ability - once you have a solution to a problem, no matter how small, it usually continues to be a solution. The knowledge gleaned from a proof-of-concept may be adapted or expanded to the real solution, or may suggest a better approach.

The wall of complexity presented by the computer system is non-linear in the size of the problem. If you have to do 10 things right to get your program to work, and each has probability 0.9 of working, you have a 0.34 probability of having your program work the first time. If it doesn't work and you use stab-in-the-dark techniques to try to resolve the problems, you may think that the expected number of attempts to get a working solution is 3. But your stab-in-the-dark attempts aren't really random - this may cause you to converge more quickly on a solution or it may cause you to diverge from a solution. For example the 0.9 probability may be your best guess at the right answer and your stab-in-the-dark techniques may introduce sillier and sillier attempts (with lower and lower probabilities of success) in an attempt to gain a correct solution. Another fatal flaw is to increase the complexity of the solution in an attempt to make it right. If your program that started with 10 components grows to 20 in the debugging process, each with a 0.9 probability of being correct, your probability of success per attempt goes down to .1156.

What's the solution to the wall of complexity? It goes by many names: divide-and-conquer, modularity, abstraction, separation of concerns, Object-Orientedness, layering, reuse, decoupling, robustness. If each component can be independently verified (submitted to the monster, tested, whatever) each has a 0.9 probability of passing. As before, the chance of all passing is 0.34. You *expect* one to fail. When it fails, you fix it and resubmit it. It is small enough that your new solution has probability 0.9 of working, so it almost certainly does on the next try. Then you have to put the system together just to make sure that you didn't overlook something when you tested the components. Putting the system together can be considered an 11th component, so this strategy is still slightly worse than linear with the number of components, but its a heck of a lot better! If the 11th component (integration) fails, you must have a way to diagnose the problem and isolate the incorrect one of the original components. If you can't, you are back to stab-in-the-dark, and you might as well not have modularized it in the first place.

I should also point out that excessive decomposition into components is just as absurd as no decomposition. Then hooking the components together is just has hard as the original problem, and no advantage is gained. And you incurred lots of overhead in creating the modules.

The 11th component is made a lot easier if the system is incremental. That is, you can assemble subsets of solution and build on them. That means you can take a running system, make an enhancement, and have, say, a 0.9 probability of still having a running system. A running system is a tranquilizer that keeps the monster asleep. Don't let it wear off - give the monster a booster dose at regular intervals.

One of the approaches I mentioned above deserves special note: robustness. I assumed above that the system would operate only if all 10 components were correct. This is a badly designed system, akin to the series-wired Christmas-tree lights of 50 years ago. They had a mere 7 bulbs per string, but were often good for many hours of frustration on Christmas Eve. If one bulb was bad, you had some chance of recovering the string using stab-in-the dark techniques and 1 spare bulb. But if that didn't work you had to rely on another string of lights as a testbed to verify the bulbs instantly. Of course, a typical situation on first opening the decorations was to find *no* working strings of lights. This usually precipitated a trip to the store for one more string, from which the rest could be bootstrapped. Two forms of fault-tolerant strings of lights have been developed since then: parallel-wired lights require a high overhead (an extra wire running the length of the string) but allow each bulb to function independently - bulb failure is a trivial issue in such a design. Another approach is used in strings of mini-lights: they are series-wired, like the 50-year-old strings, but the bulbs are designed so that, when they fail, they short rather than to fuse, so that the series circuit remains intact an the other bulbs still work. This increases the robustness enough that 50-light strings are tolerable, but I've thrown out more strings of these that I care to count because the bulbs failed to short, or because the sockets or connections failed. The point is that robustness can be achieved by making systems that are insensitive to the failures of other components, or by making components that behave in a reasonable fashion even when they fail. So in Christmas-tree-lights 101, which lights should we use in the lab? Parallel so that the lights can be lit and students can head for the bombshelter? Series so that we inure students to the frustrations of problem solving? Series with shorting bulbs? All three? If you chose "all three" where do you find the time and other resources?

There are many, many more aspects to the discussion, and I'm sure there are more points that can be made on the aspects I have introduced. I solicit such a discussion.

Thanks for your attention.

Gordon V. Cormack     CS Dept, University of Waterloo, Canada N2L 3G1
cormack@cormack.uwaterloo.ca     http://cormack.uwaterloo.ca/cormack/