Core S2 Software Solutions

Power of Algorithms

Older article from Lost in Dev; originally written by Jeremy Bridon.

Many Computer Science students, especially those who aren’t specializing in computational theory or math, do not appreciate the importance of algorithms. Algorithms, a series of mathematical instructions, are a way to solve problems. Tying your shoe is a series of instructions, usually where you move your lace over or under or into a loop. Driving a car is a massively complex algorithm, in which special conditional statements exist, such as stop at red lights or turn on blinkers when turning. The power of an algorithm is that not only can it solve for a variable length of input, but its speed of completion can be measured and have a relationship quantified between input length and performance. Sorting a list of numbers is a classic problem in computer science, and many different approaches exist. Some algorithms solve this problem very slowly, such as bubble-sort. Other algorithms are very effective at solving this classic problem, such as heap-sort, but both methods are wildly different.

The reason I bring this topic up is to show a quick, and important, example. I was writing a line extraction algorithm used in a road detection component of the PSU Robotics Mini Grand Challenge robot. I was attempting to use a laser-range finder, pointed at the road, to find what parts of the road infront of the robot was drivable, and to detect any possible collisions. I first wrote a naive algorithm, in essence a brute force algorithm somewhere on the order of O(n^3) (Big-O notation). Even with the best implementation in code, the run-times were still slow and incorrect. This is where the power of the algorithm shines!

A friend gave me this paper to read, from IEEE. The entire paper focuses on different types of line regression and extraction method, as well as their complexities, real-world speed as well as correctness values and precisions. Using all the data provided, in less then half an hour, I was able to fully implement the code, which instantly worked and at amazing speeds! I guess the lesson here is that algorithms are critically important, and the only way to succeed in any real-world program is to not only program it well, but design it reasonable algorithmic complexity! Don’t always use naive solutions for your problem; research and find an algorithm that best fits your problem!

This entry was posted in News & Updates. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *


Sites map