Master on how to compare Algorithms
Every algorithm does it’s job how to differentiate?
We build software to solve problems ?
Yes we build software to solve problems.
How do you find the right algorithm for the job?
Let’s take an example Imagine I have to sort files . Should I use bubble sort to do that. Now you know where we are heading to.
How do you compare algorithms ?
I have two internet providers in my street. how do I compare them ?
Did you get my point ? I compare common properties of both the providers and select the one suits my needs.
Let’s talk some common sense…
Ok! If I use internet for mails do I require a top tire plan with 1 GBps download and upload that would be an overkill right. In a similar way I work with remote machines should I prefer the least bandwidth plan ?
The only stuff that you need to keep in mind
I hope you got my point the two important things we have to keep in mind while building an algorithm is space and time complexity .
Algorithm Template Format
The real power of using template to describe each algorithm is that you can quickly compare and contrast different algorithms and identify commonalities in seemingly different algorithms.
Each algorithm is presented using a fixed set of sections that conform to this template. We may omit a section if it adds no value to the algorithm description or add sections as needed to illuminate a particular point.
- Name
- Input/Output
- Context
- Solution
- Analysis
- Variations
Let’s learn by example
Graham’s Scan
Name
It is an algorithm that computes the convex hull for a collection of Cartesian points.It is named after Ronald Graham, who published the original algorithm in 1972.The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.
Input/Output
A convex hull problem instance is defined by a collection of points p. The output will be a sequence of points representing a clockwise traversal of the hull.
Context
This algorithm is suitable for Cartesian points.If we have a different system then we should modify the part which computes the low and the high part.
The algorithm works in three phases:
- Find an extreme point. This point will be the anchor. The anchor is guaranteed to be on the hull, and is chosen to be the point with smallest y coordinate.
- Sort the points in order of increasing angle around the anchor. We end up with a star-shaped polygon. Note that the anchor can “see” the whole polygon.
- Build the hull, by marching around the star-shaped polygon, adding edges when we make a left turn, and back-tracking when we make a right turn.
Solution
Consider N points given on a plane, and the objective is to generate a convex hull, i.e. the smallest convex polygon that contains all the given points.
graham(P)
low = point with lowest y coordinate in P
remove low from P
sort P by descending polar angle with respect to low
hull = {P[n-2], low}
for i = 0 to n-1 do
while (isLeftTurn(secondLast(hull), last(hull), P[i])) do
remove last point in hull
add P[i] to hull
remove duplicate last point
return hullLet’s make it code
Analysis
Sorting n points requires O(n log n) performance.The rest of the algorithm has a for loop that executes n times.
T(n) = O(n) + O(n lg n) + O(1) + O(n) = O(n lg n), where n = |Q|.The result is that the overall algorithm performance is O(n log n) since the sorting costs dominates the cost of the whole computation.
Let’s not dig into the algorithm because that’s not the agenda here but now you could understand how such breakdown helps us in selecting a perfect/apt algorithm for a problem.
Variations
In the late 1960s, the best algorithm for convex hull was O(n^2) but at Bell Laboratories they wanted a better algorithm then came the Graham Scan Algorithm.
Hope you liked it, feel free to comment you queries I am happy to answer.
