Sunday, May 15, 2011

Israel and France, sister countries

Israel: the former president Katsav is in prison has been sentenced to prison for rape.
France: the former future presidential candidate Strauss-Kahn is being charged with attempted rape.

One main difference is that the Israeli justice was on the first case, but it is the US justice that is on the second case. I am having grave doubts about the French justice system's treatment of public figures.

Saturday, May 14, 2011

How to write programs

I have spent much of this week proofreading the programming assignments for my Fall course on introduction to programming. The texts contain many recommendations about what to put in but no recommendation on what not to put in, and they themselves are often rather wordy. I trimmed the texts, starting by removing 90% of the introductory paragraphs that give the broad context. When a student reads an assignment, his primary worry is to see what he has to do, not how the problem fits into some area of broader interest, so a sentence or two is sufficient.

In one lecture, I give a "design recipe" to design programs:
1. Define the data and provide concrete examples.
2. Define the procedure’s type signature and call structure.
3. Write a contract for the procedure and provide some test cases.
4. Write the procedure (in code).
5. Run your program on your test cases.

This year I think I'm going to add a step.
6. Clean-up your program - remove extraneous lines, consider removing helper procedures that are only called once, consider replacing nested "if" conditions by a list of cases, shorten or lengthen variable names, etc.

Or perhaps I could simply suggest:
6. Delete everything and do steps 1-5 over.
Isn't that what many good writers do? I am sure that regardless of the care with which the programmer has designed it, a program would be much better and much more elegant the second time.

Monday, May 9, 2011

The worst commercial web site

The French train company SNCF has one of the worst web sites I have ever seen. I usually go to that site to try to buy a train ticket, but it is exceedingly difficult. The big thing that occupied much of the screen this weekend on their web site: the news that SNCF sponsors the Winter Olympic games in the Alps for 2018. That's typical of the kind of information with which SNCF clutters their front page: irrelevant for 99.99% of the people accessing that web page.

I spent about one hour trying unsuccessfully to buy a ticket to go to Chamonix from Paris in August, taking a night train on the way there and a TGV on the way back. I finally determined, through trial and error, that August must be too far off for the night train system (but not for the TGV system). I will now try to buy my ticket on the phone, assuming that customer help replies to my mail asking for a phone number that can be called from abroad. I run into that problem every summer. My solution, when I am in France, is usually to physically go to the nearest train station and ask an actual physical person to help me, after standing in line for half an hour.

How come airlines and travel agents planning air travel have such convenient, well-designed websites, yet years after year the SNCF website remains just as bad as ever? Maybe the web designers are secretly trying to torpedoe their online information and reservation systems, so as to preserve employment by forcing customers to interact with SNCF employees in the real physical world. There is money to be made by someone who would build a website on top of sncf.fr, navigating the sncf website in such a way that its intricacies are transparent for the end user!

Update: no response to my email (the website promised an answer within 2 days, and it's been 6 days.) Friends in France went to the train station to asked for a phone number to call from abroad, and gave me the response: a number that only leads to an error message when called from here. French online travel companies sell tickets for flying, renting cars, hotels, tourism, but no train tickets. With this kind of marketing, I foresee a bleak future for SNCF.

Sunday, May 8, 2011

The end of tenure

There's an article in "The Nation" about the inexorable dwindling, and perhaps eventual near-disappearance, of tenured jobs in academia.

A friend of mine, who teaches music in high school in Providence, has been waiting for a couple of months to hear whether she is fired for good or being rehired. Every year the Providence school district sends teachers dismissals notices and then hires them back a few months later once the budget is figured out, she told me. She is in her late twenties and takes it philosophically, not having known a society with secure jobs. (Incidentally, next year, if she is rehired, she will be working longer hours: the schoolday will end at 4pm instead of 2:50pm.)

To me, that is mind-boggling. All the people in my extended family who were not farmers worked their whole lives in secure jobs. Those who, starting in the late 19th century, were teachers or professors, saw it primarily as a vocation. But how does one nurture a vocation in an environment in which every year your employment might be terminated for budget reasons? The workplace model that is fast emerging does not seem to give any value to loyalty. What then is the point of being salaried? Better be a self-entrepreneur. If that is how they are going to be treated, maybe my friend should get together with a few like-minded teachers, and they should just create their own school.

I found a few articles about it in the news:

Shortly after Mayor Angel Taveras took office, amid what he described as a budget catastrophe, 1,934 public school teachers in Providence were fired.
The mayor and school board said they sent the dismissal notices on Feb. 25 to meet the March 1 deadline imposed by the state's Teacher Tenure Act, which sets legal conditions for the dismissal of teachers based upon economic exigency. Taveras and co-plaintiff Thomas Brady, the school superintendent, say that though they fired the teachers they intended to hire most of them back after studying the city's financial situation.

Friday, 25 Feb 2011, 1:23 PM EST
When asked Friday morning about the four-to-three vote, Taveras said the move was necessary as the city and school district look to close a multi-million dollar budget gap. "What we tried to do was create the maximum amount of flexibility, so we could make informed decisions and do it right," Taveras said. "We have to balance our budget. We have to educate our kids. We're going to do both." It's not unusual each spring for a number of teachers to receive layoff notices, only to be recalled a few months later once the budget is set. This difference this time is all of the teachers have been fired, not laid off. With layoffs, teachers are asked back based on seniority. However with terminations, the school district has more power to decide who will stay and who will go.

Tuesday, 03 May 2011, 10:26 PM EDT, PROVIDENCE, R.I.
The Providence school board has voted to immediately rehire 1,445 public school teachers. More than 1,900 were terminated in February to help balance the budget. Under the rehire plan, teacher seniority is no more. School principals will decide the teachers' duties inside the school.

Friday, May 6, 2011

Looking for a random bit

It is natural to look around us and quickly spot number patterns -- numbers or sequences that are surely not there by chance -- even when we are just making up the pattern almost in spite of ourselves. But how do you come up with a random number?

I was wondering about that driving home last night. Imagine you're having a nightmare, being chased down an alley, and you have to make a split decision whether to turn right or left, so that the ennemy chasing you won't be able to guess. Flip a coin - but what if you don't have a coin? How do you quickly make up a random decision?

As I was driving, I looked around me for features that would help me find a random number. I would have been happy with just one small random bit. Street lights, signs, speed limits, curves of the road. Branches of tall, dark trees. Gas stations. Dark sky. My cell phone was dead, and neither my car clock nor my car radio work any more. There was no random bit in sight.

If I had been hiking in a mountain, I could have given myself a goal some distance away, then counted my steps mod 2; however that would not have been really random, because, as I got close to the goal, I could have shortened or lengthened my steps in spite of my efforts for objectivity, and ended up with a number that would have been biased in some way. I am Eve, and the random bit must be protected against my malicious attempts to influence the result!

I could just come up with a number, 0 or 1, but how do I know it's random?

I could take my pulse -- how many heart beats before I get to the light? -- mod 2, except that there is always a slight uncertainty in that counting; plus, I was driving.

Finally I found an approximate solution: count, mod 2, the number of cars coming the other way, from that point on until I got home. That almost worked, except that one car came out of an intersection and turned into my street as I was just driving by, so I (Eve) had to make a subjective choice whether or not to include it; so I could have manipulated the final result in that way; but I decided it should be included and did not change my mind later.

This train of thoughts affected my driving -- it's not unusual. In the present case, when I got to the turn into my street, I sped up to go across the intersection quickly, so that no other car could come by while I was turning and present me with another subjective borderline case. I got lucky, and the intersection stayed empty while I was turning; and when I got home, my number was 33. Mod 2, that's a 1. Finally, I found a pretty good random bit!

Did I miss something obvious, I wonder? It seemed ludicrously difficult.

We are wired to find patterns, but it is much harder to spot randomness.

Thursday, May 5, 2011

"Counting and waiting are the same"

That's what Joseph Hellerstein said today during his talk at Brown.

While I wait for the bus, I can engage my neighbors if there are any people around me; I can watch the trees, the birds, the traffic; I can turn inwards and focus on a problem I am currently working on. Or I can count while I wait.

Numbers are our friends.

When I was a kid, I used to have high blood pressure whenever the school nurse took my blood pressure. Waiting for her to measure it made me nervous and raised the pressure. But one day I found the secret to low blood pressure: counting. Counting keeps my blood pressure down.

When I am bored, or stressed, or at the dentist's, I count. Which numbers are prime? What are their divisors? Running the Eratosthenes sieve in my head passes the time pleasantly. Numbers are comfortingly familiar. They have a calming effect.

I can also count what I see while waiting. What fraction of the cars passing me have a passenger? How many SUV's? Do the license plates exhibit any discernible patterns? Counting helps the world make sense even when it doesn't.

Wednesday, May 4, 2011

How to motivate PhD students

Andy Yao was my first research mentor, when I was a visiting student in Princeton. After he had given me an open problem and we discussed it for a couple of weeks, he formulated an intermediate conjecture. If we could prove it, it would be a step forward. If we found a counter-example, it would give us new insight on the hidden difficulties.

Then he said: "Let's take a bet. Let's both try to resolve this question before we meet again next week, and let the stake of the bet be a dinner".

I couldn't pass up such a challenge, of course. I worked on the question intensively until I had solved it, a couple of days later. It made me so happy! I could barely contain my excitement. Later that day I saw Andy Yao at a seminar that we were both attending, and, unable to wait until the end of the talk, I leaned towards him and whispered with a big smile: "I solved it!" - and then, a little anxiously: "How about you, did you solve it?" No, he had not solved it. He said he was looking forward to hearing my solution during our next meeting.

And so, a few days later, we went (along with Kai Li) to a very good Chinese restaurant on Route 1 for dinner. Andy ordered lots of food, and, in particular, some fresh lobster. But I had never had that before and didn't know how to eat it properly, so I politely declined the lobster, contenting myself with the other dishes. In my memory, the dinner was delicious.

Now I see that that bet was an obvious ploy to get the student interested. I fell for it completely! What a great idea.

Tuesday, May 3, 2011

How to write papers: a reader-as-machine perspective

The reader has short attention span and little memory. Assuming that the reader is someone who wants to check correctness of a paper, how does the writer take into account the reader's limited capabilities? Imagine the reader is a machine with limited resources in time and memory, and that is interruptible.

Dealing with the short attention span:
(1) Each piece of information in the paper should be neatly packaged in about half a page, so that the reader can take a break after absorbing the material in that half-page.
(2) The most interesting result should come first. Or, rather, the paper should start with a shortest path to the main idea. This way, if the reader gives up after a few pages, it maximizes the chance that he will get to the main point of the paper.
(3) Side issues should be raised in comments or remarks separated from the proof of the main result; that is the presentation chosen, for example, in the Jerrum-Sinclair 1989 paper on computing the permanent.

Dealing with lack of memory:
(1) State lemmas as close as possible to the place where they are used; state definitions as close as possible to the place where they are used.
(2) A definition or a notation takes room in the reader's memory: minimize that, wisely taking into account time-space tradeoff:
"Let x denote blah blah blah ... Using x,... because of x..."
versus
"Using blah blah blah, ... because of blah blah blah".
Is it preferable that the reader first parse blah blah blah, then have to store it in memory, or that he have to parse blah blah blah every time he encounters it?
(3) Order lemmas, facts and theorems so as to minimize the width of the resulting dependency graph. In that way, the reader only has to remember a few statements at a time.

Friday, April 29, 2011

Waiting for the bus

Today when I arrived at the bus stop there were two people waiting already. The man presented the woman as his wife and insisted in having her walk a bit to show me, by her gait, that she was handicapped. I thought there was something also slightly off about the man, but the exchange was surprisingly deep.

"- What kind of work do you do?
- I teach.
- Oh, you're a teacher! Good for you! [Hug, while I uncomfortably wonder what an appropriate reaction would be]... how many students do you teach?
- About 100.
- And how many fail?
- Oh, maybe 2 or 3.
- Why do they fail, those 2 or 3?
- I don't know.
- Maybe they're not interested?
- Maybe.
- And how long do students stay?
- 4 years.
- They stay 4 years, and then they're off? And they all do good except 2 or 3?
- That's right.
- And then you teach another 100 students? Every year it's like that? They leave and do good, but you stay behind?
- Yes."

That man, who seemed to have something slightly wrong with him, managed in 5 minutes and in spite of my terse answers to raise some of the more difficult questions related to teaching: why do some students fail? How do we deal with being "stuck" at the college level while students mature and move on to the next phase of their lives?

Later on the bus, as I was working, I vaguely heard him talking loudly, but didn't really pay attention. Suddenly the bus stopped, and the driver, apparently struggling to contain his anger, shouted: "All right, enough already. Get off the bus!" A very unpleasant, tense discussion followed, with us as silent bystanders. One man intervened to express support for the driver, because "I've got to get to work", he said. The driver threatened to call the cops. The man answered that he had paid his fare and had a right to be there. The driver replied: "Well, I'll talk to them, and who do you think they're going to believe, you or me?" The woman got off, in her shuffling gait, saying: "I'm getting off. I don't want to get arrested." The man finally got off as well, and we resumed our ride. One woman started chatting pleasantly with the driver. Another one said: "That's the kind of things that happen in the 9am bus. The population is much more diverse than in earlier buses". Several people laughed. I felt bad for the stranded couple, thought the whole incident had been poorly handled, the man should have been allowed to stay on the bus, and wished I had done something. Speaking up had seemed pointless at the moment. A very unpleasant incident! (And that made me late for my meeting, too).

Friday, April 8, 2011

Voting theory in medieval times

"Blanquerna" is a 13th century Catalan novel by Ramon Lull. The protagonist Natana renounces her possessions and enters a nunnery. When it is time to choose a new Abbess, Natana has a suggestion: she tells the twenty sisters that they should first select electors, who would compare candidates with each other according to four conditions, namely:
- which of them best loves and knows God,
- which of them best loves and knows the virtues,
- which of them knows and hates most strongly the vices, and
- which is the most suitable person.
The electors should compare the candidates two by two, and, for each pair, determine which they judge to be better. In the case of 9 candidates, 36 compartments will be produced in which the votes for each candidate will appear. The candidate to be elected should be "the one with the most votes in the most compartments."

The phrase is somewhat ambiguous, but another work by the same author, "Artifitium electionis personarum" (which was discovered in 2001) is more explicit: first create a matrix for pairwise comparisons of candidates. Then, "each elector shall respond and choose the one that seems best to him. One mark shall be made against the letter representing the person who has received more votes. This mark is made against that letter wherever it appears in various places [in the vote matrix]."

Of course, one has to worry about ties. Indeed, "one of the sisters asked her: "If it turns out that some candidates have as many votes as each other in the compartment, what procedure does the art recommend?" Natana replied: "The art recommends that these two or three be judged according to art alone. It should be found out which of these best meet the four aforementioned conditions, for she will be the one who is worthy to be elected.""

(Gathered from reading "Voting in the Medieval Papacy and Religious Orders", by Iain McLean and Haidee Lorrey)