More experiments in algo-teaching

(ed. note: think of this as a 'theory'-chaser to take the bad taste of cricket-blogging out of your mouth)

Another experiment that I continued this time was a set of lectures on "fun topics". The idea is to convey some ideas about a fun topic in theoryCS without too much jargon, but with enough meat to indicate that there's something deeper going on beneath the fun stuff.

I run these lectures at the end of the semester (when everyone's worn out already :)), and throw them open to the general public: both times I did this, I got substantial attendance from people not in my class, and at least in one case, someone who attended the lecture last year actually decided to take my class this year.

Not all topics are amenable to such a treatment, but my hope is to build up a suite of such lectures: the nice thing is that they can then be reused for other venues: for example, I've given variants of these talks to freshmen and high school students, and will do an undergraduate colloquium in the math department next semester.

For all of these lectures, I've pilfered shamelessly from the original works, as well as great websites developed by the authors. This post can be viewed as a shout-out and a thank you.

1. Pancake flipping:
Brian Hayes wrote a great article on pancake flipping for the American Scientist. In it, he links it to the problem of genomic rearrangement, and in doing so, ends up with a beautiful tale of the interaction between theoretical problems and practical constraints, all told in context of a topic that everyone can relate to.

I made two-color pancakes in different sizes, and distributed them to the students at the start of class: I briefly described the problem, and let them go at it. It was quite entertaining, and put the more formal discussion later on in context.

2. Zero knowledge proofs
ZK proofs are great for this kind of setting: they are completely counter-intuitive, (and so have the 'bizarre' factor), and are easily explained using popular metaphors. I used Moni Naor's Sudoku demo page, as well as the version of the proof that involves slicing and dicing the puzzle. This was done with class participation (I was the prover, and there were multiple verifiers).

The second demo I ran was the Yao protocol for the Millionaire's problem (how do two millionaires determine which is richer, without either knowing the worth of the other). Again, I did this interactively with class volunteers and an RSA applet to speed things along. More details here.

3. Quantum Computing
No demos for this one, but I gave a crude high level view of what quantum computing is about (about one-step up from the "do everything in parallel" explanation). The main goal here was to convey the basic ideas of what a qubit is, what a quantum circuit looks like, and how the Bell inequalities show that quantum computing is much more bizarre than classical randomness. Here, Dave Bacon/Umesh Vazirani lecture notes proved indispensable, coupled with the Nielsen-Chuang book, and a recent blog post by Michael Nielsen.

4. Computational Origami
I haven't quite worked the kinks out of this one, but the basic idea is to demonstrate the principles behind computational origami (and where the 'computation' comes in) by looking at the question: What shapes can you make by folding, followed by a single cut.

There's a cool backstory to this: essentially the first example of such an algorithm was how Betsy Ross designed the 5 point star for the American Flag, and it lends itself to a nice demo in class.

Secondly, it's a classic example of resource-bounded computation: limiting yourself to one cut. Thus, it makes for a good illustration of how computation appears in all kinds of problems.

Thirdly, computational origami actually shows up in many real-world problems, most notable one involving folding mirrors for a telescope to be launched into space. If we're trying to convey a sense of computational thinking, this is a great example.

The actual problem itself was solved in this paper by Demaine, Demaine and Lubiw. Unfortunately, I have yet to find a way of explaining it that will make sense to non-expert geometers, and that's one weakness with this particular story: Erik's page has some nice examples to demo, but it's hard to convey the deeper algorithmics behind the problem.

Lessons learned:

• As always, know your audience. What works for a graduate class doesn't work for sophomores, and certainly doesn't work for eigth-graders :)
• Interactivity is key: if you allow people to participate, they're more involved, and will probably take away something positive
• Keep it light: resist the urge to get too mathematical. There are many beautiful topics in theoryCS that can be explained without jargon, and many others for which with some effort, jargon can be removed.
  
• A 'bizarro' factor helps: In general lectures that I've given, I find that presenting something completely counter to people's expectations catches their attention immediately, and leaves a lasting impression. ZK proofs have that property. Bell's inequality sort of does, but the impact would be more immediate if I could actually run a quantum experiment to demonstrate violation of Bell's inequality ;)
• Relate it to the real world: again, it's not enough to cite applications: one should try to show them as far as possible. In this regard, the Betsy Ross story is great, because it relates to something everyone (in this country) knows.
  

My goal is to add one or two such lectures to my arsenal each time I teach the class. For next time, I'm seriously considering running a live auction of some kind to demonstrate some concept in algorithmic game theory (suggestions on how best to do this are always welcome). Are there other such topics that might lend themselves to an entertaining, edifiying and educational experience ?

On run-chases

(ed. note: this is about cricket, not algorithms, or geometry, or computer science. you have been warned)

South Africa, the Netherlands of cricket, finally won a big game, beating Australia in Perth after a historic run-chase of 414. This of course follows India's famous run-chase, beating England in Chennai by chasing down 387. As Cricinfo points out, 9 of the top 25 run chases have come in the last 8 years (in a tally that dates back to 1902).

There's a detailed statistical analysis of these chases, but no speculation as to why they're becoming more frequent. The answer seems obvious to me though: the increasing scores in one-day cricket. A quick search of Statsguru indicates that of the 258 overall scores above 300 (first or second team) one 1-day games, 179 of these happened after 2000. Even to a casual observer, it's clear that the scores in 1-day games have gone up (and don't get me started on Powerplays).

Frankly, when all this fuss was being made about India's run chase, I couldn't quite understand why, because if you think of this as a one-day game, it's not too hard (and in fact India's coaches thought the same way!).

All in all, two exciting Test matches (and how often have we been able to say that)

Videotaping talks

Videolectures.net is a company that has taken on the job of videotaping and packaging conference talks. They're based out of Slovenia, and offer a good service: they take your talk and your slides, and sync up the talk video and slides so someone watching later on can follow along.

For examples, you can see my talk at ETVC, and here are the other talks. I first heard about this company when I was googling a paper and discovered that the ICML talk was online.

I originally thought that they only handle events in Europe, but they appear to have covered this year's KDD as well (although the coverage appears strangely limited).

Practical applications of 1-medians

From Optimal Home Location:

Have you been looking across many different neighborhoods for a place to buy or rent? Have you been contemplating whether to buy closer to your job, your spouse's job or your kids' school? Do not worry - this is not a simple geometric triangulation but a centuries old mathematical problem. Optimal Home Location tool is synthesizing math algorithms and Google Maps together in order to pinpoint optimal home location for any commute scenario. It is easy to use and fun to play with. All you need to do it [sic] enter all the addresses your family routinely visits throughout the day and then click on the map icons to define commute route for each member of your family. The tool automatically computes optimal home location that will minimize total combined commute for all members of your family

NSF bleg

This appears in the supplemental documents section of the upcoming CISE call:

In the Supplementary Documents Section, include a list of all PIs, Co-PIs, Senior Personnel, paid Consultants, Collaborators and Postdocs to be involved in the project. This list should be numbered and include (in this order) Full name, Organization(s), and Role in the project, with each item separated by a semi-colon. Each person listed should start a new numbered line.

Does anyone know what a "Collaborator" is ? is it merely your other-institution co-PI on a collaborative proposal ?

I had a number of responses to people from my programming project post: I thought I'd post the responses here, rather than in comment fields.

* On rolling your own: I'm intrigued by the many suggestions to use Sphere Online. I've heard of topcoder and Project Euler before, and decided not to use topcoder for ease of pedagogy (I wanted problems where the key algorithmic idea was "preidentified", so I could give a DP problem in the homework on dynamic programming). I was also not convinced that topcoder focused on the algorithmic aspects of the problem as opposed to raw speed: the fact that it was set up as a time limited competition by default was also a pain in the neck.

* On copying: this is an unsolvable problem IMO. Since I was choosing problems from the pre-canned list at the ACM server, I was at the mercy of the online solution providers. Judging by the results, my students are either very honest, or don't know how to find these sites :). I've spied on the related forums, and they tend to be somewhat militaristic about not letting people post code directly, although hints are always supplied. As an aside, for theory problems this is a royal pain: I've had to mask things in various ways to prevent a google search, and I have my own way of creating problems that I'm happy to reveal to someone who asks me directly :).

* on what to do for geometry: the problem is not the lack of a good code base. In fact it's the reverse problem. CGAL for example has many quality solutions already pre-coded, so I can't even ask students to use CGAL as a base framework. Given the limited time I have before semester starts, its debatable how much coding and test generation I can do on my own, so stay tuned...

I am less than smart :)

I posted my note on programming assignments, and then wondered why there were no comments. It turns out that I forgot to monitor my moderation list, and when I checked, there were tons of comments ! apologies to all the commenters: your comments are available now, and I'll start replying shortly.

programming assignments

Inspired in part by Michael Mitzenmacher's exhortation:

Here's my claim: theory does untold damage to itself every year by not having programming assignments in the introductory classes on algorithms and data structures.

I tried an experiment in my algorithms class this year. Using the ACM programming competition online judge as an evaluation tool, I assigned one programming assignment in each of the first three assignments in my class (later assignments went into approximations and randomization, which the site didn't really cater to). Coupled with this, I used the ACM Programming challenges book by Skiena and Revilla to guide my choice (they break the problems down nicely by dominant technique).

The way the system works is this: you're given a problem definition and an input/output specification. You write your code in one of three languages, using a specific compiler flag sequence, and then upload your code. The system runs your code through a battery of tests, and then reports whether you had

• compile-time errors
• failure to terminate in the prespecified time limit
• incorrect answers
• run-time errors
• all correct answers
  

What worked:

• Students actually liked the idea of programming assignments: I received numerous variations of the comment, "I didn't understand the algorithm, but once I coded it...". They were less enthused by the server, but more on that later.
• People started getting quite competitive: the site maintains stats on the best implementation thus far, and even after students satisfied the requirements of the assignment, by matching the desired time limit, they tried to optimize their code further.
• The questions are well-designed, and usually need algorithmic tricks rather than hacks. For example, one question is to compute the closest pair, and any optimized brute force algorithm will fail, but the standard deterministic divide and conquer will work fine.
  

What didn't:

• The server would occasionally flake, especially a few hours before assignment deadline time :)
• I/O specifications were often tricky: the problem specifications would leave out details about what one could assume about the input, so simple things like "don't assume that when a range [x,y] is given in the input, that x <=y" needed to be discovered.
• The error messages are cryptic to a fault. Compile time errors are linked to the point in the code where this happens, but for any other kind of error, you are merely told that an error occurred. This caused major frustration.
• With Java especially, getting a correct implementation within the time bound seemed harder than with C/C++. Since Java is often the first language students learn, this is annoying, especially since the whole point of such exercises is to abstract away as far as possible the particular idiosyncracies of a language.
• From a grading point of view, it's very painful to evaluate each person's submission. There's no easy way except to do it manually.
  

Overall, my experience was mixed-to-slightly-positive: I'll probably do this again, but I might also include examples where I design the test inputs and do local evaluation. For some problems (like with randomization) I might have to design the problem from scratch.

Now what I'd like is something similar for my computational geometry class :)

While in Paris...

My latest reason for being off the air has to do with the amazingly bad internet capabilities of Paris hotels. Yes, I'm in Paris, city of lovers, but certainly not of lovers of wifi. There are at least 30 networks visibile wherever you go, but they're all secure, so no mooching. The hotel-provided wifi is actually a generic service that costs 22 E/day for connectivity, with all kinds of bandwidth caps and a very slow connection. If I were to splurge for the "business" level, I get the luxury of paying 27 E/day, with unclear benefits (presumably I can now download my bootleg bittorrents (just kidding)).

Other things I've noticed since I last came to Paris: (which is not to say that they are new, just that I just noticed them):

• Every second store on the podunk street my hotel is on is a fancy clothing store. Clearly the world-wide economic collapse has not hit.
• Speaking of world-wide economic collapses, it really hurts to have a weak dollar. $7 espressos, sigh...
• ....but it's always a pleasure to walk into a cafe and order a 'cafe' and just know that something good will appear. This is in contrast to the unbounded depth circuit needed to specify a proper cup of coffee at Starbucks.
• Speaking of Starbucks, how on earth can they even survive in Paris ? I mean, you go to a Starbucks here, and you get the same experience as in the US, ending with a paper cup of coffee of questionable quality that you drink perched on a high bar stool. On the other hand, you go to a cafe, and they serve you with nice cups, and a little cookie, and let you sit there for hours nursing your coffee, and will even give you the WEP key for their secured WiFi. It's no contest !
• You can change the world while nursing your coffee. I was staying in the 14th Arrondissement (the Montparnasse area) and had to have a coffee at the Dome cafe, a place apparently frequented by Lenin and Trotsky before the Revolution. I have to say that at the time I went, the clientele looked like they were plotting a revolution... in 1907.... I'd link to a verification of this, but I can't make any sense out of the search results on google.fr
• Speaking of which, how does one tell google NOT to return results in french ? every time I edit the URL to go to google.com, it sends me back to google.fr. Suivant !!!

And why am I blogging from Paris, you might ask ? Well here's why. I'm an invited speaker, no less. Conference blogging was limited because there was no wifi at the conference site either. It's a long story involving military schools (and maybe even NASA). Details will appear shortly.

Coffee..

On the evolution of coffee drinking, by Malcolm Gladwell (he of The Tipping Point and Blink). I particularly like this line about Trotsky:

Give a man enough coffee and he's capable of anything.

Items...

I've noticed an inverse correlation between blogging frequency and "actual work", so boy must I have been working hard !!

Two items of note, as my blog and I pass in the night:

• Michael Nielsen links to a great way of advertising a speaker: use Wordle on their work (delicious feeds/research papers)
  
• ICML 2009 is going to a reviewing model where you can specify which area chairs you want your papers directed to (area chairs and interest areas will be listed). John Langford, one of the area chairs, goes further with what is essentially a personalized reviewer manifesto. An excellent idea ! He lays out his principles, and authors are fore-warned.
  

STOC abstracts due today !

According to Michael M, there are 150 and counting already. Papers are due next week. And here's where you do it !

SODA 2009 South Pacific Event

A note from Howard Karloff (please email him for more information):

To SODA '09 attendees:

I have reserved, for SODA attendees and their friends/spouses/significant others, 50 tickets in the loge section at Lincoln Center for the 7:00 PM, Tuesday, Jan. 6 show of "South Pacific," so popular a show that already both Saturday Jan. 3 performances are sold out. If you want to buy one or two tickets, send mail to howard@research.att.com with "South Pacific" as the subject field, specifying the number of tickets you want in the body of the e-mail. Tickets will go to the first SODA attendees who pay by credit card via PayPal. I'll send instructions by e-mail. The tickets are $120 each--the face value is $115, and the extra $5 is to cover the PayPal fee--and are NONREFUNDABLE: once you pay, there will be no refunds. However, I imagine someone at SODA, some random theatregoer, or an ebay user would be thrilled to take tickets to such a popular show off your hands.

So, please, start those e-mails coming. Should the demand far exceed 50 tickets, I may arrange a second outing, to a different play, either Saturday or Tuesday. A few reminders:

"South Pacific" starts at 7PM, not the typical 8PM start
time, on the last day of SODA.

The venue is Lincoln Center, not in the heart of Broadway.

Once you pay, there's no backing out.

See you in New York in a couple months!

Howard Karloff

Announcements

• Sanjeev Khanna reminds us that FOCS early registration deadline is Oct 3, 2008. Get your cheesesteak on !
• CFP for the 2009 sausage convention (with beer!!): Deadline is Nov 24 (abstracts), Dec 1 (papers)

About that whole political outreach business

that I was talking about in this post, here's what I find in my RSS reader today:

The names of seven distinguished scientists nominated by the President to serve on the National Science Board (NSB) were sent to the Senate for confirmation on September 16, 2008. Drawn from industry and universities, and representing a variety of science and engineering disciplines and geographic areas, these four new and three incumbent NSB members were selected for their preeminence in research, education or public service. When confirmed by the Senate, they will serve six-year terms to expire in May of 2014.
...

Diane L. Souvaine, of Massachusetts

Diane Souvaine is a computational geometer, who is professor and department chair of computer science at Tufts University, and holds a secondary appointment in the department of mathematics. Her current research focuses on the design and complexity analysis of geometry algorithms to solve problems from a variety of venues, ranging from computational statistics to geometric modeling to self-assembly of nano-structures. She also directs summer week-long institutes involving computational thinking for middle school mathematics teachers, funded by the Massachusetts Board of Higher Education. From 1992 to mid-1994, she served first as acting associate director and then as acting director of the NSF's Science and Technology Center on Discrete Mathematics and Theoretical Computer Science (DIMACS), while she was associate professor of computer science at Rutgers University. She has been a Fellow at the Radcliffe Institute for Advanced Study, and a member of the School of Mathematics at the Institute for Advanced Study in Princeton, NJ

Very cool indeed...

Loading Image

Click anywhere to cancel

Image is Unavailable

CS advocacy in the political realm

Two articles caught my eye recently:

• A posting on the CCC blog about why computer scientists should publish in magazines like Science, Nature and PNAS
• A Wired Science blog entry about Barack Obama's science advisors (John McCain has not revealed his list of science advisors)

In the first article, Peter Lee makes the argument (with an assist from Peter Harsha) that there are good political reasons for CS folks to publish in Science, Nature and the like (even if many of us snigger at the kinds of CS research that ends up there: I know I have horror stories about articles that are accepted over the objections of the specialist CS reviewers). One argument is that of influence: whether we like it or not, CACM is not the preferred reading material for Congressional aides and staffers that have the ears of elected representatives, but Science/Nature are on the radar. Moreover, these publications have well-honed PR engines to get articles out to reporters: often embarassingly overhyped, but hey, you know what they say about publicity :).

Which brings me to the second article on Barack Obama's science advisors. What's interesting is that 4 of 5 of them are from the life sciences. This is not to demean the importance of life sciences in the current policy environment (GMO crops, stem cells and biofuels are all on the political radar), but there are a good number of technical hot-button issues as well (voting machines, copyright issues, electronic eavesdropping, privacy), and it definitely wouldn't hurt to have a CS-oriented person near the "ear of the man", so to speak, to articulate a view of the importance of these issues and how the research community is dealing with them.

I'm a lowly untenured professor, who used to be a lowly lab researcher, so I have no good ideas on getting personally involved in such matters. But I can see (partially thanks to CCC and the SIGACT Theory group) how advocacy can, over time, lead to fundamental changes in the landscape of support for our efforts, so at the very least, I can consider the idea of disseminating my work (when appropriate) beyond our "incremental" conferences and exhort others to do the same.

SODA list is out

Some happy, some not so happy :)

Kudos to Claire Mathieu and the PC for not only including the list of papers, but also the list of abstracts !! Finally !!

As a public service, here's a TeX-formatted PDF of the list of abstracts, for those who find serif font easier to read than a stream of text on a web page. Warning, it's 44 pages long, and will have formatting errors. I wrote a perl script for the overall parsing and did lots of local fixing by hand for math-mode stuff, but it's not perfect.

Fonts !

John Holbo at CT does a not-review of books on fonts (or faces ? I'm confused now). In any case, this is clearly a book I need to get.

The tensor product trick

Blogging has been slow this summer as I (surprise surprise) was actually working. Today the semester starts, so I expect to be blogging more as I attempt to clear my head from the detritus of semester minutiae.

Terry Tao has a new post up in the "tricks wiki" started by Timothy Gowers. The "trick" can be summarized concisely as: if you want to prove an inequality of the form X < Y, but can only prove X < CY, then take "tensor powers" of the objects X and Y and prove the weaker inequality, and then take a "root".

What's interesting to me is that this is none other than a generalization of the "standard" amplification trick that is most commonly used in hardness results. The easiest application is the proof that CLIQUE admits no absolute approximation: if it did, take graph powers, find the additive-error number, and take square roots, and you have an exact solution (since the value must be integral). Generalizations exist: you can use the same argument to show that CLIQUE admits no constant factor approximation, and even more intricately (invoking the PCP theorem) that independent set has no polynomial-factor approximation.

It makes me wonder what other "standard" analysis tricks draw their lineage from generalizations in the world of "real math". For example, tricks involving building exponentially growing covers tend to show up frequently in topology and analysis.

$10 million for complexity theory...

Via His Quantum Holiness, news comes of the NSF Expeditions awards: each award is $10 million, and four were given out. One of them was for complexity theory, and the team is a star-studded list of complexity and algorithms folks, led by Sanjeev Arora. Here's the blurb:

In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics

Congratulations ! For getting the award, and demonstrating that hard-core complexity theory CAN get funded...

Update: Sanjeev Arora comments...