Monday, April 23, 2012







Sunday, April 22, 2012

Podcast assignments

I went to a talk on Friday advocating the use of podcasts or webcasts instead of written assignments. Instead of a written algorithm and proof, the student could turn in a Khan academy style proof, at most 2 minutes long.

I think of the number of times that a student has come to my office to question his or her grade. I would ask them: "Can you read to me what you wrote? Just read it aloud to me." They would start reading, then stop and say: "Well, I didn't write xxx, but of course that was what I had in mind". They would continue, then stop in some embarrassment at the lameness of their style. The lack of precision in their writing would be painfully obvious, and sometimes they couldn't help but laugh at themselves. I wouldn't need to explain why they didn't get full credit: once they read aloud, the reasons became obvious.

A webcast might be the answer!

Friday, April 20, 2012

The process of discovery

The other day I taught a reduction from 3SAT to Independent Set, and I learnt a lot from the lecture. I asked the students who had not seen reductions before to come up with it themselves, but I actually had no idea how they could go about it. My question was more like an act of faith than like a lecture plan. I thought to myself as I asked them to find the reduction: "What do I say next if no one has any suggestion? I have no idea." When, as a student, I learned that reduction, it was given to me as if by fiat, and I did not understand how one could come up with such a reduction with no knowledge of gadgets and without having seen any non-trivial reduction before.

But I was wrong to worry. I was delighted to hear many ideas spring up from the room, was careful, to save time, to prune the suggestions that I knew would lead to a dead end, and was very impressed that my class, with no prior experience and in a truly collaborative effort, was able to create all the pieces that combine to make the reduction. I hope that, like me, the students who had seen the reduction before (and who were primarily bystanders in that part of lecture) learned from watching their peers at work.

The first observation that started the discussion was that each variable in a 3SAT assignment is either true or false, with exactly two possibilities, and each vertex in a graph is either in the independent set or not, so, "by analogy", one could try to create one vertex per literal, and, for each variable x, connect the vertex "x is true" to the vertex "x is false" by an edge. The student who suggested that told me that he had never seen it before. It was not reconstructed but created ab nihilho. Impressive! I am singling out that comment because it was the first one and broke the ice, but there were several other equally insightful and creative suggestions from all different students.

The process of discovery is fascinating to watch.

Thursday, April 19, 2012

Walking out of class

Students sometimes walk out of the room during my lectures.

I know that it is considered not polite. Once in the room they should suffer through the lecture until the end, advocate proponents of good manners. But why? If they are bored, if they know the material already, if they are hopelessly lost, if they are suddenly taken by a bout of sleepiness, or if, for whatever reason, they are not getting anything out of attending class, why should they stick around?

In the room where I teach, it is easy for people near the side alley to leave discreetly without, I think, distracting anyone. I see out of the corner of my eye the figure of someone leaving, but it does not interrupt the lecture in any way. Of course I hope that students are benefiting from lectures, but if not, isn't it slightly hypocritical for them to stay?

I pretend to teach, they pretend to learn, and it becomes a charade.

Wednesday, April 18, 2012

The destiny of the professor's wife

Daniil Kharms wrote a story about a professor's wife. Here is the beginning.

Once a professor had something to eat, and you could not say a little something, and he began to feel sick. His wife approached him and said: "What's wrong with you?" And the professor said: "Nothing." The wife went back to the kitchen.

The professor lay down on a divan, stayed there for a while, got some rest, and went to work.

And there, a surprise awaited him: They had cut down his salary, instead of 650 rubles now he made only 500. The professor tried everything, but nothing would help. He went to the director, but the director wanted to strangle him. He went to the bookkeeper, and the bookkeeper said: "You should go see the director." The professor got on a train and went to Moscow.

On the train the professor caught the flu. When he got to Moscow, he was so sick he could not get off the train.

He was put on a stretcher and taken to a hospital.

He stayed there no longer than four days and died.

The professor was cremated, and his ashes were put in a little jar and sent off to his wife.

So here is the professor's wife, sitting and drinking coffee. Suddenly the doorbell rings. What's going on? "You got a parcel." The wife is very happy, she is smiling, tipping the mailman with 5 rubles, and quickly opens the parcel.

She looks, and inside the parcel are a little jar with the ashes and a note: "This is all that is left of your husband."

Tuesday, April 17, 2012


Today I was teaching reductions. I found a relevant quote on wikipedia:

Q: How do you shoot a blue elephant?
A: With a blue elephant gun.
Q: How do you shoot a yellow elephant?
A: Have you ever seen a yellow elephant?
Q: How do you shoot a red elephant?
Q: How do you shoot a purple elephant?

Sunday, April 1, 2012

Spring school heaven

This past week, during Brown's Spring break, I gave a couple of lectures at a Spring school in France on theoretical computer science.

It took place on an island off the Atlantic coast, in a campground about a mile from lovely beaches of fine sand. There were slightly more than 40 students, postdocs, and researchers there to learn from the lectures, and a half-dozen lecturers, a ratio of about 7 to 1. The weather was amazing, with bright sun and exceptionally high temperatures every day, and so, instead of observing the usual lecture format, the school improvised ad hoc Socrates-like discussions: every morning we split into small groups, with one instructor per group, got on our bikes and headed to the beach. On the beach, we formed small circles and had learned conversations about algorithms, graphs, and randomness. But how can one teach without a screen, one might ask? The answer has been known since Antiquity at least: wet sand and a stick are the perfect writing medium. I only got into trouble once on the first day, when, half way through the analysis of the Goemans-Williamson maxcut algorithm, a wave came in and erased my calculation, as well as accidentally getting me wet all the way to my knees. Instead of erasing the board when we needed more writing space, we simply walked along the shore to find the next fresh spot of unwritten wet sand. At lunch time, the staff from the compound brought us picnic lunches and some wine (two bottles for every 6 people, usually one of local wine from the island, and the other one from the Bordeaux region). After going through the presentation of an exciting result, we cooled off by running in and out of the water (everyone had brought a swimming suit, of course). In the early afternoon, we took a leisurely walk back to our bungalows, walking our bikes and discussing exercises and puzzles as we went, then took a pleasant nap (or tried to use the flaky internet connection) before heading back to the beach for the late afternoon work session and evening swim. On the last day, we switched roles: the students became the instructors, the instructors became the students, and we got acquainted with the tricks of riding bicycles in the sand, juggling torches of fire (if you get petrol on your clothes, dive into the sand and other will quickly cover you with sand to extinguish the flames), getting into cold water without effort, body-surfing the waves, and biking in the woods by night without a light. At one point Ronald de Wolf commented: "We look like a bunch of hippies!", but I could not tell whether his tone was one of approval or of disapproval.

I taught a bit of optimization, and we practiced steepest descent by rolling down the sand dunes. Someone else presented an analysis of the dynamics of the famous sandpile model, and we had a lab session testing the fit of the model with reality (it's a poor fit). But the main theme of the week was randomness and probability in algorithms, and we used waves as our random coin flips, checking how long it took to get wet as a practical instance of geometric distributions. We studied random walks by biking into the confusing salt marshes area, where an unhappy landowner once threatened to keep me as a hostage for intruding on private property. We learned the similarity between having a creative idea and seeing a shooting star: both require much patience, skill in knowing where to look, and a little bit of luck. In both cases, two persons can both be star gazing at the exact same time with the same dedication, and one will see the shooting star but the other one won't. We tested our students' ability to greet new ideas with an open mind, by giving them oysters for dinner. We suffered the predictable consequences of our hard work all week: sun burns, sore muscles, and a big pile of unread emails. But all in all, I would not complain.