This lecture was Computational Geometry and the Tablet PC. The goal of the lecture was to give a practical introduction to Computational Geometry, and to present a few key algorithms in detail. About 10 students were present for the lecture. HP TC1100 Tablets were deployed to all students, and the SIGCSE version of Classroom Presenter was used (version 1.10.5). The machines were connected using the department wireless network. Classroom Presenter was launched through conference XP, with FEC set to 200. The setup corresponded to what we are planning for SIGCSE - I wanted this to be a confidence building measure (which it was). Setup was a bit rushed - but everything went fine - there were no significant technical problems. (One student reported seeing an exception - although it is not clear what it was). The lecture was being filmed for creation of a course video - I do not believe that the filming impacted the class at all. As the lecturer, I was completely oblivious to the cameras.
Preparation for the lecture was fairly time consuming. I chose three basic topics - geometry primitives, intersections, and convexity. As soon as I started thinking about classroom activities, I was once again forced into thinking about learning goals. After a considerable amount of time, I realized that the goal was for the students to gain a sufficient understanding of a few key algorithms that they could implement (or rederive) them. I felt that this understanding could be demonstrated by tracing out some key steps of the algorithms. I only got through 15 of 33 slides, and ended up leaving off all of convexity. It would not have been realistic to get through all the material, given the number of student submission activities. I did not rush material, and I deliberately decided towards the end of class to cover the one algorithm in depth, instead of attempting to get to the next topic. There is a clear tradeoff in depth vs breadth in this style of teaching. Class length was one hour and twenty minutes, although I probably started 10 minutes late to allow students to arrive. Setup for the lecture was fairly efficient - maybe slowest step was plugging each of the tablets in to power. It was very helpful to have a student who arrived slightly early take care of some of the setup details. Several extra tablets were set up as "hot spares", but not needed.
Each student had a tablet to work on during the lecture. On many of the activities, there was discussion between students, which I considered to be a positive thing. There was no expectation of work being done on an individual basis. At the end of the lecture, there was discussion among several of the students on the details of the algorithms. Students were fairly engaged in the lecture, and there was little random doodling on the tablet. At least one student changed to free navigate mode to explore the rest of the lecture.
Self Portrait I began the lecture with a student submission asking for students to submit self portraits. The theory was that this would get the students to immediately start doing something with tablets, and also give them an immediate recognition of their contributions. This seemed to work well.
Interpolation The first "real" submission was a quick exercise about interpolation
of points on an ink stroke. The TabletPC ink SDK allows fractional indices, so I asked
what is the meaning of "Points[6.4]" on a slide that showed the stroke, so it could be answered
by drawing on the slide. I would usually have asked this as a throw away question to the
class, but the student submissions allowed for all students to provide an answer. Two separate
answers were supplied - a linear interpolation (which I expected) and an interpolation on the curve - which I did not
expect. These two separate answers allowed for a brief, unplanned digression. Some answers were just written, or
were with imprecise circles.
Line Intersection Test The next student submission was a planned exercise to show how to use the Counter Clockwise
Test (Left of test) to determine if two line segments intersect. The exercise is moderately challenging, and was planned
for about five or ten minutes. This is a type of exercise that I would put on a homework assignment. A series of solutions
came in after about five minutes. It was very difficult to evaluate the solutions as they came in - a number of the solutions
initially appeared fairly tricky using an XOR - analysis of the solutions after lecture showed several correct solutions -
although at the time, I did not know if solutions were correct. My planned solution was actually quite different from
what the students came up with. If I had been expecting the XOR based solution, I would have been able to evaluate these
much better. My approach on this problem was to pick one of the solutions, and analyze it on the fly. The one I chose was
partially correct, and worked quite well - I was able to make a series of points about the computation using the slide.
The red writing is mine, black is the students.
After lecture analysis of these solutions gave a very different impression that I received during class. Two pairs of
solutions had initial mistakes and corrections - I did not realize these were different, or that they were correct. Both
solutions did a test to see if each line spanned the other (one with XOR, the other with == !), and then combined the results.
The solutions also had small pictures used in the discovery of the solutions.
Several other solutions were presented in a less formal manner. These were all difficult to analyze while giving the lecture
although were easy to figure out after class. These types of exercises point of the challenge of working with student
problem solutions. In a different class, another instructor used the student submissions to point out the challenges of
evaluating work, and presented different ways of making their work either to understand. The ability to display student
work was critical in this process. The instructor was able explain to the students why it was in their interests to make
their work clear.
The next exercise turned out to be more involved than planned and maybe took too much time. The question was how many
intersections could a group of K line segments have, although this was phrased in a more complicated manner, of asking
how many self intersections could a stroke consisting of K segments have. Several students came up with a quick solution
which they gave as a formula, and when prompted, gave more details. The solution was a degenerate solution, where all
segments were the same point. I had talked about degenerate cases earlier, and did not exclude them on this problem.
After receiving these solutions, I asked for non-degenerate solutions.
Even though several students recognized that there was a quadratic solution where all points intersected, little
immediate progress was made in coming up with a construction. I started walking around the class, and noticed a couple of
linear solution, and asked a student to submit the following, which I displayed to the class.
This led to two quadratic solutions, one which has the right idea, but it is not clear how it generalized, and the other
which gives a general solution. In retrospect, a better activity might have been to drop the condition that the segments
formed a stroke, and just ask for a group of segments with quadratic intersection.
The final exercise was carefully designed so the students could step through the sweepline algorithm for finding
segment intersections. Three lecture slides preceded the activity - a slide where an example was done at a high level,
a slide with some of the key details of the algorithm, and then a more detailed walk through of the algorithm. The detailed
walk through was done to highlight when the intersections were identified. There was considerable discussion with the
students on the example. The use of digital ink was key to the discussion. The results of the student submissions in this
case had a very similar form - submissions were received from only about half the students which probably indicates that there
was some misunderstanding of the task or the algorithm. The first of the four solutions shown below was discussed. This
one was chosed because it was mostly correct, but had one error for discussion. The placement of the label B could occur in
two separate places - as the algorithm was described, the best answer would have been to duplicate the label B.