Algorithms... When you get started with your CS journey you'll hear this term every now and then and that might lead you down an alley of questions. We'll be trying to clear those out with this series.
This series will solely be based on my understanding of the book called Introduction to Algorithms co-authored by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein. A well known book in the field of computer science, The first edition of which won the award for Best 1990 Professional and Scholarly Book in Computer Science and Data Processing by the Association of American Publishers. That should give you an idea of what the book encloses, So without further ado let's get started.
What is an algorithm?
When learning a language, start with the first alphabet. Let's start with what an algorithm is. There is no formal definition for what an algorithm is. One could say, an algorithm is
a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.
Put in very simple English, An algorithm is any well defined computational procedure that takes in one value or a set of values and produces one value or a set of values as result.
In the midst, it executes a set of computational steps that it had been asked to do before returning the actual result.
Uses of Algorithms
Now that we have an idea of what an algorithm is, we might be curious as to where these are being used. Fair fair.
Short Answer: Everywhere !
Yes, Everywhere. Algorithms lie at the heart of computing. Did you take a lift at your office today? There's an algorithm at work there bringing the nearest available lift to your floor.
Did you scroll through your daily feed of Instagram today? There's an algorithm at work bringing you the posts of your liking to the top.
Simple algorithms have been used for computer-based decision making for decades. Today, algorithms help ease otherwise-complicated processes all the time. I think it is safe to say that in this tech driven world, We all use atleast one algorithm on a daily basis with or without our knowledge.
What are Data Structures?
There can't be a solution when there's no problem, right? Here, in this context, the troubles that we are trying to solve in different data structures are the problem. It could be as simple as adding two numbers, but with an algorithm.
A Data Structure is way to store and organize data in order to facilitate access and modifications
No single data structure works well for all purposes, so it is important to know the strengths and limitations of several of them. Some algorithms go well with only some data structures. So it is important to know the data structure of your problem set in order to solve it with an efficient algorithm which works best over that kind of data structure.
What is Parallelism?
We've been discussing some of the most commonly used terms that go hand in hand with algorithms. Parallelism is one of the most important of those terms. Parallelism is simply parallel computing (i.e) channeling the fragments of a job to multiple cores, instead of one. I know that doesn't make any sense. Well, It will in a while.
In order to understand parallelism, we need to understand how an algorithm is being executed. When a developer codes an algorithm, he codes it in some language which a machine would understand, lets say python or java. When the machine understands the steps to be executed, it executes those steps in the one of the cores of the processor. When there are a lot of tasks to be executed and when the machine executes all those tasks in a single core, the core made of silicon would overheat and which in some point would lead to melting of the core. In order to tackle this, the concept of parallelism came into light.
All I am saying is, when one man can do a job in 8 days and and with 8 men it takes only 1 day to complete the same job, why are we not using / under-utilising the other 7 men.
With an algorithm designed with parallelism in mind, the machine executes the tasks in not only just one core but in multiple cores in parallel without taking a heavy toll on one core of the processor, resulting in an efficient algorithm. I know that I use the word efficiency a lot and how it confuses you, we will discuss what efficiency of an algorithm is in the next part.
Efficiency of an Algorithm
Different algorithms devised to solve the same problem often differ dramatically in their efficiency. these differences can be much more significant than differences due to hardware and software.
To understand this, lets draft down an example problem and attempt to solve it with two algorithms.
Problem:
To sort an array of 10 million numbers
Algorithms to test and their mathematical notation:
Insertion Sort -->
Merge Sort -->
where,
c1, c2 are constants
n is the size of the array
These are the time complexities of the two algorithms
Machines to execute
Lets assume we have two machines, computer A and computer B:
- Computer A executes 10 billion instructions per second
- Computer B executes 10 million instructions per second
So roughly computer A is 1000 times faster than computer B.
Execution
Let's say the best programmer in the world codes insertion sort for computer A, the resulting algorithm requires 2n^2 instructions to sort n numbers
And a very lazy programmer codes merge sort for computer B, which results in an algorithm that requires 50nlogn instructions to sort the same n numbers
When executing insertion sort in computer A, it takes approximately 5.5 hours to complete the execution
Whereas when executing merge sort in computer B, it takes just
less than 20 mins
By using an algorithm whose running time grows more slowly even with a poor compiler computer B runs more than 17 times faster than computer A.
Thus the efficiency of an algorithm is dependent on both the hardware and the software and this is why we should consider algorithms just like computer hardware as a technology, rather than just a concept.
I will sign off with this,
Having a solid base of algorithmic knowledge is one characteristic that distinguishes the truly skilled programmers from the novices.
Top comments (0)