Samstag, Februar 28, 2015

Interesting mistakes

I taught a course in Linear and Integer Optimization last semester, the exam of which was held last week. I'm fairly pleased with the results. Grading an exam is often painful when you realize that some students failed to understand important concepts, but overall it appears that my expectations about the difficulty of this exam were mostly accurate. Sometimes, however, students fail at a problem for reasons that we do not anticipate. One problem of the exam was to prove that when P and Q are (convex) polytopes, then so is their Minkowski sum P + Q.

I am aware of two reasonable approaches to this problem. The first is to use inequality representations to argue that the product P x Q is a polyhedron, and then appeal to the fact (shown in the lecture) that the image under the linear map (p, q) -> p + q is a polyhedron (boundedness is of course easy to see, and naturally there are some variations of this approach). The second approach is to use representations of P and Q as convex hulls of finitely many points, and to show that P + Q is the convex hull of the pairwise sum of such points. This second proof is elementary but requires a bit more work because one has to argue about the coefficients in convex combinations.

To my surprise, several students attempted a third route. They started with inequality representations and used the boundedness to argue that given one of the inequalities ax <= b that define P, the maximum of ax over Q is finite. They then tried to prove that P + Q can be obtained by simply using both the inequalities defining P and those defining Q together, with the right-hand sides increased by the corresponding (finite) maximum over the other polytope. This approach cannot possibly work because the number of facets of the Minkowski sum can be exponentially larger than the number of facets of the summands (the permutahedron is a cute example of this). And yet, in hindsight, it is a very plausible approach to try if one doesn't know about this fact.

As mistakes go, I would call this an interesting mistake. In some sense it isn't even a mistake at all, just a false trail into the woods that unfortunately some students got lost in.

Freitag, Februar 20, 2015

Katharsis durch geschriebene und nicht abgeschickte Kommentare

Das ist schon fast jedem passiert: Man liest den Online-Kommentar irgendeines unbekannten Fremden, den man für furchtbaren Unfug hält. Unbedingt muss man ihn oder sie verbessern! So füllen sich die Kommentar-Bereiche von Blogs, und es werden Monster wie die Foren von Spiegel Online geschaffen.
Ich schließe mich da nicht aus. Auf Blogs, die ich regelmäßig lese, treibt sich die ein oder andere dort schon gut bekannte Person herum, mit der ich überhaupt nicht auf einen Nenner komme. Unsere größte Gemeinsamkeit, zumindest der ausgetauschten Kommentare nach zu urteilen, ist, dass wir zu viel Zeit auf Blogs verbringen.

Am besten wäre es, das alles zu ignorieren. Manchmal geht das auch, aber immer wieder kommt es vor, dass ein Kommentar an mir nagt, wenn mal wieder jemand etwas (für mich...) Offensichtliches nicht verstanden hat oder - und das ist oft wahrscheinlicher - nicht verstehen will. Dann ertappe ich mich dabei, zumindest einen kurzen Kommentar zu schreiben, der eine nutzlose Diskussion nur noch weiter verlängert. Es tut gut, in einer solchen Situation inne zu halten, kurz die Augen zu schließen, und den begonnenen Kommentar einfach wieder zu löschen, bevor er meinen Computer verlässt.

Danach fühle ich mich gut - und obwohl der Kommentar letztlich nicht abgeschickt wurde ist das nagende Gefühl, das ein gänzlich unbeantworteter Kommentar ausgelöst hat, verschwunden. Gleichzeitig ist die Diskussion beendet, so dass Zeit und zukünftige nagende Gefühle gespart werden.

Meistens ist das die beste Lösung. Es ist ziemlich irrational und unlogisch, aber so ist die Psyche nun mal. Ich kann die Strategie daher nur weiterempfehlen.

Sonntag, Februar 15, 2015

In der Schweiz Erwähnenswertes

Als ich letztes Wochenende aus Oberwolfach zurück gefahren bin, musste ich mit ein paar Kollegen in Offenburg auf den Anschlusszug warten. Dort hatte die Bahn einen Aushang, auf dem Sonderzüge zu einem sogenannten "Basler Morgestraich" angekündigt wurden.

Neugierig und mit intelligenten Telefonen bewaffnet haben wir also den Wikipedia-Artikel gelesen, den ich für die geneigte Leserin hier nicht kopieren muss. Aber wir haben doch gestutzt, dass der Bericht über die falsch gestellte Uhr, wegen der der Morgestraich im Jahr 2002 eine Minute zu früh gestartet ist, fast 10% des Artikels ausmacht. Was manche Menschen eben so bewegt...

Freitag, Februar 13, 2015

The tone of Linus Torvalds

Linus Torvalds is known for verbally ruffling feathers. I was reminded of this once more when a thread about a workaround for a bug in rarely used graphics cards caught my eye.

There's no disagreement going on - unlike in the more famous examples of Linus Torvalds ripping into a person who he disagrees with (usually rightfully, and on solid technical grounds). And yet, pay attention to Dave Airlie's emails. From my past involvement in Mesa3D for the Radeon drivers, I know Dave a little bit, as a kind and friendly person. After the mail of Linus Torvalds, his tone changes significantly, using "crap" twice in a very gratuitous way.

The situation here isn't hostile at all, and yet the language becomes hostile after the supreme alpha geek enters the ring and the others begin to ape his style.

Of course, Linus Torvalds regularly defends this style by saying that it ensures that his message really gets through instead of being dampened by layers of friendly fluff, which he considers to be noise that distracts from the signal. There's truth in that. And yet, here we have evidence that the tone of discussion becomes unwelcoming even when all of the participants are on the same page. This is bound to create an unnecessary rise in serotonin levels at least in some people, which is bound to cause losses to the project.

So is this style really necessary to successfully run a large scale open source project? The answer appears to be No, given how many other projects exist, and how few of them create the kind of noise about their internal conduct as the Linux kernel does.

I do find it interesting to observe that there is possibly no other person in a comparable situation to Linus Torvalds, simply by virtue of how the development of the Linux kernel is structured. Even though he has delegated most of the work, all changes to the Linux kernel eventually must pass through him, as he is the only person who can change the project's master branch. Compare this to other large open source projects, all of which (to my knowledge) allow their master branch to be written to by a group of core developers. It seems to me that there is a curious feedback loop going on between Linus Torvalds' character and the environment he operates in.