Wednesday, June 9, 2010

America's Next Top Nerd

I want to make a computer science reality TV show. Like in most reality shows, the participants would compete to win a prize, but since they would be CS nerds, we won't aim for something as crazy as getting married to a famous person (maybe it can be something like becoming Facebook friends with a girl).

Anyways, instead of athletic or beauty competitions, I want the participants to compete by solving computer science problems. My question is this: what are some good CS problems for TV? I have some thoughts, but I'd also like to hear what others have to say. Ideally the problems would: (1) explain a cool CS concept, (2) be accessible to a PBS-type audience (i.e., no PCP proofs), and (3) have something that can be filmed.

44 comments:

  1. Would you be the host?

    ReplyDelete
  2. Yeah, and instead of "You're fired," I'll say "You've been garbage-collected."

    ReplyDelete
  3. Are PCP proofs kind of like PIN numbers and ATM machines?

    ReplyDelete
  4. http://en.wikipedia.org/wiki/PCP_theorem

    ReplyDelete
  5. Proofs of soundness and completeness in logic systems!

    Wait...no...not that.

    I think you might be able to make a good show out of some sort of competition between teams of CS people, a lot like the show Junkyard Wars (also known as Scrapheap Challenge). Specifically, some of the most concrete CS problems to non-CS people are things that robots do, like pathfinding and being able to trick people into solving problems for them.

    I think you could do a lot with posing problems in a "lab" and having them use the resources there (and in their heads) to solve it. Don't make the problems too abstract, or you lose some of your common denominator audience, but you could do several physical puzzle challenges (flipping pancakes comes to mind) and still have it be entertaining. The best part is, if you do take the PBS-approach, you can have asides that explain the concepts that they're using to solve the problem.

    Also, if you don't wear a labcoat like Beekman from Beekman's World, I'll cut you.

    <3

    ReplyDelete
  6. Problem: crashed hard disk. Photogenic solution: pop it in the freezer. You could even share a set with a cooking show.

    ReplyDelete
  7. I liked the darpa balloon challenge.

    ReplyDelete
  8. and wild card would be a memory leak
    :D

    ReplyDelete
  9. I just thought of another thing:
    ask around for the mental exercises that a lot of people know as "interview questions" and make them REAL.

    specifically, problems like this http://mathforum.org/wagon/fall00/p921.html and http://mathforum.org/wagon/fall09/p1125.html this come to mind. Remember, the strength of the TV show and the communication of ideas is about 90% visual.

    ReplyDelete
  10. I think the low-hanging fruit for TV-friendly computer science problems are going to be things that can be visualized easily and have some sort of progress to it. Things that come to my mind

    * shortest / optimal path (robots, office floors, mazes, factories)
    * cryptography (get thru doors and stuff)
    * clustering (not sure what could be cool about this but i'm sure there's something)
    * scheduling / automation (manufacturing)
    * stable matching (traditional marriage, rogue marriage)
    * sorting (pancakes! cards! )

    I liked the format of the 251 scavenge hunts, by the way.

    ReplyDelete
  11. play the stable marriage problem with real people (the students).

    ReplyDelete
  12. Machine vision tasks are good, like object recognition using the "available tools". The good thing about it is that you can show the audience a result they can understand and connect with.

    e.g.1 who can find Waldo in an image :)
    e.g.2 whose algorithm can detect the most number of flowers in an image, showing all intermediate results ...I think it would be fun!
    e.g.3 who can automatically find the best sentence that goes with an image!

    ReplyDelete
  13. too bad, the above comments. I say, the problem: design a robot to find the hottest chick around. this one has many interesting sub-problems too.

    ReplyDelete
  14. This comic comes to mind:
    http://www.smbc-comics.com/index.php?db=comics&id=1898

    ReplyDelete
  15. The Traveling Salesman Problem could be reframed as a quest to find various gifts for a nice girl (Princess?).

    The contestant with the best approximation algorithm wins.

    ReplyDelete
  16. How about a pair drawing game, where one person holds a pen and the other person instructs them to duplicate a line drawing. Competition would be based on accuracy of rendition, as determined by audience or computer or something.

    You can tweak this a bit by restricting the flow of information; not allowing the drawer to speak, not allowing the "programmer" to see the intermediate result, etc.

    ReplyDelete
  17. Or for team challenges, how about parallel sorting. Each person represents a number, and they have to sort themselves by age faster than the other team. Go team mergesort!

    ReplyDelete
  18. This is a great idea!

    I would love to see super geeky judges.

    Although I think the line for contestants would be significantly shorter than Idol; on the other hand everyone will think they are a computer genius.

    Rewards for top prize can be employment with Google or NSA or something.

    ReplyDelete
  19. it's a pity that so few computer science professors have the broad charm needed to be the host.

    ReplyDelete
  20. This comment has been removed by the author.

    ReplyDelete
  21. bar a certain masochist... :)

    ReplyDelete
  22. Many of these are great!

    Btw, if the reward is employment at a certain company (e.g., Google or Facebook), that company can sponsor the show.

    ReplyDelete
  23. as for public audience (not on pbs), nerds-got-talent might be a bit more entertaining...

    ReplyDelete
  24. There is this show: http://en.wikipedia.org/wiki/The_Code_Room But it seems pretty bad...

    ReplyDelete
  25. lol it should just be like...True Life: I'm majoring in cs at CMU. The prize is employment upon graduation, lol. You can show entertaining visuals of all nighters and bug fixing and drinking soda and arguing about video games. It'll be awesome. And by awesome I mean....haha idk. :/ I guess what I'm saying is you could have a legit show with real and challenging problems, but not make the problems the appeal of the show. It can be traditional reality tv!! Woohoo! :D

    ReplyDelete
  26. Being that I was your NOVA producer, I want in on this!

    ReplyDelete
  27. Luis: would it be very different from the ACM programming contests?

    ReplyDelete
  28. @jyby: the ACM programming contest has bad problems for this -- they're not made with TV in mind.

    ReplyDelete
  29. Speed solving towers of hanoi. It could be just like competitive cup stacking.

    ReplyDelete
  30. A couple of ideas...

    1. Build a cool visualization of social graphs (obvious opportunity Facebook sponsorship, something regular people might care about, and something obviously visual).

    2. Take something slow and make it fast. The sorting example could be a foundation here. But I'd put it in an application context, so that it's more relevant to a general audience. E.g., maybe a photo viewer dealing with a large number of images... The original version uses bubblesort, and the contestants make it better. Or maybe it does something simplistic w.r.t disk access. My goal with this wouldn't be to have the audience grok computational complexity. It would just be to get them to see that there are deep things in CS _that actually affect them_.

    Not sure that either of these fit within the timescale of a 30 minute TV show, though.

    ReplyDelete
  31. Please don't go beauty and the geek on this! I vote against dating / romance as the prize...

    ReplyDelete
  32. Ideally it would be good to find challenges that are socially relevant--we have to fight a lot of stereotypes that computer science is just writing code, when computer science is really about using computational thinking to make the world a better place.

    What I would love to see would be a really diverse set of contestants -- get out to the Grace Hopper and Richard Tapia conferences and recruit people from there.

    Then you're starting to show your audience not only why computer science matters but also how anyone can become a computer scientist.

    ReplyDelete
  33. "maybe it can be something like becoming Facebook friends with a girl"
    A girl?? really? Damn, I wish we had some of those in CS - it's a shame no one participating in your show could possibly be one. -_-

    wrt Show ideas:
    A puzzle hunt could be a good arc for a show: it has the time-press element, and lots of physical running around that's good for cinematography. It could involve a set of smaller problems so we could optimize for the best show-producing ones without upsetting the main 'plot' and have a diverse set of highly-visual and code-intense. I agree with the acting out 'interview questions' and I think a good coding montage could be great. Also writing some sort of graphics / UI code could be good for incorporating visual elements.

    The real problem you're going to run into is the vernacular. Any problem that's going to be interesting is going to cause a lot of screaming "it's DP!" "Floyd-Warshall/ Convex Hull / etc!" and the audience will have no idea what that means.
    I guess we involve a non-technical person in some active role on each team which might cause explaining but just as likely "okay, now go right. now left."

    On the other hand a lot of algorithms have great stories to go along (bunny rabbits, marriages, pancakes...) that could be visually interesting. If that were incorporated there would be a good excuse for the host to explain the algorithm to the audience.

    ReplyDelete
  34. someone should do a hybrid show between the american reality competitions and those funny japanese game shows, but with nerds and dorks who try to win some type of game or award in various kinds of embarrassing/humorous situations (à la "revenge of the nerds").

    ReplyDelete
  35. ^
    | it is funnier than a japanese game show to call yourself "dandelion" :D

    ReplyDelete
  36. Luis, can you write some scandalous new post? i'm bored, so are most people here..

    ReplyDelete
  37. The problem here is how will you explain any of the solutions to the general public who may not have a mathematics/engineering background(unless the solution is trivial).
    Such a show will only work when there is sufficient awareness of the act being performed in the general population and when they can themselves attempt/try the act even if they fail. The act should be well known and understood. Only thing that the participants should bring in this format is the delivery/execution which an average guy at home can not achieve.
    In that sense maybe UI design is an option, or any of the known solved problems with only execution as a criteria in stipulated time.
    Hacking a known real organization could be an option, but that would be a different format for the show.

    ReplyDelete
  38. Luis - I got you beat by a long shot here!

    http://matt-welsh.blogspot.com/2009/03/top-prof.html

    ReplyDelete
  39. this is the kind of TV "programming" I would watch! great ideas, discussion.

    ReplyDelete
  40. Great! Do it! I like several of the ideas mentioned here (e.g. visualizations, ...). What about taking also some inspirations from shows that have use 'algorithms' as an ingredient, like numb3rs? Build up a fake scenario, deliver new information over the progress of some days (hours?), have several possible 'solutions' at the core of the scenario. Additionally, force the participants to work sometimes on problems in groups of 3 or 4, or build teams after the initial one-person qualifying rounds.

    ReplyDelete
  41. Advertising giant GoGoo wishes to deliver premium web content to the people of Inecha! But the Inecha government takes exception to this and wishes to shut them down.

    Each turn: GoGoo employees select from a number of underground servers, with set carrying capacities proportional to their cost. Inecha officials get to chose which server to shut down, with a cost proportional to the carrying capacity of the pipes.

    Somehow then, the concept of maximum flow = minimum cut is aptly demonstrated.

    ReplyDelete
  42. The post which you have did that is amazing and also the knowledge you have shared here it helps me to increasing mine.Thanks for the informative blog.

    ReplyDelete
  43. Great! It is cool to see this. I learned something new

    ReplyDelete