Muli Ben-Yehuda's journal

July 2, 2003

Algorithmics course

Filed under: Uncategorized — Muli Ben-Yehuda @ 2:33 PM

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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: