Week 6: Algorithms

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.

Week 5: Challenges

It was a tough week. It’s midterm, students are busy and stressed. Exams in other freshmen science classes get priority over CS Principles homework. The general bonhomie of class has been replace by some tension. Nevertheless, students performed up to expectations and continued to be sufficiently engaged in the content.

Narrative on Week’s Goals

The weekly calendar shows that Friday’s assignment received a 1-day extension, and the other two assignments this week got the same treatment.

Calendar Entries for the Fifth Week

Lecture 31 Jan: The first part of the lecture continued the coverage of functions from last week, including why one would use them and the details of parameters, arguments

and the “formal/actual correspondence” relating the two. This had to be added to the plan because of having forgotten to handle the parameter details on Friday.

The listed topic was the fundamental principle of information, which I call, “The Bias-free Universal Medium Principle.” It says that bits are sufficient to represent all digital information. We have covered content relevant to this principle in several lectures, so mostly the lecture summarized that content.

Assignment 12: Students create a GUI with two buttons (Pal and Clear) plus a line where text is displayed. They are to accept text input and when the user clicks the Pal button, the text is to reverse, so they can see if it reads backwards as a palindrome. This is an exercise to learn about text input (more complex in Processing than graphics), and the three data types, char, String and String[], which will all be needed for the next assignment.

Lab 1 Feb: Students work through a lab in which they write a series of value-returning functions based on 13th Century wine merchant measures noted by Knuth: http://www.burtonmackenzie.com/2008/01/legend-of-binary-wine-merchants.html They compute the metric weight of a liquid measure by computing the weight of it’s defining measures and adding it to itself; the basis is a gill at 118 g. Brandon then explains how the function calls are executed.

Lecture 2 Feb: Realizing just before class that everyone seemed to be struggling with Assignment 12, I decide at the last minute to begin with a chalk-talk about how the computation works, and a summary of the properties of the data types: char, String and String[]. The lecture is on computational complexity. The lecture begins with linear time and ends with the halting problem; exchange sort is a concrete example of a polynomial computation.

Assignment 13: The computation shows a pond in which a turtle can be programmed to swim around, avoiding the whirlpools and going for the sunny rock. This assignment is a primitive version of the LightBot problem used on the first day. Friday (the due date) is the last day of the first half of the term, meaning that the students will have gone from users of the game to implementers. If it isn’t too hard!

Lab 3 Feb: Students have lab time to work on the turtle assignment, with Brandon’s assistance.

Lecture 4 Feb: Realizing that the turtle is at the screaming edge of the class’ ability, I decide to begin lecture with a review the logic of the turtle computation. After that the Halting problem, which spilled from Wednesday, follows. And finally, I review the high points of the course to this point in preparation for Monday’s midterm exam.

And How Did It Turn Out?

Overall, the week was our first tough one. The students are busy with other classes – freshman chemistry was having a midterm, and the relentless pace of the class was beginning to show on everyone, including me.

Monday’s lecture began covering parameter passing to recover from having omitted it with the revised presentation Friday. Susan had also recommended that I explain more directly the point of functions, which seemed curious since Friday we’d built a timer and the students had just built the Sudoku GUI using functions. It was a good thing to do, however. Parameters were received curiously – the class seemed uninterested in them. I figure that students are in one of two camps: those who had figured them out on their own, and those who were not far enough along to understand what they were doing; I can identify specific students in each group. Nevertheless they have all used them extensively now, so operationally, they know what to do.

Regarding the “bits are the thing” main lecture content, I had the sense students were thinking, “Duh,” given that most of the components of the principles came from earlier lectures. We need to state the principle, but it won’t need as much buildup next time.

Tuesday’s lab was successful, reinforcing the value-returning functions and parameters using the binary wine measures, gallon down to gill. Brandon explained how functions suspend the execution of the present function and eventually return to continue its execution using this diagram, where red is gill, purple is gallon, and time moves to the right

Wednesday’s lecture started out with a chalk talk on the homework. This turned out to be quite a success in an odd way. I was determined not to solve the homework for them, so I only explained it at a high level. The students paid attention, and then right after class, most of them turned in the homework. What I liked is that my high level description implied a decent understanding of the material we’ve been covering.

The lecture was on complexity: linear time to the halting problem. Given the prevailing exhaustion and stress, I thought students paid attention well enough. But I note that in the summary statistics from the After Image Survey, no student mentioned this lecture as engaging. It is a dry topic for most people, and the amazing aspects of it – NP-completeness, undecidibility – are not so important for beginners. I’m sure it is possible to have a sexier lecture on the topic, but it’s eluded me for quite a few years so far.

Thursday’s lab was time to work on the turtle assignment. I had forgotten to mention a detail about testing equality of strings, which caused a small bump, but only for the better students. One problem with the recent assignments – basically 11-13 – is the unwillingness of students to read the assignment through before starting. Brandon was frustrated, writing to me after lab,

Honestly, I think the students would do a lot better if they would just read the assignment start to finish instead of greedily completing tasks as presented to them.  For example, [two top students] started programming their own logic for interpreting the Turtle commands instead of looking at the flow chart (which contained almost exactly what code to use) [on the last page].

As one of my colleagues remarked, “Not reading the assignment often saves 10-15 minutes at the cost of hours of frustration.”

Friday’s lecture also started with a chalk talk on the homework. This one was not as satisfying as Wednesday’s, partly due to the fact that it wasn’t as well organized, though both were impromptu. After that, the lecture reviewed the content to date. Students were engaged, but not by how cool was the content as they were looking for hints as to how Monday’s test would go.

It was definitely the midterm slump. Despite the tough week, students still found material that they could be positive about in the After Image Survey. Susan’s summary reported few negative comments, but perhaps she is being selective [later, she wasn’t].

My recent plan to be more informal about the class structure, and to open up with more conversation is getting tested as I scramble to explain what is written in the assignment. Am I abetting their habit of not reading the assignments if I go over what I wrote out in the first place?

Week 4: Creativity

A major challenge in the AP CS Principles curriculum is teaching Big Idea #1, “Computing is a creative human activity.” It’s number one on the Big Idea list, which seems appropriate because it is one of the best features of the field. Some students are naturally creative, and they hardly need the point explained, but for most of my students, I believe this point is best “taught” by giving them opportunities to be creative, and guidance in how they might proceed. Much of this week was spent devoted to that goal.

Narrative on Week’s Goals

The weekly calendar shows that Monday’s assignment was a week of “unconstrained programming,”

Calendar Entries for the Fourth Week

Lecture 24 Jan: The lecture began by cleaning up a few details about Processing syntax and execution. Then we returned to the Albers in a Click topic to explain why I had assigned it. (It was by now a program of the past, and whatever frustration might have been engendered while programming it was gone now.) Besides being a cool application, it was making the point that computational artifacts can raise questions in other fields, this one being art. (It’s not an art class, so we were not going to answer the questions.) An example was, “If programs can create work similar to Mondrian, Pollack and Albers – famous artists of the 20th century – using random numbers, what role did the actual production of the art by these men play in their work?” “Would they have done different work if they could have experimented this easily?”

After that, the main lecture content was a firm technical foundation for RGB color, including explaining the mystery of why yellow is the combination of Red and Green. Then the task of turning “husky purple” redder became a pretext for introducing binary arithmetic, as we added intensity to Red in several steps.

Assignment 09: The assignment – it was divided into two parts – was to create four programs in Processing that would display something on the screen that would hold a person’s interest for a few moments. Four examples were given with the assignment; see the class examples page, http://www.cs.washington.edu/education/courses/cse120/11wi/classexamples.html. Two programs were to be turned in Wednesday, and two turned in on Friday.

Lab 25 Jan: The lab practiced binary addition, per the preceding lecture. Then, in the free time, students worked on their assignments. This had the benefit that they could ask Brandon for help.

Lecture 26 Jan: The lecture opened with a short description of how to print text on the screen in Processing; (it’s a graphics language, text is harder, figures are easier). Then we moved on to the fetch/execute cycle and the components of a computer. We worked through the standard content, including instruction interpretation. A full example was illustrated.

In the last five minutes, the lecture finished with an explanation of the operation of an nMOS transistor; this was motivated by the ALU evaluation of

AND <operand>, <operand>, <operand>.

I told the class that this was for their own interest and would not be on any test.

Assignment 10: It is a continuation of the last assignment.

Lab 27 Jan: This was time to work on the assignment. All but one student was present and worked steadily.

Lecture 28 Jan: The lecture began by introducing the basics of functions, including parameters and the Processing syntax and semantics. This was followed by a demo in which a timer was developed in several layers (6) of abstraction. The base layer drew the hexagonal element and it built from there. The top level ran the image at the frameRate(10), allowing the time to count “1” with each image refresh.

Timer used In Demonstrating Layered Software Development

Assignment 11: The assignment was to apply the ideas of functional abstraction exhibited in the lecture to the creation of the Sudoku GUI. The solution probably “requires” one less layer of abstraction, but it is plenty challenging for the students.

And How Did It Work?

Nearly all of the students rated the “free programming” assignments of the week as the best part, the most fun and engaging. They appreciated the flexibility of managing their time better according to the After Image survey. I adopted the new-assignment-every-two-days approach to bring the class up to speed with the programming, but now I think we can be much more flexible in the last half of the term.

The results of the “free programming” were quite variable, but most students did something quite ingenious even with their limited knowledge of programming. Several of them tried new things on their own out of the reference materials. Only the few who are really not getting the concepts failed to express themselves through programming.

Monday’s lecture was more relaxed, as planned. It was curious in two ways. First, the miracle of colored light, and the differences it has with our usual experience with pigment seemed to hold the students’ attention, but they didn’t seem to be much interested in it. We then pushed on to do binary addition, and curiously, they were interested in that.

Then, in Tuesday’s lab, Brandon practiced with them on doing addition. Later, in the After Image Survey, someone complained that they only learned about how to do binary arithmetic, but didn’t actually use it. (I thought that was what computers were for!) The bottom line: binary, interesting; light, uninteresting.

Wednesday’s lecture continued the more informal style, which went well. The informal chatter at the start concerned printing on the screen, and everyone seemed attentive; later I heard that several students had tried it successfully. The topic of how a computer works was of interest, and the indirect reference to data through the memory seemed to go across easily. Good. In the “Department of Surprises”: when I finished up with how an nMOS transistor works in silicon – a true miracle of the universe – exactly three people seemed to be interested. The rest of them, having been told that it wouldn’t be on the test – simply packed up their papers and waited for me to quit talking.

Thursday’s lab had students work on their “free programming” assignment. I’d expected Brandon would have to deal with fairly exotic problems as the students’ dreams outpaced their capabilities, but his report was contrary. There were only a modest number of questions, and most students just worked diligently on the assignments.

Friday’s lecture, which I’d looked forward to as a great chance to program in class and guide students through functions went well, but it wasn’t as much fun (for me) as I’d hoped. At the last minute I decided not to actually do the typing real time – the code was already in the slides so we could just go through it – and this meant that we did get all the way through the material. I did show off the app running. My best idea was to create a listing of the code for the students and to distribute it. This meant that students could follow along despite the fact that the displayed program text is necessarily tiny, and about 1/3 of it is too low to view beyond the second row of seats. So, in the end the decision not to develop the code in real time was probably right, but where’s the fun???

When the lecture was over, a student came forward with a question about “formal-actual correspondence,” which is the property that arguments to a function must correspond 1-to-1 to the parameters. I’d left that out. It’s a danger of the first time through, and probably would have come in the patter had I actually done the programming. So, I hurriedly made two slides and revised the posted version of the slides to include that material. I appreciated her question; it saved a lot of confusion.

From the student perspective, it was a great week. They had a chance to program, pretty much unconstrained by anything other than the computer itself. And I got them to see computers as a place where “human intent” can be expressed.

Week 3: More Processing

It was a short week because Monday’s holiday (MLK Birthday Celebration), but there was progress in learning the Processing language. The students described themselves a very engaged in learning it, and enjoyed the assignments.

Narrative on Week’s Goals

The content of the week is summarized by the calendar:

Calendar for Week 3

Lab 18 Jan: The lab exercise was to move a colored box across the Processing canvas as a simple exercise in using variables, declarations, assignments and expressions. Most students finished the task within the allotted time; three did not, but they completed it shortly after class.

Lecture 19 Jan: The lecture was a programming demonstration, designed to work with a new language feature (arcs) that required study of the documentation. The point was to illustrate incremental program development, to introduce of the mod (%) operator, and to emphasize programming as a directed process implementing human intent. The task was to program Pacman (yes, the ancient video game) to move across the screen eating pills.

Pacman Lecture Exercise

Assignment 07: Construct the Blinky ghost from the Pacman game, and using variables and expressions make its eyes move; this is preparation for the next assignment that uses mouse motions to control the ghost.

Lab 20 Jan: The lab returned to the myCSP.html Web page that the students posted in their second lab. Now with Processing capable of generating an applet to display in a browser, this lab was devoted to explaining how to modify their portfolio page, transfer the files and link them in to their page.

Lecture 21 Jan: The lecture introduced if-statements and for-statements, but also reviewed the other features of Processing that we’ve had previously in order that all of the material be in one place. There was emphasis on other resources that could be consulted.

Assignment 08: Building on the Blinky ghost code from the last assignment, make the ghost move left or right depending on whether the mouse is left or right of the ghost; make the eyes adjust to the direction of motion, and toggle color (between red and yellow) on mouse clicks.

And How Did It Work?

Student interest in Processing continued to be “strongly engaged”, despite the not-infrequent stumbles in getting it right.

On separate mornings this week two women came in to chat. To my astonishment both made the same two points: The were not technical majors (Communications, I think in both cases) and didn’t expect to like this class – but they do – and further, not being technically inclined, they didn’t expect to do well in the class – but are. This is exactly the end state of this effort, so with any luck we can carry this through and have it apply to everyone.

At the other end of the spectrum, I asked another student to come by to discuss her homework. (One benefit of this study is that we are watching students carefully, and when they don’t deliver, we know immediately.) She seemed not to be investing the time required to actually learn the material in the assignments, and so continued days later not to understand the basics. I explained that it was an accumulating class and that in the future she would have to use material she was studying today. It was a friendly enough conversation, but it contrasted amazingly with the two others.

Tuesday’s lab was very successful. It was an easy assignment, and the students knew what they needed to know to be successful. It was definitely confidence builder.

Wednesday’s lecture engendered some discussion, and in a couple of cases some very clever suggestions – the students are thinking. The mod operator was new and they grasped both the operation and use. However, I felt that the lecture did grub around in very low-level details – antialiasing for instance was mentioned to redraw the image cleanly – that just didn’t need to be covered. In the After Image survey, one student complained that it was a boring lecture, but was out-voted by five others that thought it was engaging. I’m of mixed mind on it.

Thursday’s lab was a hit. Students were happy to get their work out in a publicly available form. This also served to solidify the value of mycsp.html.

Friday’s lecture was the laundry list of facilities that we are using in this month’s programming in order to have it one place. The things that I had already taught were reviewed, to good effect, I think. It definitely took more time than I had planned for. And I got through the rest of the material, but not the last application of mod, which I’d planned to reinforce Wednesday’s lecture.

The “Blinky Assignments” (Wednesday and Friday) were very well received by 80% of the students, though again the After Image included one student thinking it was boring. (Who is this person???) I think the value of this one was that students were pretty much in control of the whole process and though it presented plenty of challenges, they were challenges that they could over come. In office hours students comment about the great feeling of “getting it”!

The students continue to be engaged and to like programming. The After Image Survey continues to reveal that they are most interested in it, as opposed to the “principles part” of the course. Given that the class was advertised as NOT turning them into programmers (and it won’t), they seem very eager to head in that direction.

With the completion of the third week, I have decided that I need to reduce the formality of the class, and make it more chalk-talky. The students like the class; I like the students … let’s try to make it more casual. I’ll start that Monday.