Part of a course I'm teaching on the Why and How of Computing (not the High and Wow of Computing as I sometimes imagine) is a gentle introduction to programming. The idea is that to fully grasp the culture of we geeks, you must grasp our obsession with problem-solving. We usually write our solutions down as algorithms, often in formal programming languages.
This semester I've been using a particularly user-friendly environment called DrRacket that lets the user choose from a tower of languages from beginner to expert. The idea is to have level-specific capabilities and error messages. I was skeptical until I noticed that common mistakes seem to get meaningful error messages. For example, if I try to define a function with parameters (place-holders) that are literal numerical values, the error is
define: expected a variable, but found a number
... considerably more informative than the generic invalid syntax I find in another language used by beginners.
This, and other features of the DrRacket environment made me hopeful that my students would find it approachable. I was still worried about my discipline's tendency to work from manuals and texts (even when these are online), whereas techniques as diverse as biochemistry and banjo picking are taught via video tutorials. I decided to make a few introductory videos (very labour intensive, it turns out) available to get my students started.
Something must have worked. My first quiz was meant to enforce the related tutorial exercise: work the exercise and you'll ace the quiz. I left a generous amount of time for the first quiz, and asked them to evaluate a variety of expressions involving images, arithmetic, strings, and true/false. I hoped most would get perfect, but assumed that there would be a combination of late-comers and some assuming that the work of the course hadn't started yet, and that they would contribute a significant portion of 0/2 or 1/2 scores. What happened was that the quizzes were returned in record time (2 minutes, roughly) and are overwhelmingly correct.
It's always strangely surprising when something works out.
Saturday, September 22, 2012
Full binary chocolate trees
Something weird happened on the way out of lecture.
I had presented two problems in complete induction, a proof technique. The first was about full binary trees --- trees in the graph-theory sense with nodes that have either 0 or two children. The second was about how to break up chocolate bars.
I should have suspected there would be a connection when I remarked, a couple of times, that "non-empty full binary trees" was quite a mouthful: the result to be proved did not apply to a full binary tree with zero nodes (an empty full binary tree, so to speak). Except for the zero case, full binary trees have an odd number of nodes, and we prove it using the fact that subtrees are also full binary trees.
The chocolate result is that you can break up a rectangular array of n chocolate squares into individual squares with n-1 "breaks." Breaks have to cleave right across, either lengthwise or widthwise, and although the result applies to a somewhat wider class than rectangular arrays, you can find counterexamples if you allow weird cases of three chocolate bars pasted together precariously on their edges.
I'm working my way through a line of students after class who have questions or comments. One is staring into space, so I ask what's up. "I'm thinking about graph theory." The student draws a tree with the original chocolate bar labeling the root and as you break it into two, you label the two children with the resulting bars. And so on, until you have individual squares.
The resulting tree is a full binary tree. A non-empty one, since who would go about breaking up zero chocolate squares? Applying the chocolate result to trees we see immediately that a non-empty full binary trees have one more leaf than internal node.
The most wonderful part of the encounter was that my student assumed that I was leading the class toward this connection when I presented the two topics together. I hadn't, but I was flattered by the assumption.
I had presented two problems in complete induction, a proof technique. The first was about full binary trees --- trees in the graph-theory sense with nodes that have either 0 or two children. The second was about how to break up chocolate bars.
I should have suspected there would be a connection when I remarked, a couple of times, that "non-empty full binary trees" was quite a mouthful: the result to be proved did not apply to a full binary tree with zero nodes (an empty full binary tree, so to speak). Except for the zero case, full binary trees have an odd number of nodes, and we prove it using the fact that subtrees are also full binary trees.
The chocolate result is that you can break up a rectangular array of n chocolate squares into individual squares with n-1 "breaks." Breaks have to cleave right across, either lengthwise or widthwise, and although the result applies to a somewhat wider class than rectangular arrays, you can find counterexamples if you allow weird cases of three chocolate bars pasted together precariously on their edges.
I'm working my way through a line of students after class who have questions or comments. One is staring into space, so I ask what's up. "I'm thinking about graph theory." The student draws a tree with the original chocolate bar labeling the root and as you break it into two, you label the two children with the resulting bars. And so on, until you have individual squares.
The resulting tree is a full binary tree. A non-empty one, since who would go about breaking up zero chocolate squares? Applying the chocolate result to trees we see immediately that a non-empty full binary trees have one more leaf than internal node.
The most wonderful part of the encounter was that my student assumed that I was leading the class toward this connection when I presented the two topics together. I hadn't, but I was flattered by the assumption.
Subscribe to:
Posts (Atom)
