The dispositions cover the following topics:

- Polygon triangulation
- Range searching
- Point location
- Voronoi diagrams
- Delaunay triangulations
- Geometric data structures
- Robot motion planning and visibility graphs

The notes are primarily intended for other curious students at DIKU. If you wish to learn about the subjects, I can recommend the book Computational Geometry: Algorithms and Applications, which was used during the course.

]]>Recently, LinkedIn has started adding people based on your email contacts to their “People You May Know” page. Just to be clear, this is people who do not have a LinkedIn account already, so attempting to add them will have LinkedIn send them a mail on your behalf.

You might note that they cleverly have made them look almost identical to how people who actually have accounts on LinkedIn, so it’s very easy to inadvertently send an invite to someone while using this page.

I don’t quite like the thought of that, so I made a userscript that removes the email entries from the listing, showing only people with pre-existing accounts.

The resulting page looks something like this:

Once you have Tampermonkey (in Chrome) or Greasemonkey (in Firefox), the script can be installed by clicking the following button:

]]>This year I participated with Kristoffer Søholm and Morten Brøns-Pedersen, two of the members of the DIKU hacker-group Pwnies. We chose to call ourselves Fwnies, and managed to secure ourselves a 4th place in the Danish rankings, and a 20th place overall.

In connection with hacking competitions, the different teams often do write-ups explaining their solutions after the contest is over. I quite like that concept, so I thought I’d share our solutions for the NCPC problems.

This problem is rather simple, so I don’t think the code needs much explanation.

It is optimal to have each vegetable cut into even-sized chunks, since this minimizes the maximal weight (and maximizes the minimal weight) of all the chunks from that vegetable. Our solution keeps a priority queue consisting of one triple (w, ow, c) for each vegetable. w is the weight of each chunk, ow is the original weight of the vegetable, and c is the number of cuts made. (So w = ow/c). We then proceed to take the heaviest chunk and add another cut to the vegetable until we achieve the desired ratio.

Our first observation was, that a straight-forward solution would be O(n^{2}) in the number of points. At a problem size of 10^{5}, that seemed a bit high. We then observed, that the two points that are the furthest from each other must be on the convex hull of the points.^{[1]} While this still would give a O(n^{2}) worst-case^{[2]}, it seemed a much more reasonable set of points to compare against each other.

The gist of our solution to this problem is to find the length of the longest common prefix and suffix of the two strings. Once we have these, the minimal DNA inserted is whatever lies between the longest common prefix and suffix.

This is a rather straight-forward parsing problem.

Another simple problem. The key insight here is, that you only really need to know if the number is even or odd, since two bit-flips cancel each other out.

This problem basically reduces to the problem of integrating f. We integrate f on each of the rings, multiplying by the expected value for landing in that ring.^{[3]} We spent a lot of time trying to get enough precision out of our numerical integration, which we finally managed to do on our 7th submission.

Implementation of the convex hull algorithm shamelessly taken from the Stanford ACM Team notebook↩^{[1]}If they had decided to place all the points on a circle, the convex hull would be formed by all the original points. This, however, seemed unlikely to us.↩^{[2]}Easily computed by taking the average of the scores in each square on the ring, since they have equal size.↩^{[3]}

This time, it’s a script that highlights posts made by friends. The script automatically reads your buddy list when you visit your user control panel, so you don’t need to do any manual maintenance of your friends list.

I had previously made the same feature for the SALR extension for Chrome, but seeing as I don’t use that anymore, I decided to remake it in stand-alone form.

The script has been tested with Tampermonkey on Chrome, but should work just fine with Greasemonkey on Firefox.

**Screenshot:**

That is, instead of `I use the function \texttt{liftM2} to lift ...`

, use `I use the function \hoogle{liftM2} to lift ...`

.

What the command does is not only format the function name in a fixed-width font using `\texttt`

, but also link it to a Hoogle-search, to allow the reader to easily look up what the function does, in case it’s unknown to them.

So you’re a student at the University of Copenhagen, and you’re starting on a new course. Wouldn’t it be lovely if you could add your schedule to your calendar, so that you could keep track of when to be where?

Well, Rasmus Wriedt Larsen has devised a website, KU Calendar Helper, which automatically produces an ICAL feed you can add to your Google Calendar or similar. You can simply input the URL to the course schedule, and it’ll do the boring work for you.

To simplify this process, I created the following userscript:

To use this script, follow these simple steps:

- Go to the SIS-page of the course you want a calendar feed for.
- Click “Vis skema for kurset”
- On the top of the page that comes up, click “Export to calendar”
- Follow the instructions on the page that comes up

The script has been tested in Chrome using Tampermonkey, but should work well in Firefox using Greasemonkey as well.

]]>An interesting fact about them, however, is that each picture given a name consisting of only 5 alphanumerical characters. This leaves for roughly 916 million different names. As it turns out, there appears to be around 90 million uploaded images^{[1]}, which means that if we randomly guess a name for a file, we have an about 1 in 10 chance of actually finding an image.

Those odds are pretty good, so I wrote a small application which does just that.

Download the latest version here (or get the source code directly from github)

It’s written in F#, so you’ll need the F# Runtime 2.0 installed for the program to run, but apart from that it requires no installation: Simply run the .exe-file to use the program.

Credit goes to whomever wrote this script for inspiring me to create an improved version.

Enjoy finding random strange images!

Rough estimate based on empirical observations.↩^{[1]}

You can make a quine in any Turing-complete language, and the reason for this is a thorem called the

Now, in order for this post to make sense, we’ll have to look a bit into the proof of the theorem. The idea behind the proof is as follows: We divide our program into three program fragments, *A*, *B* and *F*, each of which we can think of as a function in our programming language of choice. *A* is called first, and has the task of getting , the source code of the functions *B* and *F*, and passing this on to *B*. *B* computes , and uses this to compute and pass it on to *F*. *F* is then the program fragment computing the function *f*, now with the source code of the entirety of the program in hand.

Now that we have an idea of how the different fragments are to interact with each other, we need to get down to the specifics, and actually construct the fragments *A* and *B*^{[2]}.

We will start by constructing *A*. Let us for a moment assume that we actually have *B* and *F* already constructed. In that case, is a fixed string. This means, we can have *A* simply call and be done with it.

For constructing *B* we will need to be a bit more tricksy. We know, based on how we constructed *A*, exactly what *A* looks like if we know what is^{[3]}. This means, given , we can construct — and we’re in luck: Remember, when *A* calls *B*, it passes along the extra information of . So, we now have both and , and if we compose these two we get . We now call , and *B* does what we want it to.

This concludes the proof of the theorem, and it is now time to look a bit at how we can use it. A particularily interesting thing about this proof is, that we can use this construct directly to create a quine. To try this out, let us create a SML program, which prints its own source code in reverse.

We can start by creating *F*. All that *F* needs to do is simply to reverse and then print its input. This can be achieved pretty easily like so:

`val F = print o implode o rev o explode`

Next up is *B*, but before we can construct that, we need to figure out what we want *A* to look like. The simplest option is to have *A* take on the following form:

Now we can begin constructing *B*. If we just naïvely do this, we get something to the tune of:

This, however, suffers from the fact, that we’ll need to escape the quotes in the definition of *B* when writing them inside of the string in *A*. Were we to do this, we’d find that we’d need to escape the escape characters as well. A fixed version looks as follows:

Finally, we need to create *A*, but that is fairly simple, as we already have determined what format it should have. Since SML doesn’t support multiline strings, however, I collapse *B* and *F* onto one line, giving us a final result of:

And there we have it, we’ve created a lovely^{[4]} reverse quine in SML using the recursion theorem. Not only that, we could repeat the process and do the exact same thing in most any other language — or change out *F* to whatever we wish. There is nothing special about the language or *F* we chose — and that I find quite spectacular.

The actual formal statement and proof of the theorem can be found in Introduction to the Theory of Computation by Michael Sipser. If you like the content of this article, I urge you to read it — it is quite a good book.↩^{[1]}Why do we not need to construct^{[2]}*F*?↩After all, we constructed^{[3]}*A*based on this ourselves.↩Okay, not the prettiest, but lovely in concept.↩^{[4]}

It’s that time of year again; the new students have started at DIKU and start their careers as computer science students with the course DiMS — Discrete Mathematical Structures, taught from the book by the same name.

Part of the curriculum is learning about Hasse diagrams, which in essence are a way of easily visualizing the relationships between different elements under a partial order.

Now, a student came and asked me about how to draw these diagrams in Mathematica, so I got some code working which did just that. The resulting diagram, is the picture used for this post.

In the spirit of sharing, here is the Mathematica-code I used to generate this picture:

Luckily, the marketing departments of many large software corporations know this, and wants to get you hooked on their applications, leaving us students very happy.

First of all, it’s worth checking if your school or university participates in the Microsoft Developer Network Academic Alliance, or MSDNAA for short. If that is the case, you may be eligible to get free copies of Windows, Visual Studio and much more. Simply head on over and search for your school to see if you can get lovely free software. If your school does show up in the list, ask your local IT department if it’s possible to get an account. (If you study at DIKU, you can sign up here.)

Microsoft provides another way to get free software called DreamSpark. DreamSpark provides free access to lots of free development software for students at participating schools, in a manner similar to that of MSDNAA. Sadly, University of Copenhagen does not appear to be a part of this deal, but your university might be; simply go to the page and follow the instructions to log in.

Next up is OnTheHub, with which your school might have struck a deal to provide cheap software from Microsoft, Adobe, VMware and more. Simply head on over to their search page, and see if your school is listed. University of Copenhagen has a deal with VMware, for instance, which means we get free copies of VMware Workstation, among other things. In case nothing is available for your school, you can also take a look at their store, which may contain something useful.

Additional deals that aren’t quite as major, but still notable:

- Upgrade to Windows 7 Professional for only $30.

If you don’t have Windows 7, then trust me, it’s worth upgrading to. - Get Office 2010 Professional Academic Edition for $80.

This is the full Office pack, by the way, not some trimmed down “Only Word, Excel and Access” one.