## 13 thoughts on “A students homework in algorithms”

1. The line "Do you know that third reich is a euclidean space", while the pen hits the map, is a touch of genius.

2. "It can't be solved in polynomial time"

Can you email me proof of this? I really want to win \$1 million dollars.

• Please note that you was not the first who observed that this statement is not justified -- in the movie we see that Hitler was the first one ðŸ™‚

3. Haha the whole time I was confused. At the beginning they just wanted to connect all the strategic cities with the minimum amount of road, so why no MST from the beginning?

• If one wants to connect only subset of points in the metric, then MST is only 2-approximation. Whereas Arora'a algorithm can in principle give almost optimal solutions.

• Note that when connecting the *strategic* cities you can also use all the other cities -- this is the Steiner Tree problem. If you were allowed to build roads only between the strategic cities then this would be the Minimum Spanning Tree problem indeed.

4. Oh so very clever! I enjoyed it and will share with friends (those who would enjoy NP-hard humor)!