I recently bought a ticket to go to France in May. I paid a little more than the lowest price, so that I could fly direct, and was very happy with my plan.
But two days ago I learned that my flight was cancelled. After calls to the various partners involved (airfare.com sold me an Iberia ticket for a flight operated by American Airlines...), I saw that the alternatives offered, all with a connection, were all significantly less convenient than what I could otherwise get (as well as a little bit more expensive). I gave up and asked for a refund. They are no longer offering the product that I bought, so let them give me my money back and we'll just forget the whole thing. That struck me as the simplest solution and the end of my frustrations.
But it's not easy to get a refund! After a few hours on the phone, this is my current understanding: if a customer buys a ticket and the flight later is cancelled (three months in advance) by the airline, then the customer will be refunded the price of their ticket, minus a $100 fee.
The morale of the story is: don't get into a fight with airlines. They're bigger than you and it's not worth your time.
Also: don't buy your ticket more than three months in advance!
Tuesday, January 31, 2012
Monday, January 23, 2012
"Proving something does not make it true"
This weekend I accidentally stumbled on a page for science teachers. http://digipac.ca/chemical/proof/index.htm
I was appalled by the twisted message, that reduces logic to a suspicious rhetorical device. Money quotes:
Proof does not equal truth
Here's a definition of what it means to prove something: "Proof is arriving at a logical conclusion, based on the available evidence." Notice that this has absolutely nothing to do with being right or wrong.
Proving something does not make it true. It just means that you have convinced other people that the evidence supports your conclusion.
I was particularly stung by the third quote, because I use similar terms to try to explain how to write a proof: I usually say that it should be just formal enough, but not too formal, and that "just formal enough" depends on the recipient - just enough to convince the reader that you indeed have a valid proof.
I was appalled by the twisted message, that reduces logic to a suspicious rhetorical device. Money quotes:
Proof does not equal truth
Here's a definition of what it means to prove something: "Proof is arriving at a logical conclusion, based on the available evidence." Notice that this has absolutely nothing to do with being right or wrong.
Proving something does not make it true. It just means that you have convinced other people that the evidence supports your conclusion.
I was particularly stung by the third quote, because I use similar terms to try to explain how to write a proof: I usually say that it should be just formal enough, but not too formal, and that "just formal enough" depends on the recipient - just enough to convince the reader that you indeed have a valid proof.
Sunday, January 22, 2012
Adaptive Online Adversaries
This year there are presidential elections in both France and the US. The leading party of the opposition is the Republican party in the US and the Socialist party in France.
This year for the first time in France the Socialist candidate was chosen by election, in a quick two-round affair: a one-day vote to wean all but two of the candidates, and a one-day runoff vote one week later.
The Republican primaries in the US are a prolonged game of suspenseful fractional elections, state by state, little by little.
Since the voters of the beginning period are not a random sample of the whole set, their votes are not necessarily representative of the final outcome. Information about voters' intentions is revealed gradually, and late voters can adapt their choice given knowledge of previous voters' choices. They have more information than in France, but that information is not uniformly distributed among voters: early voters have no information. It's like an online algorithm in which votes arrive online and the adversary's choices for the ith vote can depend on votes 1 through i-1. That makes for exciting news!
This year for the first time in France the Socialist candidate was chosen by election, in a quick two-round affair: a one-day vote to wean all but two of the candidates, and a one-day runoff vote one week later.
The Republican primaries in the US are a prolonged game of suspenseful fractional elections, state by state, little by little.
Since the voters of the beginning period are not a random sample of the whole set, their votes are not necessarily representative of the final outcome. Information about voters' intentions is revealed gradually, and late voters can adapt their choice given knowledge of previous voters' choices. They have more information than in France, but that information is not uniformly distributed among voters: early voters have no information. It's like an online algorithm in which votes arrive online and the adversary's choices for the ith vote can depend on votes 1 through i-1. That makes for exciting news!
Saturday, January 21, 2012
The education contract
Before I learned how to study for class, from fourth grade up to some time in college I was never better than second best in class. After I learned how to study (see yesterday's post), one year, the year I switched to computer science, I decided to apply that studying method and give my all to learning CS. That enabled me to maximize the benefit reaped from my courses (with amazing results on my grades, but that's a detail).
Still, I did not learn as much as I could have, but the fault lied, not with me, but with the teachers. Even now, I am still a bit annoyed with those among my instructors that year who taught bad courses. Dedicated students deserve good courses. When students put a lot of effort into a course, the instructor has a responsibility to make it worthwhile by also putting a lot of effort into the course - and conversely. It's a dynamics of mutual emulation.
I am thinking about this as I re-read "La Sorbonne en guerre", my grandfather's book about being a professor during the Occupation. At the beginning of the war, universities were temporarily closed, students and professors were scattered, and no one knew what was going to happen. In the middle of the chaos, students kept trying to study for their exams, and my grandfather's students resorted to sending him assignments by postal mail. He would receive translations of ancient Greek classical texts, grade them and send them back to his students by postal mail. Word got around, and he started receiving translations from students who were not his! And so he graded even work written by complete strangers and mailed it back to them. It seems to me that there was a sense of duty and of mutual respect: one party was there to learn, and the other was there to help learn, like an implicit contract. Even in the middle of destruction, survival of the intellectual life was for them a matter of highest priority.
That view of education, resolutely non-utilitarian, is to some extent present at Brown. It can also be found in France: for example, when I taught with Jean-Jacques Levy, I was amazed by the time he put in preparing lectures and assignments, true perfectionist that he is. That makes teaching a large class intimidating: each typo in a homework problem, each poorly specified exercise, each algorithm whose presentation in class is botched means that many dedicated students will waste time on something non-constructive, and it is damaging. It puts a dent in the contract.
Still, I did not learn as much as I could have, but the fault lied, not with me, but with the teachers. Even now, I am still a bit annoyed with those among my instructors that year who taught bad courses. Dedicated students deserve good courses. When students put a lot of effort into a course, the instructor has a responsibility to make it worthwhile by also putting a lot of effort into the course - and conversely. It's a dynamics of mutual emulation.
I am thinking about this as I re-read "La Sorbonne en guerre", my grandfather's book about being a professor during the Occupation. At the beginning of the war, universities were temporarily closed, students and professors were scattered, and no one knew what was going to happen. In the middle of the chaos, students kept trying to study for their exams, and my grandfather's students resorted to sending him assignments by postal mail. He would receive translations of ancient Greek classical texts, grade them and send them back to his students by postal mail. Word got around, and he started receiving translations from students who were not his! And so he graded even work written by complete strangers and mailed it back to them. It seems to me that there was a sense of duty and of mutual respect: one party was there to learn, and the other was there to help learn, like an implicit contract. Even in the middle of destruction, survival of the intellectual life was for them a matter of highest priority.
That view of education, resolutely non-utilitarian, is to some extent present at Brown. It can also be found in France: for example, when I taught with Jean-Jacques Levy, I was amazed by the time he put in preparing lectures and assignments, true perfectionist that he is. That makes teaching a large class intimidating: each typo in a homework problem, each poorly specified exercise, each algorithm whose presentation in class is botched means that many dedicated students will waste time on something non-constructive, and it is damaging. It puts a dent in the contract.
Friday, January 20, 2012
On studying for class
As the beginning of the semester is approaching, it may be a good time to think about how to study.
Here is how I used to go about learning when I was a student, before I knew better.
During Math class, which I enjoyed, I paid close attention and whenever I had an inkling of how to do the next step - for example, after the instructor had stated a lemma but beforehe he or she had proved it - I would work through the argument by myself, oblivious to the lecture; after a couple of minutes, I would raise my head and catch up with the lecture. Occasionally, I would go off the wrong track, waste some time, then have trouble catching up, but more often it was a very effective way to stay engaged. It's about active learning. Even now, I would still recommend that way of attending lectures.
To study material from lecture, I would quickly skim over my lecture notes to memorize the main definitions and theorems. Then, to work through assignments, I would do many exercises with ease, then stop when I encountered a difficulty and, after giving it a fair try, either manage or fail to solve the problem, call it good and turn in what I had - usually about 80 or 90 percent of the assignment. That meant that, as the assignment usually had problems of increasing difficulty and I stopped before the last problem, my studying reinforced my knowledge of material which I already understood fairly well, but never made me get insights that I had not already acquired in class. I do not recommend that way of studying.
One year I made a friend with whom I worked closely, and, from her, I learned how to study.
To study material from lecture, here is what she did: she would reconstruct the lecture. She had her lecture notes in her notebook next to her, but usually kept it closed. She would try to write down definitions and main theorems from memory, checking by briefly opening her notebook after writing. Moreover, she would also try to reconstruct the arguments by writing down the statements of the lemmas and outlining a proof sketch for each of them! Of course, that was time consuming: even a well-understood two-hour lecture that was fresh in our memory would take at least one hour and often close to two hours to redo. But if there was any subtlety that had gone by unnoticed during class, it really put the spotlight onto it. Then, to do the assignments, she would put in about twice as much work as I used to: indeed, she proudly claimed that she would never turn in an incomplete assignment. Since the last problems were much more difficult than the rest, she would spend the larger part of her time working on those challenging problems. At first that seemed stupid to me: why would one spend so much time reviewing lecture notes, when there was no grade associated to that activity, and we had understood the class fine anyway? Why would one spend more than half of one's study time on a tiny part of the assignment, for a tiny part of the grade? What an inefficient use of one's time! But then, as I watched her work, a realization dawned on me: the assignment was a way for her, not just to practice, but to gain better understanding of the material. She was learning in depth.
Here is how I used to go about learning when I was a student, before I knew better.
During Math class, which I enjoyed, I paid close attention and whenever I had an inkling of how to do the next step - for example, after the instructor had stated a lemma but before
To study material from lecture, I would quickly skim over my lecture notes to memorize the main definitions and theorems. Then, to work through assignments, I would do many exercises with ease, then stop when I encountered a difficulty and, after giving it a fair try, either manage or fail to solve the problem, call it good and turn in what I had - usually about 80 or 90 percent of the assignment. That meant that, as the assignment usually had problems of increasing difficulty and I stopped before the last problem, my studying reinforced my knowledge of material which I already understood fairly well, but never made me get insights that I had not already acquired in class. I do not recommend that way of studying.
One year I made a friend with whom I worked closely, and, from her, I learned how to study.
To study material from lecture, here is what she did: she would reconstruct the lecture. She had her lecture notes in her notebook next to her, but usually kept it closed. She would try to write down definitions and main theorems from memory, checking by briefly opening her notebook after writing. Moreover, she would also try to reconstruct the arguments by writing down the statements of the lemmas and outlining a proof sketch for each of them! Of course, that was time consuming: even a well-understood two-hour lecture that was fresh in our memory would take at least one hour and often close to two hours to redo. But if there was any subtlety that had gone by unnoticed during class, it really put the spotlight onto it. Then, to do the assignments, she would put in about twice as much work as I used to: indeed, she proudly claimed that she would never turn in an incomplete assignment. Since the last problems were much more difficult than the rest, she would spend the larger part of her time working on those challenging problems. At first that seemed stupid to me: why would one spend so much time reviewing lecture notes, when there was no grade associated to that activity, and we had understood the class fine anyway? Why would one spend more than half of one's study time on a tiny part of the assignment, for a tiny part of the grade? What an inefficient use of one's time! But then, as I watched her work, a realization dawned on me: the assignment was a way for her, not just to practice, but to gain better understanding of the material. She was learning in depth.
Thursday, January 19, 2012
On parenting
I had children younger than most of my US friends, and when it was their turn to raise young kids, whenever they saw me they asked questions such as: "How did you do it? I never realized it was so hard!", or "I love him/her/them, but I'm barely making it through the days", or "Tell me, how many more years do I have to go through before it gets easier?"
Yes, I do have a few friends who blossom as parents and seem to take everything in stride, usually leaving their career by the wayside along the way to perpetual parental bliss. It's a sacrifice that seems to come easily to those friends, who appear to have a natural vocation for pure parenthood.
But most of my friends are juggling career and parenting, and, while parents of young children, live in a state of constant tension, stress and tiredness. They do not have quite enough energy and time to perform as well as they expect from themselves at work, nor to be as attentive to their children as they would like to be.
As a parent, one of the most helpful things I got told came from the mother of a colleague. I only met her once, when they came to dinner at my house.
Making small talk, she asked: "So, how is it, doing research, having two young children, and all that?"
I answered succinctly: "It's not easy".
She glanced at me, surprised by my frankness. After a short pause she replied: "It will get better."
Then, seeing that her answer hadn't sunk in, she insisted: "I have had two children myself. I remember what it's like. It will get better. It really will!"
That time, I paid attention. Unnoticed by the other people present at dinner, we exchanged a look of mutual understanding; and the conversation moved on to other topics.
In the following months, whenever things were almost overwhelming, I recalled what she had told me and, instead of thinking "Things cannot go on like this," I soothed myself by repeating in petto: "It will get better."
Yes, I do have a few friends who blossom as parents and seem to take everything in stride, usually leaving their career by the wayside along the way to perpetual parental bliss. It's a sacrifice that seems to come easily to those friends, who appear to have a natural vocation for pure parenthood.
But most of my friends are juggling career and parenting, and, while parents of young children, live in a state of constant tension, stress and tiredness. They do not have quite enough energy and time to perform as well as they expect from themselves at work, nor to be as attentive to their children as they would like to be.
As a parent, one of the most helpful things I got told came from the mother of a colleague. I only met her once, when they came to dinner at my house.
Making small talk, she asked: "So, how is it, doing research, having two young children, and all that?"
I answered succinctly: "It's not easy".
She glanced at me, surprised by my frankness. After a short pause she replied: "It will get better."
Then, seeing that her answer hadn't sunk in, she insisted: "I have had two children myself. I remember what it's like. It will get better. It really will!"
That time, I paid attention. Unnoticed by the other people present at dinner, we exchanged a look of mutual understanding; and the conversation moved on to other topics.
In the following months, whenever things were almost overwhelming, I recalled what she had told me and, instead of thinking "Things cannot go on like this," I soothed myself by repeating in petto: "It will get better."
Wednesday, January 18, 2012
Independence
Whenever I read about "independence", it raises a red flag in my mind. If a paper contains a probabilistic analysis, bugs or even errors can often be hidden behind the word "independent". I am slow in believing independence, and especially conditional independence. That's where I have seen many bugs come up in proofs by me and by others. I am now skeptical of any unproved claims of independence.
Is the pro-Colbert super-PAC “Americans for a Better Tomorrow, Tomorrow” independent of Colbert? As it exists in real life, we are assuming, barring evidence to the contrary, that it is not coordinated. But if it came up in a science paper, we would ask to see a proof.
Is the pro-Colbert super-PAC “Americans for a Better Tomorrow, Tomorrow” independent of Colbert? As it exists in real life, we are assuming, barring evidence to the contrary, that it is not coordinated. But if it came up in a science paper, we would ask to see a proof.
Monday, January 16, 2012
Teaching algorithms: the concepts
The other day I saw a student studying a handout with a vocabulary list of figures of speech in English, with definitions and examples. For example, there was "Juvenalian irony" , "Metaphor", "Meter", etc. What struck me was that the list was in alphabetical order! What a way to teach! I started imagining what would happen if I organized my Algorithms class or my lecture notes using that principle. The reader would find topics in the following order:
Asymptotics
Average case
Big oh
Bipartite matching
Divide and conquer
Dynamic programming
Fast Fourier transforms
Greedy algorithms
Heaps
Huffman coding
Induction
Knapsack
Little oh
Matching
Max cut
Max flow
Median finding
Min cut
Minimum spanning tree
Randomized algorithms
Recurrences
Run time
Scheduling
Shortest paths
Sorting
Strassen's algorithm
Union find
Worst case
Asymptotics
Average case
Big oh
Bipartite matching
Divide and conquer
Dynamic programming
Fast Fourier transforms
Greedy algorithms
Heaps
Huffman coding
Induction
Knapsack
Little oh
Matching
Max cut
Max flow
Median finding
Min cut
Minimum spanning tree
Randomized algorithms
Recurrences
Run time
Scheduling
Shortest paths
Sorting
Strassen's algorithm
Union find
Worst case
Dealing with email: the subject line
I stumbled on articles about how people manage email.
-"Revisiting Whittaker and Sidney's "email overload" ten years later."
-"Everything through email"
http://eprints.rclis.org/bitstream/10760/13707/1/2007_Email_PIM_WBG_PIM_book_Chapter_authors_final.pdf
-"Am I wasting my time organizing email? A study of email refinding." http://people.ucsc.edu/~swhittak/papers/chi2011_refinding_email_camera_ready.pdf
I saw one piece of advice that would make our lives easier: to put the subject line to good use.
That made me wonder what subject line I had chosen. Here is a representative sample of my recently composed work-related emails:
- my attempt at a high-level description of Elkin's algorithm
- The problem with your proof
- notes on dp
- we can chat on google gmail?
- back
- Back at Brown
- (no subject)
- dynamic networks reference (a model)
- sujet cours College de France? [English: topic course at College de France?]
- your student
- on another topic
- ton avis [English: your advice]
- resume [English: summary]
Before I looked, I was ready to give myself a pat in the back for the care with which I compose my subject lines. Now I realize that actually, my subject lines are only well-done when I am careful: for every message with a carefully chosen subject line, it turns out that I write several that are completely uninformative. I mean, come on: "on another topic": what kind of a subject is that?? Even "notes on dp" is highly context-dependent and pretty non-descriptive of my work.
This suggests a late new year's resolution: when I take the time to compose an email, I should take a little bit of extra time to compose the subject line, keeping in mind that it may get archived and might need to be retrieved in several months.
-"Revisiting Whittaker and Sidney's "email overload" ten years later."
-"Everything through email"
http://eprints.rclis.org/bitstream/10760/13707/1/2007_Email_PIM_WBG_PIM_book_Chapter_authors_final.pdf
-"Am I wasting my time organizing email? A study of email refinding." http://people.ucsc.edu/~swhittak/papers/chi2011_refinding_email_camera_ready.pdf
I saw one piece of advice that would make our lives easier: to put the subject line to good use.
That made me wonder what subject line I had chosen. Here is a representative sample of my recently composed work-related emails:
- my attempt at a high-level description of Elkin's algorithm
- The problem with your proof
- notes on dp
- we can chat on google gmail?
- back
- Back at Brown
- (no subject)
- dynamic networks reference (a model)
- sujet cours College de France? [English: topic course at College de France?]
- your student
- on another topic
- ton avis [English: your advice]
- resume [English: summary]
Before I looked, I was ready to give myself a pat in the back for the care with which I compose my subject lines. Now I realize that actually, my subject lines are only well-done when I am careful: for every message with a carefully chosen subject line, it turns out that I write several that are completely uninformative. I mean, come on: "on another topic": what kind of a subject is that?? Even "notes on dp" is highly context-dependent and pretty non-descriptive of my work.
This suggests a late new year's resolution: when I take the time to compose an email, I should take a little bit of extra time to compose the subject line, keeping in mind that it may get archived and might need to be retrieved in several months.
Saturday, January 14, 2012
What do professors do between semesters?
Here is how my time was spent this week, a typical light week. It was light in the sense that on each day, besides tending to that day's tasks, I had some "remaining time" that could be spent working by myself on longer-term projects. The longer-term project that was my focus this week was the preparation of a journal submission.
Monday: Attended ITCS in Boston. 4 hours of transportation, 4 hours of attending talks, 2 hours of chatting with colleagues in the hallways (on topics similar to the ones discussed on TCS blogs). Started to prepare a scientific blog post (still pending).
Tuesday: Sent some recommendation letters - the most urgent matter on my to-do list. Had a hiring-related email conversation. Met with a colleague to discuss what ideas to convey at an upcoming conference talk. Remaining time was spent proofreading a paper about to be submitted to a journal. Also attended a Skype/google chat/phone meeting to discuss another paper to be submitted to a journal.
Wednesday: Did two important items of my to-do list, involving photocopying, scanning and faxing. Cleaned up a little bit of my overflowing email box. Met a student over lunch. Remaining time was spent editing a subsection of the paper to be submitted to a journal.
Thursday: Attended a faculty meeting about hiring. Met with head TA to prepare course for this coming semester. Remaining time was spent continuing to edit the subsection of the paper in preparation, as well as the next section.
Friday: Did three items on my to-do list, involving emails and phone calls, related to hiring and to teaching. Met with a graduate student to read a research paper together. Missed a deadline for turning in a report, not by oversight but by a conscious decision (I put it on my to-do list for Tuesday): instead, remaining time was spent continuing to edit the section of the paper in preparation. At the end of the day, when it was about finished, I started thinking that maybe it should be written in a completely different way, and that I should re-write those two sections from scratch.
Monday: Attended ITCS in Boston. 4 hours of transportation, 4 hours of attending talks, 2 hours of chatting with colleagues in the hallways (on topics similar to the ones discussed on TCS blogs). Started to prepare a scientific blog post (still pending).
Tuesday: Sent some recommendation letters - the most urgent matter on my to-do list. Had a hiring-related email conversation. Met with a colleague to discuss what ideas to convey at an upcoming conference talk. Remaining time was spent proofreading a paper about to be submitted to a journal. Also attended a Skype/google chat/phone meeting to discuss another paper to be submitted to a journal.
Wednesday: Did two important items of my to-do list, involving photocopying, scanning and faxing. Cleaned up a little bit of my overflowing email box. Met a student over lunch. Remaining time was spent editing a subsection of the paper to be submitted to a journal.
Thursday: Attended a faculty meeting about hiring. Met with head TA to prepare course for this coming semester. Remaining time was spent continuing to edit the subsection of the paper in preparation, as well as the next section.
Friday: Did three items on my to-do list, involving emails and phone calls, related to hiring and to teaching. Met with a graduate student to read a research paper together. Missed a deadline for turning in a report, not by oversight but by a conscious decision (I put it on my to-do list for Tuesday): instead, remaining time was spent continuing to edit the section of the paper in preparation. At the end of the day, when it was about finished, I started thinking that maybe it should be written in a completely different way, and that I should re-write those two sections from scratch.
Subscribe to:
Posts (Atom)