Muli Ben-Yehuda's journal

Yesterday was the first class of the summer course I’m taking at the Open University, “Algorithmics – Foundations of Computer Science”. When I registered, I was pretty excited about this class. It’s based on the book by Prof. David Harel of the Weizmann institute, that I’ve been meaning to read anyway. Then I got the book (openu edition) and read the first four chapters. While it’s written quite clearly and is interesting, it’s a popular science book, not a text book! there is nary a proof in sight, and the treatment of the material is quite superficial. Therefore, it was with some trepidation that I went to class yesterday. My feelings of foreboding (“is this fluff what I’m going to waste the summer on?”) weren’t helped when I heard class mates talking about this course, which is supposed to be a breeze to pass.

Then the instructor started talking, and within an hour into the lesson, I realized that my summer wasn’t going to be wasted after all. We discussed the “subset sum problem”, NP complete problems, the graph coloring problem and its relation to the map coloring problem[0], and the variations of knapsack problem. Unlike my usual habit, I actually took part in the class, proposing solutions and optimizations and finding flaws in others proposed solutions. Fascinating stuff!

[0] The instructor discussed graph coloring, and showed that any graph which is a clique of size N cannot be colored with less than N colors. This statement, which is obviously correct, contradicted with what I remembered about any map being 4 colorable. After thinking about it for a few minutes, I asked what was the relation between coloring a graph and coloring a map. The answer is that any map can be represented by a planar graph, but not every graph can be represented by a map. All planar graphs are indeed 4 colorable, and a clique of N > 4 cannot be represented by a planar map. Contradiction solved.