tag:blogger.com,1999:blog-6555947.post5329426920541848746..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: More experiments in algo-teachingSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-6555947.post-54750174001352189162009-03-16T18:55:00.000-06:002009-03-16T18:55:00.000-06:00Hi:Here are some fun examples that I have used in ...Hi:<BR/><BR/>Here are some fun examples that I have used in algorithms courses (undergrad and grad) over the years. <BR/><BR/>1) Cheney's card trick: Originally Cheney (apparently the first Ph.D. in Math from MIT) developed it as a trick done by two performers A and B. Initially, A is on stage, B is away. A gives a deck of cards and asks the audience to choose 5 cards from the deck. She examines them and selects one, shows it to audience and puts it back in the deck and leaves the other four cards on four vertical place holders on the table and leaves the stage. B then enters, looks at the four cards in display and announces the five card. <BR/><BR/>I perform this trick in my class as follows: I play the role of A, and my laptop will play the role of B (or vice-versa with a different applet). <BR/><BR/>One can show that the trick can be done with a deck of size 124 (but no larger) using Hall's theorem.<BR/><BR/>2) The next one superficially resembles the above trick. A pulls out the spades from a deck of cards (as usual B is away) and asks the audience to select 7 of them and hand it to her. A examines them and places them on 7 vertical place holders - all cards facing down - and leaves. B enters and can be questioned about any specific card - for example, is J of spades one of the cards in display? Since all the cards are facing down, B has no way of answering this question without a wild guess, so B is allowed to take one peek - he can choose to look at one of the cards and should then correctly answer the question.<BR/><BR/> The idea underlying this is Yao's perfect hash function (from the paper "Should tables be sorted?"). <BR/><BR/> 3) This one is performed with a deck of blank cards. Thus each card has a design printed on one side and white on the other side. There are seven vertical place holders for cards on the table. A gives four cards to someone in the audience, and asks him/her to place them in the first four slots so that each card has either printed side or the blank side facing front. Then A adds three more cards in slots 5, 6 and 7. Finally, A asks the audience to flip one of the cards after she leaves. B comes in and identifies the flipped card.<BR/><BR/>This one, of course, can be implemented using Hamming code.<BR/><BR/>It is somewhat interesting that they all have similar themes - two performers in which one of them is the computer, but based on very different models.<BR/><BR/>I have created a series of such tricks ahd have tried them at different times.Bhttp://www.blogger.com/profile/00912885685559214269noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-80327781876343711222009-01-01T13:30:00.000-07:002009-01-01T13:30:00.000-07:00You can also sort by height a bunch of students fo...You can also sort by height a bunch of students following different algorithms. I usually do it with freshmen and they have fun while learn insertion, selection, merge...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-29084303688648762452008-12-29T11:23:00.000-07:002008-12-29T11:23:00.000-07:00And here's the video of the scene. Isn't the inter...And here's the video of the scene. Isn't the internet great ?<BR/><BR/>http://www.youtube.com/watch?v=tc1awt6v2M0Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-80164208108235419862008-12-29T11:17:00.000-07:002008-12-29T11:17:00.000-07:00And here's some discussion on the game theory of t...And here's some discussion on the game theory of the scenario:<BR/><BR/>http://www.quantitativepeace.com/blog/2008/07/the-dark-knight.htmlSureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-70265712985908193102008-12-29T11:15:00.000-07:002008-12-29T11:15:00.000-07:00Oh dang. of course. I was thinking about the dilem...Oh dang. of course. I was thinking about the dilemma earlier facing Batman, of which person to save of the two being held captive.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-24744055183031981682008-12-29T11:13:00.000-07:002008-12-29T11:13:00.000-07:00At the very end of Dark Knight (um, spoiler) the J...At the very end of Dark Knight (um, spoiler) the Joker tells each boat that if they blow up the other then they will be saved. Of course, it ends in the unlikely way (in terms of the prisoners' dilemma) where neither boat is blown up.sorellehttp://kdphd.blogspot.comnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-54009107382228531932008-12-28T21:15:00.000-07:002008-12-28T21:15:00.000-07:00I just saw the Dark Knight ! which two boats clip ...I just saw the Dark Knight ! which two boats clip are you referring to ? <BR/><BR/>And as for material, I linked to all the material that I use: the rest is just my own notes, and me waving my hands around :).Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-67259997751098418212008-12-28T21:09:00.000-07:002008-12-28T21:09:00.000-07:00It seems like it should be possible to compile a w...It seems like it should be possible to compile a whole video clip list. It would include a lot of Numb3rs scenes, of course (I especially like the episode that uses the art museum problem), but could also include the 2 boats clip in the Dark Knight for the prisoner's dilemma and I imagine other clips as well.<BR/><BR/>Also, Suresh, do you have any materials from these lectures to share so that we can borrow shamelessly from you? (: They sound great!sorellehttp://kdphd.blogspot.comnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-63372538214426890562008-12-25T19:31:00.000-07:002008-12-25T19:31:00.000-07:00I would agree on the "friends" comment. Nobody ca...I would agree on the "friends" comment. Nobody can remember leave it to beaver.Dennishttp://www.dennisblackmore.comnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-58684698952353172712008-12-23T06:37:00.000-07:002008-12-23T06:37:00.000-07:00I had never seen that solution to the millionaires...I had never seen that solution to the millionaires' problem before (though it is not Yao's solution...). On the same topic, you may want to check out the paper <A HREF="http://www.wisdom.weizmann.ac.il/~naor/PAPERS/comp_abs.html" REL="nofollow">"Comparing Information w/o Leaking It"</A> that discusses several other (simple) approaches to the problem.Jonathan Katzhttp://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-56680819491300728772008-12-21T18:42:00.000-07:002008-12-21T18:42:00.000-07:00You could also explain RSA. I did this with a grou...You could also explain RSA. I did this with a group of high-schoolers and it went over really well.<BR/><BR/>I used a phone-book for the analogy. To encode a letter, pick someone who's last name begins with that letter, and write down the phone number. One person gets a reverse-phone book to decode.<BR/><BR/>I then had them talk about the strengths and weaknesses of this approach (generating the reverse book takes too long) as a lead-in to the actual algorithm.Jeremy Hnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-65512484752375173242008-12-21T15:13:00.000-07:002008-12-21T15:13:00.000-07:00For an introductory talk on quantum computing you ...For an introductory talk on quantum computing you can play around with polarized light to get some of the ideas across. My typical set-up includes an overhead projector (increasingly hard to find), three sheets of polarizers, two beakers, and some high fructose corn syrup. <BR/>With the polarizers you can show the probabilistic and changing effects of measurements in different bases: 2 aligned sheets let light through, when rotating them the intensity decreases, until they are perpendicular and things turn black. Then, you can insert a 3rd sheet between the two and show how the 'measurement effect' of that one allows light to go through again. If you're really ambitious, you can also show how corn syrup can rotate the polarization of light, thus acting as a single qubit gate.Wim van Damhttp://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-75586194295456928072008-12-21T13:27:00.000-07:002008-12-21T13:27:00.000-07:00Kirk: cake cutting is an EXCELLENT suggestion. My ...Kirk: cake cutting is an EXCELLENT suggestion. My only worry with the friends video is that today's high schoolers probably have no clue what Friends was :)<BR/><BR/>Aaron: thanks for the tips on auctions. I'll definitely do something like this next year. <BR/><BR/>Anon: the blind buyer idea is a good one: I've used Coke/Pepsi tasting, which is a similar concept.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-46924591992904166972008-12-21T12:57:00.000-07:002008-12-21T12:57:00.000-07:00Another nice example of ZKP is one where a blind b...Another nice example of ZKP is one where a blind buyer is trying to buy two identical but different colored pieces from seller. <BR/><BR/>Seller tries to convince buyer that they are indeed different in color. In every round buyer takes the pieces behind and shuffles them with probability 1/2, then shows it to seller and asks if they are shuffled or not.<BR/><BR/>I found this in a writing of anup rao http://docs.google.com/View?docid=dq6zxpq_473cvj8ggfxAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-46042841858596620792008-12-21T10:00:00.000-07:002008-12-21T10:00:00.000-07:00An auction in class is a fun idea. I'm not sure wh...An auction in class is a fun idea. I'm not sure what sort of auction would help explain the <I>computational</I> aspects of game theory, but there's plenty you can do to illustrate the incentive aspects. A classic is to auction off a dollar bill to the class in several ways: as a first-price ascending auction, as a second-price one-shot auction, and finally (to make some money) as an all-pay auction.<BR/><BR/>In an ascending all-pay auction, everyone pays their bid, but only the highest bidder wins the dollar bill. The cute thing here it that bids will likely <I>exceed</I> 1 dollar, because at some point, people are already taking a loss, and would like to at least win the dollar to take a smaller loss.Aaronhttp://www.blogger.com/profile/09952936358739421126noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-15674326849037165822008-12-21T06:14:00.000-07:002008-12-21T06:14:00.000-07:00For high school students, I have done envy-free ca...For high school students, I have done envy-free cake division:<BR/>http://en.wikipedia.org/wiki/Cake_cutting<BR/><BR/>I explain cut-and-choose using the the classic scene from the old TV show Friends<BR/><BR/>http://www.youtube.com/watch?v=98KZNd03l4U<BR/><BR/>The cut and choose part starts about at 3:30 in.<BR/><BR/>Then I have 3 volunteer students run through the 3 person algorithm on a real multi-layer cake, asking them to explain why they are not envious as the cuts are made. Then while the students eat the cut up cake, I tell them that they can work on the 4 person algorithm as a hard homework problem, and tell them that I will give them their PhD for an n person algorithm with the number of operations bounded by some function of n. <BR/><BR/>Cheers,<BR/>Kirk PruhsAnonymousnoreply@blogger.com