After two months of classes and two weeks of exams, the first quarter of my Master’s is finally complete. I can say that 1/8th of my degree is complete. With a new quarter comes new courses. It’s been just a week but there is one specific topic that I found quite intriguing: geometric algorithms, specifically sweep line algorithms. Before getting deeper into the subject, what are geometric algorithms? Well, they are used to solve geometric problems! Now you may be thinking “why is he stating the obvious?”. Since geometric problems usually deal with an enormous amount of diverse data, the computational complexity is very important. A difference between the running time of a bad algorithm compared to an efficient one can be in the order of days, or even months and years. To illustrate this, I’m going to use a variant of the sweep line algorithm. Traditionally, the algorithm is sued to find intersections aong line segments in a plane but there are many variations.
I recently started my Master’s degree in Computer Science and Engineering (MSCE) and one of the first courses I am following is Advanced Algorithms. It is actually the only single course that is mandatory for all MSCE students, independently of the track/stream they chose. I chose the Web Stream.
The Advanced Algorithms course is divided into three main topics and we recently finished the first one: approximation algorithms. As a way of consolidating my knowledge and also reading a bit more than the notes given by my professor, I decided to write this essay. But first, what is an approximation algorithm and why is it important?
Some of the most well-known problems within Computer Science are virtually impossible to solve optimally at scale in a useful time. One of the most important known problems is the Traveling Salesmen problem. This problem boils down to: given a list of cities and the distances between each pair of them, what’s the shortest possible route to go from a certain city to itself, visiting all of the other cities. This is problem has many more applications that its literal sense, hence its importance.