By: Arif Khan.
The most important and core subject of computer science “Design analysis of algorithm” also known as DAA.
Why it is most important?
There are some main reasons behind its importance.
- In Graduate Aptitude Test in Engineering (GATE) exam, 10 to 15 percent paper consists of this subject.
- In competitive exam this subject is also very important.
- Any highly paying national and international companies always evaluate the candidates understanding over this subject. They less care about how many languages you know and you can work, but their most concern is about what are your concepts on this subject, they always ask some main questions about the data structure/design analysis and algorithm.
Every technology is based on this, big companies like Google, Amazon and other big giants who are providing their services on the net and dealing with petabytes of data, are using most complex algorithms, their algorithm developers are highly paid personals.
If we talk about google search engine or google maps which are most suited examples of algorithm implementation, now a days you can go anywhere without even asking anybody about the path, just start google maps enter your desired location over a blink of an eye the whole path way will be in front of your eyes, just click of a single button, even it will tell you the shortest and fastest way to reach your destination, just because they are using searching algorithms. You also noticed that in a single day you search so many sites by google search engine to seek knowledge. It all happens just because of their efficient searching algorithms implemented in their servers. Let’s together learn this most important topic.
First take a look at Algorithm
Simple definition of Algorithm
Finite and unambiguous set of steps or instructions to solve a problem is called Algorithm.
Let’ understand this definition with the example. If you have to problem to perform mathematical calculation on two numbers which are A & B, and mathematical calculation can be (+, -, /, *). You can write a simple program to solve this problem in any language like (JAVA, PYTHON, C #, C++, C and Julia ETC) but your task is to write a blueprint using layman language which will be very easy to understand to others and to yourself, rather than going into a particular programming language. This blueprint will explain the execution process which will happened in background when program will execute.
While writing algorithm you should remember three things:
- It should be finite set of instructions.
- It must be unambiguous.
- Each instruction should have finite time of executed.
The finite and unambiguous set of steps for given task will be as follows:
Example Algo:
Step#1: Read A
Step#2: Read B
Step#3: C = A + B
Setp#4: Print (C)
As you saw, above instructions are finite and there are not ambiguities in them. Let’s understand, step by step.
In step 1 your program will read the given value for variable A, in step 2 program will do the same for variable B, in step 3 program will store the sum of A & B, finally in step 4 program will print the resulting value which is stored in variable C on the screen.
This program will just execute once and will not perform any repetitive execution that is why you can say that these instructions are finite, secondly you did not use any unwanted/unnecessary symbol or sign within the steps that is why you can say that those lines are unambiguous. Everything is clear and to the point, you can now implement this code on any language of your choice.
Be careful to write the algorithm which contain loops, must not infinite. For example below loop will infinite which is very wrong.
If loop line changed as for (int a = 0; a >= -50; a–) it will become finite which is good.
Now take a look at Analysis
Simple definition of Analysis
Analysis is a process of comparing two or more algorithms with respect to Time, Space etc.
Let’s understand with example.
If you are working on searching algorithm then you have two main search algorithms (Binary Search and Linear Search) you have to decide which is best for your requirement, if you are working on sorting than you have (Quick Sort, Bubble Sort, Merge Sort, Heap Sort, Radix Sort, Bucket Sort etc.) from all of these algorithms you have decide which is best for your requirements.
To compare between algorithms you must have some constraints/parameter and the parameters are (Time, Space, number of registers, network bandwidth etc.) there are so many parameters available to compare two or more algorithms but the most important are Time and Space as written above. So, the comparison is the most important part, that’s how you find their time complexity and space complexity.
There are two methods of algorithm analysis.
- Prior ( before execution analysis)
- Posterior (after execution analysis)
Prior analysis is always independent of machine hardware or software while the posterior analysis dependents of machine hardware and software, like if you write a C-Sharp code with stopwatch enabled, then you will find that after execution the program stopwatch will give you the execution time, that is how you can monitor the Elapsed execution time of your algorithm according to your working environment, if you upgrade or downgrade your hardware resources, the execution time will reduce or increase after the change.
But in prior analysis we just check that how many time each iteration is executing, what is its frequency and magnitude, like how many times a function is being called internally or externally. If we look into Example Algo written above, and check its iteration frequency you will notice that every instruction will execute just once, like step 1 will run only once and the same will happened with all the instructions.
So the approximate execution time of each instruction is 1, as prior analysis will always give you approximate execution time, on the other hand the posterior analysis will give you exact execution time depending on the hardware resources.
We will consider prior analysis because it is independent and will always give you approximate uniform results, you only need to consider its worst and best scenarios. To represent prior analysis you can use asymptotic notations/Big O notations/Big Omega notations/Theta notations/Small O notations and Small Omega notations. We will discuss about them in latter articles.
Your are always welcome to write comments and suggestions
