Uncharacteristically for me, CS Principles has covered functions, functional abstraction and creativity heavily, and not mentioned algorithms much at all. It reflects, I think, the big ideas pressure to faithfully handle tough concepts, which for me means taking aim at them at the start and staying on target. Easier topics such as algorithms can come along when the trajectory is established. So, this week we gave a definition of algorithm, did recursion, and addressed correctness.
Narrative on Week’s Goals
The weekly calendar shows that Monday was the midterm exam, and students got Tuesday off, since they have been working so hard.
Calendar Entries for the Sixth Week
Midterm 7 Feb: Being at an ACM Education Council meeting over the weekend, I’d selected this day for the mid-term. The exam was mostly short answer and a few multiple choice questions tossed in. I had allowed each student to bring a single, handwritten sheet of notes to the exam to thwart the anxiety of “memorizing” stuff.
Lab 8 Feb: Class canceled.
Lecture 9 Feb: The topic was Algorithms, and I believe it is now generally less intimidating than it was a decade ago. Students have apparently heard it a lot. I gave the standard Knuthian definition, and then moved on to recursion. My goal was simply to explain it without making it into any sort of big deal. (There had been a request for everyone to return to the Lightbot recursion problems as a refresher.) Standards like fact( ), fib( ), sierpinski( ) are given. The scoping of formal parameters is explained in order to show how recursive functions are executed. Finally as an antidote to the orderliness of sierpinski( ) I show a Processing Reference Library program for recursive random circles. The first three levels are easy to see.
Recursive random circle program from the Processing reference library.
Assignment 14: The assignment is to use a program for a recursive enumeration as the basis for a different recursive enumeration. The purpose is to work from a closely related program as a guideline.
Lab 10 Feb: Time to work on the recursive enumeration with Brandon’s help.
Lecture 11 Feb: The lecture asks the question, how do you know that your program computes what you think it does. This is a “correctness” lecture, and I use sorting for the purpose. The main point is emphasized by noticing the comparison patterns of Exchange sort and Bubble sort; they are different, but each is the basis for arguing that it works as claimed.
With twenty minutes of lecture left, Susan takes over to present the concept of Pair Programming, and to introduce an assignment that uses the methodology. Using the responses from a survey collected in the previous lecture, she assigns pairs based first on matching their abilities, and secondly on finding compatible schedules so the teams could meet.
Assignment 15: Pair Programming. Develop a game using processing. Any game is OK provided it isn’t beyond the team’s programming skills. First the game has to be developed on paper, and treat the following topics: rules, description of play, clear way to win, clear way to lose, and how the game can be restarted without being rerun. The plan must be approved by someone on the teaching staff. The teams can only work on the computation when they are together, and only one of them is allowed to type. Goals include learning how to describe computation to a colleague.
And How Did It Work Out?
Monday’s midterm exam showed that students had acquired a good understanding of factual material, could write a standard Processing program (essentially, a portion of their second lab on Processing), and are still struggling some with details of functions, such as using void when there is a return value. Among the remarkable-to-me results was that all students got all points on the binary addition question, implying that I don’t have to ask that one again. (More analysis of the exam when it’s in.) The single sheet of notes worked well.
Wednesday’s recursion lecture was reportedly engaging by a substantial portion of the class, which was my assessment, too. The goal of presenting recursion without making it so important that it becomes something to panic about seems to have been achieved. It was a waste to explain the formal parameter scoping needed to explain why recursive programs “work”. No one was interested in it. I won’t do it again.
(In this class especially considering that the material is (to me) fascinating, and deep, there is always the issue of when to “quit”. I believe explaining parameter scoping is not the first time I’ve crossed over the line this term, and a postmortem would be indicated to find other instances.)
Thursday’s lab was frustrating for Brandon because the students were supposed to use strange UTF-8 characters (♥) and there are apparently bugs in Processing’s ability to include these in a computation. Most students got it to work, but that complication coupled with the student’s habit of not reading the instructions, kept it from being the “programming by analogy” success I was hoping for.
Friday’s lecture was extremely satisfying. The students followed along well, and I was able to make the “know why your code’s correct” point without the dreadful detail used in, for example, the Fluency with Information Technology book, Ch. 10. The key was to use schematics of the traces of the binary comparisons.
Comparison Patterns for a 5-element Exchange sort (l) and 5-element Bubble Sort (r); time goes down.
I believe these two diagrams effectively made the point that algorithms operate differently, but there is an abstraction for any one of them that can be used to reason why it is does what’s claimed for it, i.e. sort.
OK, so students were following along, and I was making my points. But when Susan took over to do pair programming, the whole behavior of the class changed: they straightened up, paid close attention, answered and asked questions. They became the definition of engaged!
Thanks to her, the week ended on a high note. We entered a new regime with more time for assignments, more discussion, and more variation in what we do. It’s more relaxed. This has been greeted with approval.