## Archive for the ‘Personal’ Category

### The Weight of Uncertainty

Tuesday, July 24th, 2012

The Weight of Uncertainty is an artwork by the artists Guillermo Faivovich and Nicolás Goldberg at documenta (13), substituting a meteorite. While the iron mass was placed outside at the Friedrichsplatz, the label for the artwork was “hidden” inside the Fridericianum, a nearby museum. Hence I had the pleasure to inform a person that she is sitting on an artwork. Knowing that it weighs more than 3.5 t and is not just a cupped box she felt much safer.

When arriving at The Weight of Uncertainty together with a guide people behave like that.

But some people behave like that.

Somebody else proposed the following concept for an artwork: Materials: Some comfortable benches, trees, an unconspicuous, but eager person. The person couwers behind the trees blaming everybody for sitting on the benches while wearing the label for the artwork. Wouldn’t that be nice?

### Proseminar: Computing Maximal Independent Sets an a PRAM

Sunday, February 26th, 2012

Last year I had a proseminar at university and I do not want the stuff to moulder on my hard drive. It was about randomised algorithms and I had to write about ways to compute maximal independent sets in parallel. The considerations are primarily theoretically, proving runtime complexities on abstract parallel machines—we do not have a problem with using polynomially many cores for a trivial task (we simply have to choose anything that fits) which would in practice be more difficult to distribute to the nodes than computing it sequentially—but it might be interesting to see how randomisation can guarantee uncoupling between different processes resulting in a better runtime complexity, I enjoyed it. What is a maximal independent set? Given a graph it is a subset of the vertices of the graph being both independent and dominating, no two of its members are adjacent, but every other vertex is adjacent to a member of the set—not to be confused with maximum independent sets being maximal independent sets of maximal cardinality, computing maximum independent sets is NP hard. If anybody is interested in a German explanation of randomised parallel computation of maximal independent sets not requiring specific knowledge about the theory parallel or randomised algorithms, here you go (slides).

### Back from NWERC 2011

Monday, November 28th, 2011

Hi folks!

This weekend I participated at the North Western European Regional Contest, a regional preliminary round for the ACM ICPC. It is an international students contest about solving as many as possible out of 10 algorithmic problems in 5 hours in teams of three students and one PC. It was my first time there and it was quite fun.

At saturday we visited the historic harbour of Bremen Vegesack, which was partly boring and partly quite nice. At sunday there was the actual contest at the quite decadent and walled Campus of Jacobs University in Bremen (you even have to pay tuition of ~€25000, ~$33000 per year, at public universities you pay about €400-1400, I could live from it for long time, but even at elitist economical universities like EBS and WHU you have to pay much less). We used KDevelop 4.2 for solving the tasks and enjoyed the nice completion, source code reformatting (nice when you are not sure any longer which braces belong together and do not have much time :)), and inline documentation of STL functions. Thank you, KDevelop guys. Our team from RWTH solved only three out of 10 tasks (30st place out of 70). B and E were quite trivial (I did not even had to read B since my team members solved it). I want to tell a bit about the other problems, I hope it is interesting for some of you. Of course you may try to solve the problems your self, it is quite a lot of fun. ### A Given a natural number x<10^15 we should compute all n,k such that binomial(n,k)=x. It was quite simple, but we had a bug in our implementation and I do not have any clue what the problem was. We chose to check the cases binomial(n,1)=n and binomial(n,2)=n·(n-1)/2 manually and brute force the solution for all other cases by computing lines of Pascal’s triangle for k values such that binomial(n,k)≤x and terminating when binomial(n,2)>x. Alternatively you could check more terms explicitly (the team from LMU did it) and compute the whole triangle for the remaining values or use binary search to find the parameters. ### C Given a sequence of films watched by a person we should answer for each time position how many different films have been watched since the last time he watched the current one. By maintaining a binary tree containing the films ordered by the last time they were watched and a map containing this time for each movie this queries can be easily answered to if you have a way to get the number of nodes after a specific one in the tree in O(log n). That for you would have to store the size of each subtree and STL set/map unfortunately do not support this. Thus we decided to write our own tree, we went for a Treap with random priorities since it is the easiest way to avoid degeneration (easier to implement than AVL and Red-Black trees). Unfortunately we did not have enough time for debugging the tree and we even forgot to update the counters when balancing the tree after insertion. There were simplier solutions using segment trees. For this task there were particularly many wrong submissions (the man presenting the solutions assumed that many teams tried to solve this one because the first team solved it yet after 20 minutes and thought it would be the easiest one, he even presented a very funny solution using java.lang.String. a linear time Java indexOf() call, which was of course way too slow). ### D This task was about deciding whether it is possible to partition a given pattern of black and white square into disjoint, L-shaped “puzzle pieces” of one black (in the corner) and two white squares. We had no idea how to solve that, we thought a lot about backtracking, but there semt to be no clever way to do that in polynomial time. The trick was to encode this problem in Boolean formulas and to use a standard algorithm (e.g. resolution) for the 2-SAT problem using variables encoding “white square x,y belongs to the same puzzle piece as the white square x+1,y+1“ etc. ### F Nobody solved this problem at the contest (though there were some people at the semi-live contest at Spoj solving it, a coach of another team said he knew a very similiar task from a different contest). Look at it, it looks like really complicated spam. Only one team tried. Cool geometric structures, quad-trees etc. will not help you to solve this problem: 500×500 fields, each one is either water or grass. You want to build a pool area. The border has to be grass and every pool of water has to be surrounded by a wall, which will cost$a per wall. You can transform water fields into grass, which will cost $b per field, and grass into water for$c. You want to build the cheapest pool area possible.

Actually it is a simple max-flow problem, since a minimum cut in a certain flow encoding the landscape is the optimal solution. You have a source, a sink and a node for every field. A cut should divide the nodes into water-nodes and grass-nodes. Source-to-x edges should have a capacity of the price needed to transform x into a grass-field and x-to-sink edges should have a capacity refering of the price needed to transform x into a water-field, unless the node represents a field at the border, then the capacity should be infinity. Additionally you add x-to-y nodes with a capacity of the price needed to build a wall for adjacent nodes x and y. That is it (if I am not wrong, I hope so :D). Really awesome.

### G

I will post a full description later. For each observation you can yield an inueqility and you can complete the information in a Floyd-Warshall-like manner.

### H

Spam. You have 13 out of 52 regular playing cards and want to partition it into as few as possible bunches of single cards, pairs, triples, quadruples, full-houses and streets of at least five consecutive cards. You can simply use brute force: Test all combinations of up to two full-houses and up to two streets (cannot be more for 13 cards) and greedily take the remaining cards as quadruples, triples, pairs and single cards. We tried that with a lot of copy-and-paste code and our program printed wrong answers, but we have no idea in which cases it failed. Alternatively you can choose a probably more compact solution by building a directed acyclic graph of all 2^13 combinations of your cards where edges represents adding one of the allowed bunches. Then you use breadth-first-search to get the solution. This was one of those typical tasks with useless information in the input (cards were encoded as 4h for ♥4 and Jd for a ♦Jack, in fact the suits did not even matter).

### I

Given integer coordinates of up to 10000 RFID chips, 250000 RFID sensors and 25 walls compute which sensors can detect which chips. Each sensor can detect any chip within a radius of r, while walls reduce the radius by 1. No two sensors are closer to each other than r (“due to interference”^^). We used a sweep-line algorithm. Whenever the sweep line reaches the value x where x+r is the abscissa of a product we add the product to an ordered binary tree (std::set in C++) ordered by the ordinate. When reaching the value x where x-r is the abscissa of a chip we erase it from the tree. If x-r is the abscissa of a sensor we query all products in the tree with ordinates between y-r and y+r using lower_bound and upper_bound where y is the ordinate of the sensor. We count the number of walls intersecting the line between sensor and chip (we check that by adding up angle(p1, q1, p2)+angle(q1, p2, q2)+angle(p1, q2, p2)+angle(q1, p1, q2), which should be 2π (aka 360 degrees) for intersecting line segments) and check whether the chip is within the resulting reduced radius. This solution has a complexity of O((n+m)log(n+m)+n·w) where n is the number of chips, m the number of sensors and w the number of walls. This is guaranteed since the distance between any two sensors is at least r, thus at most 7 sensors can detect one chip (imagine a regular hexagon of sensors with one sensor in the center). Thus for many walls you would probably require a more sophisticated algorithm taking walls into account when sweeping.

Surprisingly only 7 teams solved it, I thought it would be kinda a standard-geometric-sweep-line-problem, it was even easier than E for us (there we used int instead of long long :D). Alternatively you can use binning (since the coordinate space is limited) or quad-trees to solve this problem.

### J

You have a couple of train-stations and ≤1000 connections between these stations. Each connection will be once an hour at a certain minute (e.g. 13:47, 14:47 and so on). However, there is a certain probability that the train will be too late. If it is too late the delay is uniformly distributed in a range from 1 to some number ≤120. You have to compute the minimum expected duration of a trip from the start to the target. We solved that problem by a fixed-point iteration: For each station and each minute (0≤m<60) we store the best known expected duration to the target. We propagate that information till it does not change any longer. Unfortunately it timed out, probably because of floating point issues: we recognised changes which where insignificant or caused by rounding. Only one team solved this problem, three teams tried.

### Subsumption

Yesterday I returned from Bremen, entered the first train at about 17:00, arrived at 0:45 and slept till 12:00. It was a really nice experience. If you are a student, like algorithms and want to participate: go ahead, look for two comrades, ask your professor to register you and join your regional contest! (at some universities there is a local preliminary contest)

PS:
Some visual impressions:

:)

The camera of my N97 mini mobile phone had a bug or something like that, however, when trying to photograph an ugly super market or something like that in the early evening and accidentally moving the camera too early I got this nice photo. Could not reproduce.

Could not reproduce :(

PPS:
The contest was sponsored by Facebook and we had to attend a boring presentation of a Facebook employee. It was quite funny how he tried to make advertisement to work there. He assumed everybody in the room would use Facebook, what? We could get free t-shirts when answering his silly questions, did he think we would like to work there because of a t-shirt? It happened multiple times that he said that he is not allowed to tell about xy, really a great opportunity to work for a company where you cannot even superficially talk openly about the things you are doing there. And he told us that they would finally delete all messages six days after you have pressed the delete-button, haha.

PPPS:
I have pushed some solutions here.

### Barfüßigkeit in den Pinakotheken

Wednesday, September 28th, 2011

Ein Erlebnis, von dem ich bislang hier noch nicht erzählt habe (eines von vielen): Vor einigen Wochen stattete ich der Pinakothek der Moderne in München einen Besuch ab. Neben kräftiger BMW-Werbung gab es wirklich großartige Werke zu sehen, von Dalí, Beuys und vielen anderen. Fotos durften gemacht werden und es war einfach ein schöner Besuch. Wie es mir beliebte, war ich barfuß unterwegs, und als ich mit dem Gedanken spielte, das Museum zu verlassen oder noch einen Teil zu erkunden, und hierzu ins Foyer zurück geschritten war, sprach mich doch tatsächlich eine Angestellte des Museums an, ich könne mich nicht ohne Schuhen in ihren Räumlichkeiten aufhalten. Sie fragte nach dem Aufenthaltsort meiner Schuhe – Garderobe/Rucksack – ich möge sie doch bitte anlegen, so sei die Hausordnung. Auch hielt sie sich nicht damit zurück, mit dem Kontaktieren des Sicherheitspersonals zu drohen. Da ich mir dachte, wie blödsinnig dies ist, wollte ich doch interessehalber diese Hausordnung auch einmal sehen, geht ja nicht an, dass man sich vage auf irgendein Dokument beruft und nichts vorzuweisen hat, zudem hatte ich mich in einer ähnlichen Situation schon einmal abwimmeln lassen – dies sollte sich nicht wiederholen. Sie reagierte gereizt und beleidigt, ich würde ihr nicht glauben, in der Tat hatte ich meine Zweifel, was da in der Hausordnung bitte stehen sollte, doch meine Motivation war mein Interesse.

Ganz ohne den Sicherheitsdienst zu kontaktieren ging sie dann doch zum Thresen und suchte nach der Hausordnung, fragte Kolleginnen nach dem Aufenthaltsort ihrer und rufte sogar an anderer Stelle an. Die Forderung nach Einsicht schien wohl doch nicht völlig unberechtigt. Während dessen redeten sowohl sie als auch eine andere Angestellte auf mich ein, wieso ich ihr denn nicht glaube, obwohl sie so lange schon dort arbeite (die eine), und dass man schließlich nicht wolle, dass das Museum zu einer Art Badewiese verkomme (die andere, wenn ich mich recht entsinne). Schließlich wurde die Hausordnung doch in einem Papierstoß ausfindig gemacht, und ich staunte nicht schlecht: Es wurde tatsächlich in einem Abschnitt konstatiert, dass das Betreten sowohl mit Rollschuhen als auch ohne Schuhe „(‚barfuß‘)“ nicht gestattet sei. So verließ ich verwundert und noch immer barfüßig das Gebäude und wurde noch von hinten als Querulant beschuldigt, da ich nunmal Interesse gezeigt habe.

In einem Satz mit Rollschuhen? Geht es um eine vermeintlich erhöhte Rutschgefährdung, durch die empfindliche Kunstwerke, wie etwa geklebte, frei im Raum stehende Schnüre bedroht werden könnten? Bei den genervten Angestellten war keine Nachfrage mehr möglich, doch die Antwort eines Herrn Regierungsdirektors auf meine EMail-Anfrage brachte dann zum Vorschein:

Als Museen von Weltrang sind wir der Kunst und Ästhetik in besonderer Weise verpflichtet und haben deshalb in unserer Hausordnung die Erwartungshaltung festgeschrieben, dass unsere Besucher der Kunst in üblicher Bekleidung gegenübertreten, wozu nach unserer Auffassung auch Schuhe gehören.

Wunderbar, ich dachte zumindest die Pinakothek der Moderne hätte sich der Kunst verschrieben, und nicht bürgerlicher Selbstdarstellung. Tja, was soll man machen, künftig heißt es dann wohl Waschlappen um die Füße binden. Frei Kunst und freies Denken! Jaja… Das erklärt jedenfalls, wenn keine Kunst in Moscheen aufgehängt wird, wäre ja respektlos, und so mancher Orden hat wohl kollektives Hausverbot in den Pinakotheken.

### Shedding tears, but not crying

Thursday, March 10th, 2011

This is a short post, so I have written it in English and German.

Today I shed some tears – maybe thrice – but I did not cry (no mimic shift, no sadness). That is strange, there were simply some tears, and they were salty. I had already experienced crying without shedding tears, but that is really a new thing.

Heute habe ich ein paar Tränen vergossen, wohl etwa dreimal, aber ich habe nicht geweint, meine Mimik hat sich nicht verändert, und ich war auch nicht traurig. Irgendwie merkwürdig. Es waren einfach nur ein paar Tränen da, sie waren auch salzig. Geweint, ohne Tränen zu vergießen, habe ich schon, aber das ist mir jetzt neu.