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...

Math != calculation, part 537...

From the NYT, on scoring the i-can't-believe-it's-not-a-sport sport of gymnastics:

The new system is heavy on math and employs two sets of judges, an A panel and a B panel, to do the computations. Two A-panel judges determine the difficulty and technical content of each routine. Six B-panel judges score routines for execution, artistry, composition and technique.

The A-panel judges’ scorecards start at zero, and points are added to give credit for requirements, individual skills and skills performed in succession.

The A panel counts only the gymnast’s 10 most difficult skills, which are ranked from easiest to most difficult (from A to G for women and from A to F for men). An A-level skill, like a back handspring in the floor exercise, is worth one-tenth of a point. The value increases by one-tenth of a point for each subsequent level, meaning a B-level skill is worth two-tenths and an F-level is worth six-tenths.

Required elements add a maximum of 2.5 points to the score. Extra points, either one-tenth or two-tenths, are given for stringing skills together.

Each judge adds the marks, then the two reach a consensus. Elite gymnasts usually have a difficulty score in the 6’s; the toughest routines generally have difficulty scores in the high 6’s or 7’s.

[...]
The system rewards difficulty. But the mistakes are also more costly.

Which is where the judges on the B panel come in. They rate the execution, artistry and technique of a routine, starting at a score of 10.0 and deducting for errors.

This score, called an execution score, is where the perfect 10.0 still exists. But reaching it is unlikely.

A slightly bent knee can be a deduction of one-tenth of a point. A more drastically bent knee can cost three-tenths. In this system, the deductions jump from one-tenth to three-tenths to five-tenths. A fall costs a gymnast eight-tenths. In the old system, a fall was a five-tenths deduction.

The highest and the lowest of the judges’ scores are thrown out. The remaining four scores are averaged to obtain the final B-panel score.

On the scoreboard, the final score appears in big numbers, just above the gymnast’s marks for difficulty and execution.

Apart from my grumble about the level of 'math', it's an interesting way of doing the scoring.

I wonder if this could work for conferences: replace 'degree of difficulty' by 'hardness of problem, general hotness of the area, etc', and then you could deduct points for things like

• More than two digits after the decimal point in the approximation ratio
• exponent of running time requires the \frac environment
• More than two parameters in the running time
• Gratuitous use of O() notation to hide dependencies you don't like (yes I'm talking to you, high dimensional clustering folk)
• Requiring your winged pigs to be large in dimension, have extra glitter on the wing tips, and carry golden harps in order to make the horses take off (Hi there, complexity denizens)

The concept of an approximation

We're always searching for new ways to communicate cool ideas in theoryCS to the outside world, and the list gets more and more esoteric each time one thinks about it. But in my interactions with people, people generally unfamiliar with algorithm, and theoretical computer science in general, I'm constantly amazed at how counter-intuitive the very notion of an approximation appears to be.

A typical conversation goes something like this:

Person: Oh this problem is NP-hard so we ran this heuristic
Me: Have you tried approximating it ?
P: What do you mean ? Our heuristic seems to be reasonable.
M: I mean an algorithm that guarantees that it'll get close to optimal.
P: But how can you know that ? It's hard to find the optimal solution, global minimum, yadda yadda yadda...
M: We can often prove an answer is close to OPT without knowing OPT itself.
P: [total silence]

This kind of thing happens often in research conversations, as well as in the classroom (where it's less surprising I guess). In fact, one person was so amazed at the idea that even proving an approximation could be NP-hard that we spent a good semester plowing through the PCP theorem (at least parts of it).

I'm not dissing heuristics: it's often the case that either the approximation guarantees one can show are too weak, or that the claimed bounds don't match the empirical performance. But I do think it's important to at least ask the question of whether provable approximations exist, much in the way people in CS are now reasonable comfortable checking (or asking the resident theoretician !) if a problem is NP-hard.

But you can't ask till you know. This is one of the main reasons I teach a smattering of approximations in my graduate algorithms class (and why I teach some randomization as well). The concept of an approximation (especially when you can't find the actual answer) is a surprisingly slippery conceptual leap, and requires mental agility that goes beyond the standard "algorithms toolkit" that focuses on issues of performance.

The Katayanagi Prize

Via the Baconmeister (er.. the Quantum Pontiff), we hear that Christos Papadimitriou and Erik Demaine have received the Katayanagi Prize. Christos gets it for "research excellence":

The Katyanagi Prize for Research Excellence will be awarded annually to an established researcher with a record of outstanding, and sustained achievement.

and Erik gets it for "emerging research leadership":

The Katyanagi Emerging Leadership Prize will be awarded annually to an individual recognized as an emerging research leader.

Congratulations to both of them, (and do read the Dr. Dobbs interview with Christos, where he shows that he knows what "Guitar Hero" is :))

Edge people...

Bill Gasarch has an interesting post up comparing attendance numbers at SoCG and CCC. He introduces the interesting notion of 'edge people': people in related areas who wouldn't normally attend the conference, but would because of locality.

This of course makes me a little worried about 2010. We have a rather large 'edge' community at the U. of Utah itself within SCI. But Utah as such is fairly geographically isolated (and indeed, there's a general belief that our department suffers a little in perception as a consequence), so we don't get the 'edge' crowd that places like NYC and Maryland potentially get.

I say 'potentially': as always, it's probably possible to get data on this. Specifically, if one had access to historical attendance lists (not numbers) for SoCG, one could first identify candidate 'edge' people (either by subjective eyeballing, or even more numerically as people who only show up "rarely" and publish "rarely"), and then figure if there's a correlation between location and presence of an edge crowd.

Similarly, one might even do this for CCC vs SoCG although as one commenter points out, the larger number of total unique authors on SoCG papers might be sufficient to explain the discrepancy in attendance (Paul Beame's argument about competing conferences is also valid: I couldn't imagine going to FOCS, STOC, SODA and SoCG every single year, in addition to the various DB/data mining conferences I attend).

Women in Computing workshop, and a new blogger

Sorelle Friedler, UMD grad student in geometry, tireless staff volunteer at SoCG 2008, and former AT&T summer visitor, has a new blog. One of the first things she writes about is the Women in Theory workshop at Princeton that ran Jun 14-18. Add the feed, folks !

Money Money Money

(ed: three NSF posts in a row ? maybe you're a little obsessed with funding ?

As CRA and USACM are now reporting, the president just signed a bill that among other things allocates 62.7M in supplemental funding for the NSF. However,...

Funding for the National Science Foundation is split 70/30 between education and research programs at the Foundation with $40 million going toward the Robert Noyce Teacher Scholarship Program, which “seeks to encourage talented science, technology, engineering, and mathematics majors and professionals to become K-12 mathematics and science teachers

Which means that only 22.7M is left to be divvied up among the many directorates. Optimistically, that's roughly 44 new proposals, over ALL of NSF. Hmmm....