In the US, sometimes at Mass I see people quietly playing angry birds or scrabble on their iPhone during the homily. France I thought had been preserved until now. But at midnight Mass here in France, I saw a man texting on his phone immediately after receiving communion, while others were still standing in line for communion.
Are there no limits to that need to be constantly connected?
When are people not connected?
As far as I know, the shower might be the last refuge against the invasion of technology. I have yet to see a gadget to send email while showering.
Sunday, December 25, 2011
Friday, December 23, 2011
Learning Algorithms online
No, this is not about online algorithms, nor about learning theory.
I have signed up for Tim Roughgarden's online course on Algorithms, http://www.algo-class.org
One might wonder why I need to learn about divide-and-conquer, searching, quicksort and shortest paths. In fact, I'll be teaching Algorithms myself at the same time. What's wrong with me? Do I plan to steal Tim's lectures and repeat them verbatim to my students, thus sparing myself the need to understand the material? Have I been secretly incompetent during all the years during which I pretended to teach the material, and is this a remedial course to finally patch my ignorance in my alleged area of expertise? Am I so stingy that I can't refuse something that is offered for free? Or have I so bought into the school system of grades and diplomas that I can't pass on the chance for an easy way to get one more certificate? In a few months I will be able to add it to my vita, and perhaps it'll help me get a raise. Or do I enjoy criticizing other people so much that I'm going be watching those videos of Tim and snickering, and then posting on my blog nasty comments about every slip that might occur? Am I secretly in love with Tim, or do I secretly bear a grudge against him?
None of those reasons. I am curious to see someone else teach the same material that I teach. I look forward to the ability of fast-forwarding the parts I have down pat, and paying careful attention to the material which I have trouble conveying to my students. Perhaps I can use some of it to improve my own teaching.
Additionally, I am curious to see how the Stanford online courses work in practice, with the thought, in the back of my mind, that perhaps I will also engage in online teaching in the future, if the technology is user-friendly enough. The idea of higher education freely available to all in that manner is fascinating, and experiencing how it plays out on a familiar subject might help me understand the strong points and the weaknesses of the approach.
I have signed up for Tim Roughgarden's online course on Algorithms, http://www.algo-class.org
One might wonder why I need to learn about divide-and-conquer, searching, quicksort and shortest paths. In fact, I'll be teaching Algorithms myself at the same time. What's wrong with me? Do I plan to steal Tim's lectures and repeat them verbatim to my students, thus sparing myself the need to understand the material? Have I been secretly incompetent during all the years during which I pretended to teach the material, and is this a remedial course to finally patch my ignorance in my alleged area of expertise? Am I so stingy that I can't refuse something that is offered for free? Or have I so bought into the school system of grades and diplomas that I can't pass on the chance for an easy way to get one more certificate? In a few months I will be able to add it to my vita, and perhaps it'll help me get a raise. Or do I enjoy criticizing other people so much that I'm going be watching those videos of Tim and snickering, and then posting on my blog nasty comments about every slip that might occur? Am I secretly in love with Tim, or do I secretly bear a grudge against him?
None of those reasons. I am curious to see someone else teach the same material that I teach. I look forward to the ability of fast-forwarding the parts I have down pat, and paying careful attention to the material which I have trouble conveying to my students. Perhaps I can use some of it to improve my own teaching.
Additionally, I am curious to see how the Stanford online courses work in practice, with the thought, in the back of my mind, that perhaps I will also engage in online teaching in the future, if the technology is user-friendly enough. The idea of higher education freely available to all in that manner is fascinating, and experiencing how it plays out on a familiar subject might help me understand the strong points and the weaknesses of the approach.
My other theory on grades
Assignments are either for helping the students learn, or for evaluating them. Grades are either to give them an incentive to do the work involved in learning, or to evaluate them. Two very different goals!
For evaluation purposes, grades give the maximum information is the distribution has maximum entropy, so ideally there ought to be about 1/3 A's, 1/3 B's, and 1/3 C's.
For evaluation purposes, assignments are most useful if they help distinguish students from one another, so the ideal exercise is at the right level of difficulty so as to be solvable by exactly half of the students. An exercise that is successfully done by all serves no purpose for evaluation. An exercise that almost no one can do may still serve a purpose: that of distinguishing the few students who stand out by their ability to solve a problem that the vast majority could not do. Exercises with a variety of difficulty levels help evaluate more finely. Since the primary goal of midterms and finals is to evaluate, that's how they should be designed, and the median grade for those would probably be around 50. In fact, that's more or less how things are done in France. The learning part happens in exercises that are not graded, and the sole purpose of grading is to evaluate.
In the US, my experience is that assignments are usually designed so that, with enough time, most students can do most of the assignment: their primary purpose is to help the student learn. A very different perspective!
For evaluation purposes, grades give the maximum information is the distribution has maximum entropy, so ideally there ought to be about 1/3 A's, 1/3 B's, and 1/3 C's.
For evaluation purposes, assignments are most useful if they help distinguish students from one another, so the ideal exercise is at the right level of difficulty so as to be solvable by exactly half of the students. An exercise that is successfully done by all serves no purpose for evaluation. An exercise that almost no one can do may still serve a purpose: that of distinguishing the few students who stand out by their ability to solve a problem that the vast majority could not do. Exercises with a variety of difficulty levels help evaluate more finely. Since the primary goal of midterms and finals is to evaluate, that's how they should be designed, and the median grade for those would probably be around 50. In fact, that's more or less how things are done in France. The learning part happens in exercises that are not graded, and the sole purpose of grading is to evaluate.
In the US, my experience is that assignments are usually designed so that, with enough time, most students can do most of the assignment: their primary purpose is to help the student learn. A very different perspective!
Thursday, December 22, 2011
My theory on grades
I wish students typically got a B in my course.
C's would be reserved to the students who stand out because they're at the lower tail of the distribution (something of the order of 5 percent of the students), and
A's would be reserved to the students who stand out because they're at the upper tail of the distribution (also something of the order of 5 percent).
This way students would expect to get a B, the bulk of the students would get the grade which they expected to get, and the occasional A would be a pleasant surprise.
As it happens, this semester my class was so good and hard-working that I gave a very large number of A's (40 percent!!), which meant that the cutoff point fell in the dense part of the distribution of grades, which meant that it was rather arbitrary: between the 20 "A students" with lowest average grade, and the 20 "B students" with highest average grade, I bet that the difference in performance is statistically completely insignificant. That's a lot of students who will curse their bad luck or question my judgment!
But even for next semester, I don't dare try my theory. B versus A grades don't really matter very much anyway for Brown CS students. The expectation is that they work hard, learn well, and get a good education. Whether that means giving A's to the majority (because we're so pleased with them), or giving B's to the majority (because they're doing as expected, and it's difficult for a student to stand out in an environment in which most are putting so much effort into their coursework), really does not matter much.
C's would be reserved to the students who stand out because they're at the lower tail of the distribution (something of the order of 5 percent of the students), and
A's would be reserved to the students who stand out because they're at the upper tail of the distribution (also something of the order of 5 percent).
This way students would expect to get a B, the bulk of the students would get the grade which they expected to get, and the occasional A would be a pleasant surprise.
As it happens, this semester my class was so good and hard-working that I gave a very large number of A's (40 percent!!), which meant that the cutoff point fell in the dense part of the distribution of grades, which meant that it was rather arbitrary: between the 20 "A students" with lowest average grade, and the 20 "B students" with highest average grade, I bet that the difference in performance is statistically completely insignificant. That's a lot of students who will curse their bad luck or question my judgment!
But even for next semester, I don't dare try my theory. B versus A grades don't really matter very much anyway for Brown CS students. The expectation is that they work hard, learn well, and get a good education. Whether that means giving A's to the majority (because we're so pleased with them), or giving B's to the majority (because they're doing as expected, and it's difficult for a student to stand out in an environment in which most are putting so much effort into their coursework), really does not matter much.
Wednesday, December 21, 2011
First impressions of Paris after a transatlantic red-eye.
As the airplane approaches, we see mostly darkness, punctuated by village and highway lights. In the distance, the City of Lights: a beneath a light veil-like cloud, a large cluster of dense, very bright lights, whose reflection in the dark gives the cloud a yellowish, almost golden appearance. I am musing on how funny it is that the cloud picked precisely Paris to hand over, not the surrounding countryside; I note that the cloud is much lighter than the occasional black clouds between us and the land down below. Then it hits me: it's smog!
Paris is choking in air pollution.
In the airport hallway, large signs on the sides advertised Paris. The first sign: Eiffel tower, Champs-Elysees,... Parisian monuments. The second sign: Opera, jazz, ... (meanwhile background music had Edith Piaf and then accordeon music). The third sign: strolls along the river, romantic scenery, used book shops by Notre Dame,... That was it. This is Paris! Nothing about La Defense, about businesses, or about the people living and working there. It looked like a pure tourist destination and nothing else.
Paris markets itself as merely a more authentic version of Disneyland.
At 8am in Paris, the subways were full of people standing close to one another, some fraction of them sniffing, sneezing or coughing. Colds and minor epidemics plague Parisians all winter long, in ways unknown to Rhode Islanders.
Paris is the Kingdom of Kleenex.
I had the usual hassles with unhelpful staff and buggy official information, no big deal but annoying and a waste of time.
In Paris, when something works right and easily at the first attempt, you stop in wonder and give thanks to God for that small miracle.
Paris is choking in air pollution.
In the airport hallway, large signs on the sides advertised Paris. The first sign: Eiffel tower, Champs-Elysees,... Parisian monuments. The second sign: Opera, jazz, ... (meanwhile background music had Edith Piaf and then accordeon music). The third sign: strolls along the river, romantic scenery, used book shops by Notre Dame,... That was it. This is Paris! Nothing about La Defense, about businesses, or about the people living and working there. It looked like a pure tourist destination and nothing else.
Paris markets itself as merely a more authentic version of Disneyland.
At 8am in Paris, the subways were full of people standing close to one another, some fraction of them sniffing, sneezing or coughing. Colds and minor epidemics plague Parisians all winter long, in ways unknown to Rhode Islanders.
Paris is the Kingdom of Kleenex.
I had the usual hassles with unhelpful staff and buggy official information, no big deal but annoying and a waste of time.
In Paris, when something works right and easily at the first attempt, you stop in wonder and give thanks to God for that small miracle.
Tuesday, December 20, 2011
The experience of reading a paper
Trying to read a proof in depth (say, because I was preparing a blog post on it), the reader may go through various feelings in sequence.
1. Stupidity; How come I don't understand it at all? Am I becoming stupid?
2. Anger and frustration; how come the authors leave some definitions ambiguous, and why did the referee not send the paper back to ask for another round of polishing?
3. An idea: let me just look for slides of a talk on the subject! Slides usually put much more emphasis on intuition and might help me understand what the authors meant to say.
4. Obstination; I can do it. There are no slides available, but I'm interested in the result and just need to put my mind to it. Go through examples systematically, try out the various interpretations until one fits and the proof goes through.
5. Suspicion. Is that result really correct? None of my interpretations seem to work.
6. Discouragement; I can't do it. I'll have to look up references of prior work and see which ideas are present in there and whether they are explained any better. This is turning into a major time sink.
As an intellectual activity, reading technical text is really not much different from doing research.
1. Stupidity; How come I don't understand it at all? Am I becoming stupid?
2. Anger and frustration; how come the authors leave some definitions ambiguous, and why did the referee not send the paper back to ask for another round of polishing?
3. An idea: let me just look for slides of a talk on the subject! Slides usually put much more emphasis on intuition and might help me understand what the authors meant to say.
4. Obstination; I can do it. There are no slides available, but I'm interested in the result and just need to put my mind to it. Go through examples systematically, try out the various interpretations until one fits and the proof goes through.
5. Suspicion. Is that result really correct? None of my interpretations seem to work.
6. Discouragement; I can't do it. I'll have to look up references of prior work and see which ideas are present in there and whether they are explained any better. This is turning into a major time sink.
As an intellectual activity, reading technical text is really not much different from doing research.
Friday, December 16, 2011
On applying for jobs
At this time of year, I often get contacted by potential job applicants. It is often quite difficult to gauge how interested I might be in their application, just by looking at their vita or trying to read one of their papers (and who has time to do more than that.) Arranging to meet with them is usually a big hassle for one or the other party, since they are seldom local.
What would help me would be if I saw them give a talk. For me a talk is much more informative than a paper and with much less effort. But how can that happen without the bother of traveling?
Simple: job applicants could simply videotape themselves giving their job talk, and post it on their web page.
Then I could simply download and watch their talk, and in 50 minutes I would have a good idea of their research, of how interested I am in it, and of how good they are at communicating. That would be great for me!
Why not?
What would help me would be if I saw them give a talk. For me a talk is much more informative than a paper and with much less effort. But how can that happen without the bother of traveling?
Simple: job applicants could simply videotape themselves giving their job talk, and post it on their web page.
Then I could simply download and watch their talk, and in 50 minutes I would have a good idea of their research, of how interested I am in it, and of how good they are at communicating. That would be great for me!
Why not?
Wednesday, December 14, 2011
The in-between time
I am in a transition week. The lectures of the semester are over, but final grades have not yet been calculated and turned in. I have a few days of delicious freedom to catch up with the semester's unfinished business before heading home for Christmas. It's a time to wrap things up, archive the semester's work, and assign priorities to tasks for the break.
A similar transition week happens just before the first day of classes of each semester. People plan their lectures, their travels, and organize the semester.
Transition periods are wonderful. I think that they are key to being in control of one's professional life.
When I was a professor in France, there was no clean break between semesters. The Fall semester ran well into January, and the last meetings and unresolved questions related to the Fall semester overlapped with the beginning of the Spring semester. As for the summer, one of the worst things about it was that it ended, not merely with the preparation of the Fall, but also with make-up exams for students who had failed in the Spring and who had spent the summer studying. Because of those make-up exams, there was a continuum of teaching-related tasks, with never a chance for a reboot.
Transition periods happen at all time scales. For example, google calendars offers the option of planning hour-long meetings so that they're actually 50 minutes long. That gives time for a bathroom and coffee break between meetings. Brilliant idea!
A similar transition week happens just before the first day of classes of each semester. People plan their lectures, their travels, and organize the semester.
Transition periods are wonderful. I think that they are key to being in control of one's professional life.
When I was a professor in France, there was no clean break between semesters. The Fall semester ran well into January, and the last meetings and unresolved questions related to the Fall semester overlapped with the beginning of the Spring semester. As for the summer, one of the worst things about it was that it ended, not merely with the preparation of the Fall, but also with make-up exams for students who had failed in the Spring and who had spent the summer studying. Because of those make-up exams, there was a continuum of teaching-related tasks, with never a chance for a reboot.
Transition periods happen at all time scales. For example, google calendars offers the option of planning hour-long meetings so that they're actually 50 minutes long. That gives time for a bathroom and coffee break between meetings. Brilliant idea!
Tuesday, December 13, 2011
Organizing recommendation letters
A novelty this year: I have several students who have created a google document in excel format listing the places where they have applied, how to send a recommendation letter, and a column for each letter writer to mark when they actually do send the recommendation letter.
I find it convenient. I no longer have to worry about whether I accidentally missed one of the requests. They no longer have to worry about reminding us uselessly.
In addition this gives us new data to mine: when do the various schools send their requests for recommendation letters? How prompt are my various colleagues in responding to those requests? It's all there for us to see. Of course it's not clear what to do with that interesting data. Maybe it's useless knowledge, but I like it anyway. Plus, in our race to the bottom, it's making me realize that I am not the most disorganized: I still have room to spare!
I find it convenient. I no longer have to worry about whether I accidentally missed one of the requests. They no longer have to worry about reminding us uselessly.
In addition this gives us new data to mine: when do the various schools send their requests for recommendation letters? How prompt are my various colleagues in responding to those requests? It's all there for us to see. Of course it's not clear what to do with that interesting data. Maybe it's useless knowledge, but I like it anyway. Plus, in our race to the bottom, it's making me realize that I am not the most disorganized: I still have room to spare!
Monday, December 12, 2011
On naming files
Last week I renamed my files containing the slides of my lectures for this past semester. I had started the semester by naming them: "lecture1", "lecture2", "lecture3", etc. At some point I lost track, and started using dates instead: "october25", "october28", etc. Now I wanted to given them a name that would be helpful, should I look them up again in the future.
Should I call them by their number - lecture1 through lecture35? Not so good, because I may want on some future day to look up the lecture about, say, quick sort, and with that labeling I have no easy way to know where those slides are.
Should I call them by their topic - "Ocamlpatternmatching", "quick sort", etc.? Not so good, because there is a logical order that is lost when I do that.
Should I call them by a combination - "15_higherorderprocedures", "25_runtimeanalysis", etc.? Pretty good, except for one minor flaw: when I list the files in the directory, they do not appear in the correct order: 12blabla precedes 2blabla.
So I ended up calling them by a combination, by started the numbering at 100: "115_higherorderprocedures", "125_runtimeanalysis", etc.
The result looks pretty good. It only took me 25 years of professional experience to figure that out. How come no one has ever taught me how to organize my files? Did I miss a class on "remedial organization" at some point?
Should I call them by their number - lecture1 through lecture35? Not so good, because I may want on some future day to look up the lecture about, say, quick sort, and with that labeling I have no easy way to know where those slides are.
Should I call them by their topic - "Ocamlpatternmatching", "quick sort", etc.? Not so good, because there is a logical order that is lost when I do that.
Should I call them by a combination - "15_higherorderprocedures", "25_runtimeanalysis", etc.? Pretty good, except for one minor flaw: when I list the files in the directory, they do not appear in the correct order: 12blabla precedes 2blabla.
So I ended up calling them by a combination, by started the numbering at 100: "115_higherorderprocedures", "125_runtimeanalysis", etc.
The result looks pretty good. It only took me 25 years of professional experience to figure that out. How come no one has ever taught me how to organize my files? Did I miss a class on "remedial organization" at some point?
Sunday, December 11, 2011
Outdegree, contractions, planar graphs
You can always direct the edges of a planar graph so that every vertex has outdegree at most 5. That fact is clear to anyone who has taken a discrete math course at one point in their life.
My question is:
Q: What happens if the edges of the graph get contracted one by one?
A: Then the outdegree risks growing. For example, if one contracts two adjacent vertices that each have outdegree 5, the resulting vertex will then have outdegree 5+5-1=9. The next contraction may bring its degree up to 9+5-1=13, then 17, etc.
My question then is:
Q: Is it possible to efficiently modify the orientation of some edges along the way and prevent the outdegree from blowing up?
A: Yup. Here's the algorithm, appealingly simple and natural. After each contraction, do the following: while there exists a vertex v of outdegree greater than 10, reverse the orientation of every outgoing edge of v.
At this point your question surely is or should be:
Q (Toto): Cute, maybe, if that's your taste, but why do you care?
A: Because it is used in an upcoming SODA paper by David Eisenstat, Philip Klein and myself, to reduce the runtime of a primal-dual region-growing phase.
Now that the motivation is out of the way, we can think about it together.
Q (Toto): Ok, I'm willing to temporarily accept that this might be interesting. Then, why does this algorithm work and how efficient is it?
A: By design, it obviously maintains an orientation in which each vertex has outdegree no more than 10. The neat observation is that it is an efficient algorithm: the total number of reversals, and hence the runtime (assuming you don't mess up the low-level implementation details), is O(n log n).
Q (Toto): Why is the total number of reversals O(n log n)? I don't see it.
A: The proof is magic.
Q (Toto): I don't like magic.
A: The magic would disappear if you did a few examples of amortized analysis, but for a single analysis of a single problem, you have to accept the magic. Let G(i) be the graph after i contractions. We consider two orientations of the edges of G(i): Alg(G(i)), the orientation obtained by executing the algorithm, and a certain orientation Ideal(G(i)) such that the maximum outdegree in Ideal(G(i)) is at most 5. To start the proof, magically define the potential of G(i) to be
Potential(G(i))= distance(Alg(G(i),Ideal(G(i))), that is, the number of edges that are oriented differently in the two orientations.
Now, here's my question.
Q: What happens to the potential when the algorithm reverses all the outgoing edges of a vertex v?
A: That's not hard to see. Let S denote that group of edges. Immediately before the reversal of S, in Alg the outdegree of v is |S|>=11, and in Ideal the outdegree is <=5, so S contributes at least |S|-5 to the distance; immediately after the reversal of S, S contributes at most 5 to the distance. So the reversal of S has caused the distance to decrease by at least (|S|-5-5)>=1. Overall the total number of edge reversals is within a constant factor of (sum of decreases in the potential function): instead of analyzing the number of edge reversals, we can just analyze the number of decreases of the potential function.
Q (Toto): Big deal. It's not clear to me that you have made any progress: how do you analyze the number of decreases of the potential function?
A: Let's see. Since the potential function is always non-negative, each decrease must be compensated by some previous increase (or by the initial value). So, the total number of decreases is at most the initial value of the potential (which is O(n)), plus the increases that may happen when going from Ideal(G(i)) to Ideal(G(i+1)).
Q (Toto): But you haven't even told me what that "certain orientation Ideal(G(i))" was! I am frustrated.
A: Patience! It is now time to define Ideal(G(i)). Let's do it in backwards order.
Q (Toto): Why? I am frustrated.
A: Because that's what works. Be quiet! Start from the final graph, give it an orientation such that the maximum outdegree is 5, and "uncontract" the edges one by one. To define Ideal(G(i)) from Ideal(G(i+1)), do the following. After the uncontraction of edge uv, in the orientation of G(i) that is inherited from G(i+1), vertex u and vertex v each have outdegree at most 5, and edge uv needs to be given an orientation: arbitrarily direct it from u to v; if u now has degree 6, find a shortest path p (in the directed graph) from u to a vertex with outdegree less than or equal to 4, and reverse the orientation of every edge on p. Now the outdegree of u is reduced to 5. That defines Ideal(G(i)).
Q (Toto): I'm tired. Are we there yet?
A: To finish the proof, it only remains to observe that p has length O(log n).
Q (Toto): Why does p have length O(log n)? Oh, whatever.
A: Easy. Do breadth first search from u. How can it be that all vertices in the first i levels have degree >=5? From Euler's formula for planar graphs, it is easy to see (it's an exercise) that it can only happen if the growth rate is exponential, and such a growth rate can only be maintained for O(log n) levels.
Q (Toto): If you say so. Whatever.
A: Hang on! We're done, just about: So p has length O(log n), so Ideal(G(i)) differs from Ideal(G(i+1)) in O(log n) edges, so the potential can only increase by O(log n) at each contraction, so it can only increase by O(n log n) overall, so it can only decrease by O(initial value + n log n), so the total number of edges reversals is O(n + n log n)=O(n log n) overall, so the algorithm is efficient. I'm done.
My last question:
Q: Isn't it elegant, simple, and clever?
A (Toto): I guess so. You certainly seem excited about it.
Your final question is:
Q (Toto): How do you know all that stuff?
A: The basic technique is from Brodal and Fagerberg, "Dynamic Representations of Sparse Graphs." The application to contractions is from Kowalik, "Fast 3-coloring triangle-free planar graphs". It's also explained in an upcoming textbook by Philip Klein.
My question is:
Q: What happens if the edges of the graph get contracted one by one?
A: Then the outdegree risks growing. For example, if one contracts two adjacent vertices that each have outdegree 5, the resulting vertex will then have outdegree 5+5-1=9. The next contraction may bring its degree up to 9+5-1=13, then 17, etc.
My question then is:
Q: Is it possible to efficiently modify the orientation of some edges along the way and prevent the outdegree from blowing up?
A: Yup. Here's the algorithm, appealingly simple and natural. After each contraction, do the following: while there exists a vertex v of outdegree greater than 10, reverse the orientation of every outgoing edge of v.
At this point your question surely is or should be:
Q (Toto): Cute, maybe, if that's your taste, but why do you care?
A: Because it is used in an upcoming SODA paper by David Eisenstat, Philip Klein and myself, to reduce the runtime of a primal-dual region-growing phase.
Now that the motivation is out of the way, we can think about it together.
Q (Toto): Ok, I'm willing to temporarily accept that this might be interesting. Then, why does this algorithm work and how efficient is it?
A: By design, it obviously maintains an orientation in which each vertex has outdegree no more than 10. The neat observation is that it is an efficient algorithm: the total number of reversals, and hence the runtime (assuming you don't mess up the low-level implementation details), is O(n log n).
Q (Toto): Why is the total number of reversals O(n log n)? I don't see it.
A: The proof is magic.
Q (Toto): I don't like magic.
A: The magic would disappear if you did a few examples of amortized analysis, but for a single analysis of a single problem, you have to accept the magic. Let G(i) be the graph after i contractions. We consider two orientations of the edges of G(i): Alg(G(i)), the orientation obtained by executing the algorithm, and a certain orientation Ideal(G(i)) such that the maximum outdegree in Ideal(G(i)) is at most 5. To start the proof, magically define the potential of G(i) to be
Now, here's my question.
Q: What happens to the potential when the algorithm reverses all the outgoing edges of a vertex v?
A: That's not hard to see. Let S denote that group of edges. Immediately before the reversal of S, in Alg the outdegree of v is |S|>=11, and in Ideal the outdegree is <=5, so S contributes at least |S|-5 to the distance; immediately after the reversal of S, S contributes at most 5 to the distance. So the reversal of S has caused the distance to decrease by at least (|S|-5-5)>=1. Overall the total number of edge reversals is within a constant factor of (sum of decreases in the potential function): instead of analyzing the number of edge reversals, we can just analyze the number of decreases of the potential function.
Q (Toto): Big deal. It's not clear to me that you have made any progress: how do you analyze the number of decreases of the potential function?
A: Let's see. Since the potential function is always non-negative, each decrease must be compensated by some previous increase (or by the initial value). So, the total number of decreases is at most the initial value of the potential (which is O(n)), plus the increases that may happen when going from Ideal(G(i)) to Ideal(G(i+1)).
Q (Toto): But you haven't even told me what that "certain orientation Ideal(G(i))" was! I am frustrated.
A: Patience! It is now time to define Ideal(G(i)). Let's do it in backwards order.
Q (Toto): Why? I am frustrated.
A: Because that's what works. Be quiet! Start from the final graph, give it an orientation such that the maximum outdegree is 5, and "uncontract" the edges one by one. To define Ideal(G(i)) from Ideal(G(i+1)), do the following. After the uncontraction of edge uv, in the orientation of G(i) that is inherited from G(i+1), vertex u and vertex v each have outdegree at most 5, and edge uv needs to be given an orientation: arbitrarily direct it from u to v; if u now has degree 6, find a shortest path p (in the directed graph) from u to a vertex with outdegree less than or equal to 4, and reverse the orientation of every edge on p. Now the outdegree of u is reduced to 5. That defines Ideal(G(i)).
Q (Toto): I'm tired. Are we there yet?
A: To finish the proof, it only remains to observe that p has length O(log n).
Q (Toto): Why does p have length O(log n)? Oh, whatever.
A: Easy. Do breadth first search from u. How can it be that all vertices in the first i levels have degree >=5? From Euler's formula for planar graphs, it is easy to see (it's an exercise) that it can only happen if the growth rate is exponential, and such a growth rate can only be maintained for O(log n) levels.
Q (Toto): If you say so. Whatever.
A: Hang on! We're done, just about: So p has length O(log n), so Ideal(G(i)) differs from Ideal(G(i+1)) in O(log n) edges, so the potential can only increase by O(log n) at each contraction, so it can only increase by O(n log n) overall, so it can only decrease by O(initial value + n log n), so the total number of edges reversals is O(n + n log n)=O(n log n) overall, so the algorithm is efficient. I'm done.
My last question:
Q: Isn't it elegant, simple, and clever?
A (Toto): I guess so. You certainly seem excited about it.
Your final question is:
Q (Toto): How do you know all that stuff?
A: The basic technique is from Brodal and Fagerberg, "Dynamic Representations of Sparse Graphs." The application to contractions is from Kowalik, "Fast 3-coloring triangle-free planar graphs". It's also explained in an upcoming textbook by Philip Klein.
Saturday, December 10, 2011
Ruth Simmons on interviewing and hiring
Ruth Simmons, our beloved president here at Brown university, has some advice about interviewing.
I look for people who are supremely self-confident, very secure, but also profoundly interested in other people. [...] How curious are they about other people, and about new things outside their own area of specialization? [...]
I keep going back to this fundamental idea of being able to respect other people, especially if you’re in a senior position. You can get a lot more done if people have a sense that you respect them, and that you listen to them. You would be surprised at the number of interviews I’ve done where the person never stops talking. If I’m interviewing someone and if they never stop talking, I will never hire them, no matter how qualified they are. If you cannot listen, you can’t be the site of welcoming, nurturing, facilitating new ideas, innovation, creativity, because it really is ultimately only about you. So I look for people who listen well and can respect the ideas of others.
I look for people who are strong enough to be critical of things that are not very good. And more than being critical of things that are not very good, they have to have the capacity to tell people that. [...].
(From the NYT)
I look for people who are supremely self-confident, very secure, but also profoundly interested in other people. [...] How curious are they about other people, and about new things outside their own area of specialization? [...]
I keep going back to this fundamental idea of being able to respect other people, especially if you’re in a senior position. You can get a lot more done if people have a sense that you respect them, and that you listen to them. You would be surprised at the number of interviews I’ve done where the person never stops talking. If I’m interviewing someone and if they never stop talking, I will never hire them, no matter how qualified they are. If you cannot listen, you can’t be the site of welcoming, nurturing, facilitating new ideas, innovation, creativity, because it really is ultimately only about you. So I look for people who listen well and can respect the ideas of others.
I look for people who are strong enough to be critical of things that are not very good. And more than being critical of things that are not very good, they have to have the capacity to tell people that. [...].
(From the NYT)
Friday, December 9, 2011
ITCS: some innovations
Today I looked at the ITCS web page, to register (even though I'll miss the first day), and, lo and behold! They're going to have some innovations!
People looking for jobs (graduating students and postdocs completing their postdoc this year) will each be given a few minutes to present their work. They are asked to send email before December 15. I am looking forward to that event, to get a quick snapshot of our field, as represented by the most recent PhD theses.
Each session will be preceded by a short "chair rant". I am very curious to see how that will turn out. It all depends on the personality of the session chairs, of course. Will it be a waste of time, will it provide some actual insights into the papers, will it be fun? It is intriguing.
There's also going to be improvisational theater. I am more dubious about that and will probably simply sit in the back; it doesn't seem like my thing. But de gustibus non est disputandum.
People looking for jobs (graduating students and postdocs completing their postdoc this year) will each be given a few minutes to present their work. They are asked to send email before December 15. I am looking forward to that event, to get a quick snapshot of our field, as represented by the most recent PhD theses.
Each session will be preceded by a short "chair rant". I am very curious to see how that will turn out. It all depends on the personality of the session chairs, of course. Will it be a waste of time, will it provide some actual insights into the papers, will it be fun? It is intriguing.
There's also going to be improvisational theater. I am more dubious about that and will probably simply sit in the back; it doesn't seem like my thing. But de gustibus non est disputandum.
Thursday, December 8, 2011
Things about my work that I enjoy
I enjoy interacting with students.
I enjoy helping someone learn something new.
I enjoy learning something new.
I enjoy discovering something new.
I enjoy understanding something new.
I enjoy teaching a well-prepared lecture.
I enjoy seeing students become researchers.
I enjoy good writing.
I enjoy writing well (but it takes lots of effort).
I enjoy having an idea.
I enjoy discussing research.
I enjoy brainstorming.
I enjoy going to Israel.
I enjoy hearing Hebrew.
I enjoy people laughing at my jokes.
I enjoy compliments.
I enjoy the feeling of work well done (but that's rare).
I enjoy having caught up with email (but that's rare).
I enjoy exploring Dagstuhl.
I enjoy sunsets in Bertinoro.
I enjoy Ivy League architecture.
I enjoy wood-paneled classrooms.
I enjoy the smell of white board pens.
I enjoy hiking with colleagues.
I enjoy meeting academics who are not scientists.
I enjoy free coffee.
I enjoy the view from my office.
I enjoy the money and status.
I enjoy the freedom to define my work.
I enjoy the freedom to, occasionally, wake up without an alarm and go to work when I feel like it.
I enjoy being part of a field that is changing the world.
I enjoy having a paper accepted.
I enjoy helping someone learn something new.
I enjoy learning something new.
I enjoy discovering something new.
I enjoy understanding something new.
I enjoy teaching a well-prepared lecture.
I enjoy seeing students become researchers.
I enjoy good writing.
I enjoy writing well (but it takes lots of effort).
I enjoy having an idea.
I enjoy discussing research.
I enjoy brainstorming.
I enjoy going to Israel.
I enjoy hearing Hebrew.
I enjoy people laughing at my jokes.
I enjoy compliments.
I enjoy the feeling of work well done (but that's rare).
I enjoy having caught up with email (but that's rare).
I enjoy exploring Dagstuhl.
I enjoy sunsets in Bertinoro.
I enjoy Ivy League architecture.
I enjoy wood-paneled classrooms.
I enjoy the smell of white board pens.
I enjoy hiking with colleagues.
I enjoy meeting academics who are not scientists.
I enjoy free coffee.
I enjoy the view from my office.
I enjoy the money and status.
I enjoy the freedom to define my work.
I enjoy the freedom to, occasionally, wake up without an alarm and go to work when I feel like it.
I enjoy being part of a field that is changing the world.
I enjoy having a paper accepted.
Wednesday, December 7, 2011
Things about my work that I don't enjoy
I don't enjoy faculty meetings.
I don't enjoy giving final grades.
I don't enjoy failing students.
I don't enjoy reporting suspected cases of cheating.
I don't enjoy setting up my laptop for class.
I don't enjoy refereeing.
I don't enjoy being an editor.
I don't enjoy writing recommendation letters.
I don't enjoy revising papers.
I don't enjoy flying.
I don't enjoy chain hotels.
I don't enjoy committees.
I don't enjoy being hopelessly stuck on a research problem.
I don't enjoy failure.
I don't enjoy being stuck on some notation as I read a paper.
I don't enjoy being behind in my work.
I don't enjoy not doing what I'm supposed to be doing.
I don't enjoy working in the evening.
I don't enjoy most seminars.
I don't enjoy email.
I don't enjoy criticism.
I don't enjoy the lack of tangible impact of my work.
I don't enjoy working indoors.
I don't enjoy writing introductions.
I don't enjoy having a paper rejected.
I don't enjoy deadlines.
I don't enjoy having my research community scattered around the world.
I don't enjoy decisions by consensus.
I don't enjoy giving final grades.
I don't enjoy failing students.
I don't enjoy reporting suspected cases of cheating.
I don't enjoy setting up my laptop for class.
I don't enjoy refereeing.
I don't enjoy being an editor.
I don't enjoy writing recommendation letters.
I don't enjoy revising papers.
I don't enjoy flying.
I don't enjoy chain hotels.
I don't enjoy committees.
I don't enjoy being hopelessly stuck on a research problem.
I don't enjoy failure.
I don't enjoy being stuck on some notation as I read a paper.
I don't enjoy being behind in my work.
I don't enjoy not doing what I'm supposed to be doing.
I don't enjoy working in the evening.
I don't enjoy most seminars.
I don't enjoy email.
I don't enjoy criticism.
I don't enjoy the lack of tangible impact of my work.
I don't enjoy working indoors.
I don't enjoy writing introductions.
I don't enjoy having a paper rejected.
I don't enjoy deadlines.
I don't enjoy having my research community scattered around the world.
I don't enjoy decisions by consensus.
Tuesday, December 6, 2011
Only one lecture left!
One more lecture, and I am free!
Much as I enjoy teaching, the end of the semester is always a relief.
Much as I enjoy hiking, arriving at the refuge is always a relief.
Much as I enjoy family reunions, I am always relieved when they end.
Everything that takes effort and concentration is always, to some degree, a relief to get over with, even if it is gratifying.
Much as I enjoy living, when death comes near, will I be relieved to welcome it?
Much as I enjoy teaching, the end of the semester is always a relief.
Much as I enjoy hiking, arriving at the refuge is always a relief.
Much as I enjoy family reunions, I am always relieved when they end.
Everything that takes effort and concentration is always, to some degree, a relief to get over with, even if it is gratifying.
Much as I enjoy living, when death comes near, will I be relieved to welcome it?
Monday, December 5, 2011
A good deed
The other day, I was starting my car just as the light turned green, when a car honked behind me. Surprised, I thought: "this driver is really impatient!" Then he passed me to my right, and I got annoyed.
So, at the next red light, instead of sitting patiently behind him, I changed lanes and, with my car lined up next to his, I waited in high alert. When the light turned green, I took advantage of my stick shift to start the car sharply. Vroom!
The other driver reacted by speeding up, passed me and positioned himself in front of me, his car squarely straddling the center line in such a way that I would not be able to pass him on either side. I had to laugh!
By giving that stranger a chance to compete and win, I probably made his day. He must have felt really good about himself, all thanks to me!
And that was my good deed for the day.
So, at the next red light, instead of sitting patiently behind him, I changed lanes and, with my car lined up next to his, I waited in high alert. When the light turned green, I took advantage of my stick shift to start the car sharply. Vroom!
The other driver reacted by speeding up, passed me and positioned himself in front of me, his car squarely straddling the center line in such a way that I would not be able to pass him on either side. I had to laugh!
By giving that stranger a chance to compete and win, I probably made his day. He must have felt really good about himself, all thanks to me!
And that was my good deed for the day.
Sunday, December 4, 2011
Yao and Preparata on US higher education
Andy Yao and Franco Preparata sat on a panel at Brown about globalization. Andy Yao said that the US system of higher education was the best in the world, for the following reasons.
- Indirect evidence from the results. US institutions of higher learning train the best scientists and the best engineers, he said. I would say that it is an indicator of the quality of the PhD and Masters programs, but not necessarily of the undergraduate programs.
- Merit-based decisions for admitting students, hiring faculty, and promotion to tenure. Andy Yao specifically praised the tenure-track system, that, by putting new hires on probation for 6 years, prevents hiring mistakes from having life-long consequences. As someone who has greatly benefited from the French tenured-upon-hiring system, as a friend of women who have avoided the stressful tenure-track phase by spending the early part of their career in industry labs, and as a witness of women who wait until tenure before having children (at 35, the age when fertility starts to decrease significantly and the risk of genetic defects in babies rises), I see the great personal cost of the tenure-track system and am reluctant to consider its advantages.
- Franco Preparata added the 9-month salary system: US universities only pay faculty for work 9 months of the year. That gives professors both freedom and incentive to go elsewhere for the remaining three months: visit another university or industry lab. The arrangement promotes the exchange of ideas and cross-fertilization between different places.
- Indirect evidence from the results. US institutions of higher learning train the best scientists and the best engineers, he said. I would say that it is an indicator of the quality of the PhD and Masters programs, but not necessarily of the undergraduate programs.
- Merit-based decisions for admitting students, hiring faculty, and promotion to tenure. Andy Yao specifically praised the tenure-track system, that, by putting new hires on probation for 6 years, prevents hiring mistakes from having life-long consequences. As someone who has greatly benefited from the French tenured-upon-hiring system, as a friend of women who have avoided the stressful tenure-track phase by spending the early part of their career in industry labs, and as a witness of women who wait until tenure before having children (at 35, the age when fertility starts to decrease significantly and the risk of genetic defects in babies rises), I see the great personal cost of the tenure-track system and am reluctant to consider its advantages.
- Franco Preparata added the 9-month salary system: US universities only pay faculty for work 9 months of the year. That gives professors both freedom and incentive to go elsewhere for the remaining three months: visit another university or industry lab. The arrangement promotes the exchange of ideas and cross-fertilization between different places.
Saturday, December 3, 2011
Andy Yao: the atom whisperer
Andy Yao visited Brown this week.
He gave a talk about quantum computing, ending with a slide on "What makes great science". His answer was poetic; he apologized for being a romantic, then said: we are learning the language of atoms. Once we understand their language, we will whisper a computational problem into their ear (?), and watch them do an elegant dance to perform the computation. After a few minutes the answer will appear.
He gave a talk about quantum computing, ending with a slide on "What makes great science". His answer was poetic; he apologized for being a romantic, then said: we are learning the language of atoms. Once we understand their language, we will whisper a computational problem into their ear (?), and watch them do an elegant dance to perform the computation. After a few minutes the answer will appear.
Friday, December 2, 2011
Quarter or semester?
What's the difference in workload between the semester and the quarter systems?
Universities that follow a semester-based calendar usually have 12 to 15 weeks of lecturing during the semester, for a total of 24 to 30 weeks per year; let's say 27 weeks, just for definiteness. Universities that follow a quarter-based calendar have about 10 weeks of lecturing in the quarter, I think, for a total of about 30 weeks per year. That's 3 more weeks of teaching.
In addition, a good part of the work teaching a course is in the initial setup and in the final wrapping-up. The week before the semester or quarter starts is usually occupied by various routine teaching-related tasks, and, after the course ends, it takes about two weeks before the final exam is done, graded, and final course grades are turned in: that's an additional 3 weeks per semester/quarter, so those who are using the quarter system have an extra 3 weeks of that stuff during the year.
3 more weeks of teaching and 3 more weeks of "stuff": that's an additional 6 weeks spent on teaching-related activities - 39 weeks per year instead of 33. For professors, going from the semester to the quarter system is an 18 percent increase in teaching load.
Universities that follow a semester-based calendar usually have 12 to 15 weeks of lecturing during the semester, for a total of 24 to 30 weeks per year; let's say 27 weeks, just for definiteness. Universities that follow a quarter-based calendar have about 10 weeks of lecturing in the quarter, I think, for a total of about 30 weeks per year. That's 3 more weeks of teaching.
In addition, a good part of the work teaching a course is in the initial setup and in the final wrapping-up. The week before the semester or quarter starts is usually occupied by various routine teaching-related tasks, and, after the course ends, it takes about two weeks before the final exam is done, graded, and final course grades are turned in: that's an additional 3 weeks per semester/quarter, so those who are using the quarter system have an extra 3 weeks of that stuff during the year.
3 more weeks of teaching and 3 more weeks of "stuff": that's an additional 6 weeks spent on teaching-related activities - 39 weeks per year instead of 33. For professors, going from the semester to the quarter system is an 18 percent increase in teaching load.
Thursday, December 1, 2011
The great pendulum
Professors don't think in terms of calendar years but of academic years. The school year is partitioned into four great periods, corresponding to the two semesters and the long breaks between semesters.
During the breaks, we are primarily focused on our research.
During the semester, many of us are primarily focused on our teaching. To prevent excesses in that regard, if may be good to plan a trip to a conference some time during the semester: that is one purpose served by conferences, that neither Arxiv nor journals can be a substitute for.
So, every three months or so, the great pendulum of our work-life swings from teaching to research and from research back to teaching.
During the breaks, we are primarily focused on our research.
During the semester, many of us are primarily focused on our teaching. To prevent excesses in that regard, if may be good to plan a trip to a conference some time during the semester: that is one purpose served by conferences, that neither Arxiv nor journals can be a substitute for.
So, every three months or so, the great pendulum of our work-life swings from teaching to research and from research back to teaching.
Subscribe to:
Posts (Atom)