Scroll back to the top

Two cameras are better than one (and make for better demos, too!)

submitted by:
Tim Davis

Professor
Department of Computer Science and Engineering
CSE 629, Analysis of Algorithms

  September 01, 2020


I'm teaching a graduate course, CSE 629, Analysis of Algorithms.

I have a 2nd web cam and 2 laptops. The web cam is masking-taped to a 1950s style desk lamp, which you can see in the screenshot below. This is my document camera. I then write with color Sharpies on the paper.


image001.jpg


So they can see my face while I talk, but also my "white board". After class I scan in the hand-written notes.

I also use manipulatives. Here, I'm describing the dynamic programming technique as applied to string-edit distance, which asks what the smallest distance is from one string to another, via incremental changes (delete/insert/match). There are only m*n subproblems to solve. Here the pen illustrates one of them: what is the shortest edit distance of converting "ALGOR" into "ALTRU"? This is one of m*n subproblems for converting the string ALGORITHM into ALTRUISTIC, where m = 9 and n = 10 in this case. The pen can appear between any pair of letters, or at the ends, give 9*10 = 90 places I can put the pen.

The physical location of the pen immediately shows the student what the given subproblem is, and also can be moved around (which I do in my lecture) to illustrate that I can place it in any one of 9*10 = 90 positions.
 

So all you have to do is to solve all 90 subproblems, and you've solved the problem at hand. That's dynamic programming: solve all subproblems, save them and reuse them if reencountered in solving subsequent problems, and build up to solve the end problem. It's a fundamental method in computer science, and I find using pens / dominoes / scrabble pieces a perfect way to illustrate ideas from algorithms / computer science / discrete math.

Or I'll use dominoes to illustrate other algorithms: sorting, permutations, selection, proof by induction (falling dominoes) and so on.



image002.jpg


In the screen shot above, I'm illustrating this idea: solve the problem to find the edit distance from ALGOR to ALTRU. The result is some number. Now, extend that to ALGORI to ALTRUI, which appends the letter I onto (the converted ALGOR), obtaining ALTRUI. So the cost or distance to convert ALGORI to ALTRUI is the cost to convert ALGOR to ALTRU, plus the cost of one "match" on the letter I, to extend the solution by 1 character.

The webcam makes this possible. I can do this in a lecture hall too, but it's actually easier to teach this way while sitting at my desk online. The 4K webcam I have gives a very clear view, and standing at a podium to do this is a little trickier.

And with the 2 laptop monitors and another desk monitor, I set one laptop for "Gallery view". The students' cameras are all turned on, with mics off unless they want to ask a question. So I can see all their faces (OK, only 20 faces out of a 100...).

In this shot you can see where I see the Gallery view, in the laptop to the left. You can also see the webcam for my document camera, taped to my desk lamp.


image003.jpg


Having 2 cameras like this is essential for my teaching style. The material I'm teaching can be done with prepared slides, but I find writing it out by hand as I go, like a white-board, works better for me. Dealing with mathematical proofs is better if seen worked out step by step, and doing it on a "white board" (my paper in the doc camera, sometimes augmented with manipulatives) forces me to slow down enough to explain it.

The same style of discourse is also in the Numberphile youtube series, like this one: https://www.youtube.com/watch?v=vv0bHK44Q1s which uses pens on paper, plus manipulatives (wood cubes stacked together), to get across a deep mathematical truth.

My videos are nowhere as good as Numberphile, but I do record them and post them for the class in Canvas.