DAA Tutorial

Our DAA Tutorial is designed for beginners and professionals both.

What is Algorithm?

Basic : An Algorithm is a sequence of steps to solve a problem.

Detail : An algorithm can be defined as a well-defined computational procedure that takes some values, or the set of values, as an input and produces some value, or the set of values, as an output. An algorithm is thus a sequence of computational steps that transform the input into output.

It describes specific computational procedures for achieving the input-output relationship.

For Example, We need to sort the sequence of number into ascending order. Here is how we define the sorting problem.

Input:

A sequence of n number (a1, a2,......an)

Output:

A permutation (reordering) (a'1, a'2 .... a'n) of the input sequence such that (a'1 ≤ a'2 ≤ ....≤ a'n)

Why study Algorithm?

The standard definition of algorithm is:

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output.

In other words it defines a step by step process to solve a particular problem.

Now let's come to the question, by studying algorithms you will be able to find the best algorithm for you problem(as there exists multiple algorithms for a problem).

By studying algorithms you can differentiate two or more algorithms on the basis of there efficiency, resource utilization , time to solve problem and accuracy.

Characteristics of an algorithm:-

Must take an input.
Must give some output(yes/no, value etc.)
Definiteness –each instruction is clear and unambiguous.
Finiteness –algorithm terminates after a finite number of steps.
Effectiveness –every instruction must be basic i.e. simple instruction

Expectation from an algorithm

1. Correctness:-

Correct: Algorithms must produce correct result.
Produce an incorrect answer:Even if it fails to give correct results all the time still there is a control on how often it gives wrong result. Eg.Rabin-Miller Primality Test (Used in RSA algorithm): It doesn’t give correct answer all the time.1 out of 250 times it gives incorrect result.

2. Approximation algorithm: Exact solution is not found, but near optimal solution canbe found out. (Applied to optimization problem.)

3. Less resource usage:

Algorithms should use less resources (time and space).

Complexity of Algorithm

It is very convenient to classify algorithm based on the relative amount of time or relative amount of space they required and specify the growth of time/space requirement as a function of input size.

1. Time Complexity: Running time of a program as a function of the size of the input.

2. Space Complexity: Some forms of analysis could be done based on how much space an algorithm needs to complete its task. This space complexity analysis was critical in the early days of computing when storage space on the computer was limited. When considering this algorithm are divided into those that need extra space to do their work and those that work in place.

But now a day's problem of space rarely occurs because space on the computer (internal or external) is enough.

Broadly, we achieve the following types of analysis -

Worst-case: f (n) defined by the maximum number of steps taken on any instance of size Best-case: f (n) defined by the minimum number of steps taken on any instance of size Average case: f (n) defined by the average number of steps taken on any instance of size n.

That's all basic introduction about Algorithms, Now we move to particular topic in sequence.

Call us

DAA : Design and Analysis of Algorithms