DAA Unit 1.pdf

Design and Analysis of Algorithm- Unit 1: Introduction

1. DESIGN AND ANALYSIS
OF ALGORITHM -
INTRODUCTION
DR. V. NIRMALA
DEPARTMENT OF AI & DS
EASWARIENGINEERING COLLEGE

2. Algorithm
•An algorithm is a procedure to solve a particular problem in a finite number of steps for a finite sized
input.
•An algorithm can be implemented in more than one programming language so algorithm is a language
independent.
•Not all procedures can be called an algorithm.
For example, Task: to make a cup of tea.
Algorithm:
•add water and milk to the kettle,
•boil it, add tea leaves,
•Add sugar, and then serve it in cup.

3. Characteristics of Algorithm
•Unambiguous:
Algorithm should be clear and unambiguous. Each of its steps (or phases), one and their inputs/outputs should
be clear and must lead to only meaning.
•Input:
An algorithm should have 0 or more well-defined inputs.
•Output:
An algorithm should have 1 or more well-defined outputs, and should match the desired output.
•Finiteness:
Algorithms must terminate after a finite number of steps.
•Feasibility:
Should be feasible with the available resources.
•Independent:
An algorithm should have step-by-step directions, which should be independent of any programming code.

4. Properties of Algorithm

5. Properties of Algorithm…
1. Input: An algorithm should have some inputs.
2. Output: At least one output should be returned by the algorithm after the completion of the specific task based on the
given inputs.
3. Definiteness: Every statement of the algorithm should be unambiguous.
4. Finiteness: No infinite loop should be allowed in an algorithm.
Example:
while(1<2)
{
number=number/2;
}
5. Effectiveness: Writing an algorithm is a priori process of actual implementation of the algorithm. So, a person should
analyze the algorithm in a finite amount of time with a pen and paper to judge the performance for giving the final
version of the algorithm.

6. Properties of Algorithm…
6. Non Ambiguity
Each step in an algorithm should be non-ambiguous. That means each instruction should be clear and precise. The
instruction in any algorithm should not denote any conflicting meaning. This property also indicates the effectiveness of
algorithm.
7. Range of Input
The range of input should be specified. This is because normally the algorithm is input driven and if the range of input is
not being specified then algorithm can go in an infinite state.
8.Multiplicity
The same algorithm can be represented into several different ways. That means we can write in simple English the
sequence of instruction or we can write it in form of pseudo code. Similarly, for solving the same problem we can write
several different algorithms.
9.Speed
The algorithmiswritten using some specified ideas. Bus such algorithm should be efficient and should produce the output
with fast speed.
10.Finiteness
The algorithm should be finite. That means after performing required operations it should be terminate

7. How to write an Algorithm?
•There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms
are never written to support a particular programming code.
•As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-
else), etc.
•These common constructs can be used to write an algorithm. We write algorithms in a step-by-step manner, but it is
not always the case.
•Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the
problem domain, for which we are designing a solution
•Example: Two ways of writing an algorithm

8. Pseudo code for expressing algorithms
•Pseudo code, as the name suggests, is a false code or is a high-level description of an algorithm.
•Pseudo code can be easily understood by someone who has basic knowledge of programming.
•Pseudo code does not have a specific syntax unlike a program that is written using syntaxes of a
particular language.
•Hence, pseudo code cannot be executed on a computer; rather it eases the work of a programmer as it
can be easily understood.
•While writing pseudo code one can use control structures that include for, while, if-then-else, repeat
until.
•These control structures are common in almost all programming languages and hence can be used
when required.
•Once we are done with the pseudo code we can easily modify it into a program in our preferred
language.
•Another advantage of pseudo code is that the running time of the program can be estimated in a
general manner using it. A pseudo code gives us a count of fundamental operations

9. Difference between Algorithm and
Pseudo code
•An algorithm is a well defined sequence of instructions that provide a solution to the given problem.
•A pseudo code is a method which is used to represent an algorithm.
•An algorithm has some specific characteristics that describe the process.
•A pseudo code on the other hand is not restricted to something. It’s only objective is to represent an
algorithm in a realistic manner.
•An algorithm is written in plain English or general language.
•A pseudo code is written with a hint of programming concepts such as control structures.
•To understand the difference between an algorithm and pseudocode lets have a look into the following
example:

10. Advantages of pseudo code
•Pseudo code improves the readability and is the best way to start implementing an algorithm
•A pseudo code works as a rough documentation. It makes the work of a programmer easy as it
helps them understand the code better.
•It acts as a bridge between a program and an algorithm.
•It makes the process of constructing a code easy

11. How to write a Pseudo code
As mentioned, a pseudo code is a method used to implement an algorithm. However there are a few points to be noted
while writing a pseudo code.
They are:
1. First, arrange the tasks in a sequence so that the pseudo code can be written by following the same sequence. This will
make the process more clear and simple.
2. A pseudo code is something that can be understood by any basic programmer. However, in case of complex problems it
could be difficult to understand the main goal of the problem if it is not specified in the pseudo code. So, do include a
statement that established the main goal.
3. Follow the indentation and whitespaces as you would do while writing an actual program. Indentation helps greatly
with readability.

12. How to write a Pseudo code..
4. Here, both the examples have the same meaning. However, the 2nd example is more clear and understandable compared to the
1st. This is the magic of Indentation and white spaces.
5. Following a naming convention is important. Sometimes, naming in the wrong way can lead to confusion. So, naming must be
done in a simple and distinct way. Sentence casings will always help you differentiate between constants, variables, methods,and
others. This will avoid any confusion that might be present in the algorithm.
For methods use CamelCase
For constants use UPPERCASE
For variables use lowercase
6. A pseudo code is supposed to explain the code in detail. Do not keep the pseudo code abstract.
7. Use of control structures such as ‘for’, ‘while’, ‘if-then’ and ‘cases’ makes it easy while you develop a program using the
pseudo code as reference.
8. A pseudo code must be perfect in order for the code to be perfect. So do check if the pseudo code consists of any infiniteloops
or any gaps.
9. A pseudo code must be must enough to be understood by a layman so do not write it in a programmatic way.

13. Do’s and Don’ts while writing a Pseudo
code:
Do’s:
Make use of control structures.
Naming conventions must be followed properly.
Use indentation and white spaces wherever required as these are the key points for a pseudo code.
Keep the pseudo code simple and concise.
Don’ts:
Do not generalize the pseudo code.
A pseudo code mustn’t be abstract.

14. Performance analysis of an algorithm
Performance analysis of an algorithm depends upon two factors i.e. amount of memory used and amount of compute time
consumed on any CPU.
Formally they are notified as complexities in terms of:
1. Space Complexity.
2. Time Complexity.
Space Complexity of an algorithm
Space Complexity of an algorithm is the amount of memory it needs to run to completion i.e. from start of execution to its
termination.
Constant space complexity
Linear space complexity
let’s have a look into a few examples to understand how to calculate the space complexity.

15. Performance analysis of an algorithm
..
Here, in this example, we have 4 variables which are a, b, c, and sum. All these variables are of type int
hence, each of them require 4 bytes of memory.
Total requirement of memory would be : ((4*4)+4) 20 bytes.

16. Performance analysis of an algorithm
..
Here, we have considered 4 additional bytes of memory which is for
the return value. Also, for this example as the space requirement is
fixed it is known as constant space complexity.
In this example, we have 3 variables i, k, n each of which will be
assigned 4 bytes of memory. Also, for the return value 4 bytes of
memory will be assigned. Here, we also have an array of size n,
hence the memory required for that would be (4*n).
Hence the total memory requirement would be : (4n+12)
This value will vary based on the value of n. As the value of n
increases the memory would also increase linearly. Therefore it is
known as Linear Space Complexity.
Depending on the complexity of the algorithm, the space
complexity can range uptoquadratic or complex too. We should
always try to keep the space complexity as minimum as possible.

17. Performance analysis of an algorithm
..
Time complexityis most commonly evaluated by considering the number of steps required to complete the execution of an algorithm. Also,
many times we make use of the big O notation which is an asymptotic notation while representing the time complexity of an algorithm. We
will be discussing asymptotic notations in the next article.
Now, let’s dive into calculating the time complexity with the help of a few examples.
Constant time complexity:
Example:
Statement –printf(“EASWARI”);
In the above example, as it is a single statement the complexity of it would be constant. Its complexity wouldn’t change as it is not dependent on any variable.
Linear time complexity:
Example:
for(i=0; i< N; i++)
{
statement;
}
Here, the complexity would be proportional to n. Hence, the time complexity would be linear.

18. Performance analysis of an algorithm
..
Quadratic time complexity:
Example:
for(i=0; i< N; i++)
{
for(j=0; j <N;j++)
{
statement;
}
}
Here, in this example we have a loop inside another loop. In such a case, the complexity would be proportional
to n square. Hence, it would be of type quadratic and therefore the complexity is quadratic complexity.

19. Performance analysis of an algorithm
..
Logarithmic time complexity:
Example:
while(low <= high)
{
mid = (low + high) / 2;
if (target < list[mid])
high = mid -1;
else if (target > list[mid])
low = mid + 1;
else break;
}
In this example, we are working on dividing a set of numbers into two parts. Which means that the complexity would be
proportional to the number of times n can be divided by 2, which is a logarithmic value. Hence we have a logarithmic time
complexity.

20. Performance analysis of an algorithm
..
Example:1 Algorithm for Transpose of a Matrix
1. Create an auxiliary dummy_matrixthat stores the transpose of the_matrix.
2. For a row in the first matrix, make it the first column in the newly constructed matrix.
3. Move to the next row and do it for all the rows. B[i][j] = A[j][i] , B is Transpose of A.
4. After completing all the rows, print the new_matrix, it is a Transpose of the given_matrix.
Time Complexity O(n2)
where n is the maximum of r1 and c1.
Here we simply run two loops first loop run r1 times and the second loop runs c1 times.
And inside the second loop, we just change the location of the current element in the auxiliary matrix.
Space Complexity O(m2)
where m is the maximum of r1 and c1.
Here we create extra space for storing the transpose of the given_matrix.
Here we also declared r1*c1 size for taking input from the given matrix.

21. Performance analysis of an algorithm
..
Example:2
How to find the time complexity of an algorithm
Given the following algorithm:
public Integer sum EvenNumbers(Integer N)
{
int sum = 0;
for (int number = 1; number <= N; number++)
if ((number % 2) == 0)
sum = sum + number;
return sum;
}
First, we split the code into individual operations and then compute how many times it is being executed as is shown in the following table
Now, we need to sum how many times each operation is executing.
Time complexity = 1 + 1 + N + N + N + N + 1 => 4N + 3 .

22. Asymptotic Notation
Asymptotic notations are the mathematical notations used to describe the run time complexity of an
algorithm
Types of asymptotic notations:
1. Big-O notation
2. Omega notation
3. Theta notation
4. Little oh notation

23. Asymptotic Notation…
Big-O Notation (O-notation)
Big O Notation is a mathematical notation that helps us
to analyze how complex an algorithm is in terms of time
and space.
Big-O notation represents the upper bound of the
running time of an algorithm.
Thus, it gives the worst-case complexity of an
algorithm
O(g(n)) = { f(n): there exist positive constants c and n0
such that
0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

24. Asymptotic Notation…
Omega Notation (Ω-notation)
Omega notation represents the lower bound of the
running time of an algorithm. Thus, it provides the best
case complexity of an algorithm.
Ω(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
The above expression can be described as a function f(n)
belongs to the set Ω(g(n)) if there exists a positive
constant c such that it lies above cg(n), for sufficiently
large n.
For any value of n, the minimum time required by the
algorithm is given by Omega Ω(g(n)).

25. Asymptotic Notation…
Theta Notation (Θ-notation)
Theta notation encloses the function from above and below.
Since it represents the upper and the lower bound of the
running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.
Theta bounds the function within constants factors
For a function g(n), Θ(g(n)) is given by the relation:
Θ(g(n)) = { f(n): there exist positive constants c1, c2 and
n0
such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

26. Asymptotic Notation…
Thus, little o() means loose upper-bound of f(n). Little o is a rough estimate of the maximum order of
growth whereas Big-Ο may be the actual order of growth
Θ(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f (n) <cg(n) for all n ≥ n0 }

27. Properties Asymptotic Notation…
As we have gone through the definition of these three notations let’s now discuss some important properties
of those notations.
1. General Properties:
If f(n) is O(g(n)) then a*f(n) is also O(g(n)) ; where a is a constant.
Example: f(n) = 2n²+5 is O(n²)
then 7*f(n) = 7(2n²+5) = 14n²+35 is also O(n²) .
Similarly, this property satisfies both Θ and Ω notation.
We can say
If f(n) is Θ(g(n)) then a*f(n) is also Θ(g(n)) ; where a is a constant.
If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)) ; where a is a constant.

28. Properties Asymptotic Notation…
2. Transitive Properties:
If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) = O(h(n)) .
Example: if f(n) = n, g(n) = n² and h(n)=n³
n is O(n²) and n² is O(n³)
then n is O(n³)
Similarly, this property satisfies both Θ and Ω notation.
We can say
If f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) = Θ(h(n)) .
If f(n) is Ω (g(n)) and g(n) is Ω (h(n)) then f(n) = Ω (h(n))

29. Properties Asymptotic Notation…
3. Reflexive Properties:
Reflexive properties are always easy to understand after transitive.
If f(n) is given then f(n) is O(f(n)). Since MAXIMUM VALUE OF f(n) will be f(n) ITSELF !
Hence x = f(n) and y = O(f(n) tie themselves in reflexive relation always.
Example: f(n) = n² ; O(n²) i.e O(f(n))
Similarly, this property satisfies both Θ and Ω notation.
We can say that:
If f(n) is given then f(n) is Θ(f(n)).
If f(n) is given then f(n) is Ω (f(n)).

30. Properties Asymptotic Notation…
4. Symmetric Properties :
If f(n) is Θ(g(n)) then g(n) is Θ(f(n)) .
Example: f(n) = n² and g(n) = n²
then f(n) = Θ(n²) and g(n) = Θ(n²)
This property only satisfies for Θ notation.
5. Transpose Symmetric Properties :
If f(n) is O(g(n)) then g(n) is Ω (f(n)).
Example: f(n) = n , g(n) = n²
then n is O(n²) and n² is Ω (n)
This property only satisfies O and Ω notations.

31. Probabilistic Analysis
In general, probabilistic analysis is used to analyze the running time of an algorithm. In simple words, probabilistic
analysis is the use of probability in the analysis of problems.
Sometimes, we can also use it to analyze quantities. One such example is the hiring cost in procedure Hire-Assistant.
Hiring Problem:
For example, you are using an employment agency to hire a new assistant for your company. The agency works in such a
way that it sends you one candidate per day. You then interview the candidate after which you must immediately decide
whether or not to hire that person. Also, if you hire that person, you must fire your current office assistant. Even if it is
someone you have hired recently you must fire them before you hire a new assistant.
For this, let us consider the cost to interview as ci per candidate and the cost to hire the candidate is ch.
Also, there are a few requirements to be fulfilled which are:
At all times, you want to have the best candidate you have seen so far.
Whenever you interview a candidate and feel that the candidate is better than your current assistant, you have to fire the
current assistant and then hire the candidate.

32. Probabilistic Analysis..
Let us have a look at the pseudo code to the model.
Hire-Assistant (n)
best<-0 ;Candidate 0 is a least qualified candidate
fori<-1 to n
do interview candidate i
if candidate i is better than candidate best
then best <-i
hire candidate i
Here are a few points to be considered for the Cost Model:
We are not concerned about the running time of the Hire-Assistant.
We must determine the total cost of hiring the best candidate.
If n candidates are interviewed and m candidates are hired, then the cost would be nci+mch
We have to pay the cost: ncito interview the candidates’ irrespective oof how many candidates we hire.
So, focus on analyzing the hiring cost mch
m varies with the order of the candidates.

33. Probabilistic Analysis..
Best-Case Analysis for Hiring Problem
We get the best case when the agency sends us the best applicant on the first day.
The cost would be nci+ch
Worst-case Analysis for Hiring problem
The worst case is when we hire all the n candidates.
This happens only if each candidate that comes later is better than all those who came before. That is
when candidates come in increasing order of quality.
The cost would be nci+nch
Whenever this happens, we will fire the agency.

34. Probabilistic Analysis..
Average-case Analysis for Hiring problem
For the average case, an input to the hiring problem is an ordering of the n applicants, there are n! different
inputs.
To use probabilistic analysis, we assume that the candidates arrive in random order.
Then we analyze our algorithm by computing an expected running time.
This expectation is taken over the distribution of all the possible inputs.
Thus, we are averaging the running time over all possible inputs.
Now, we want to know the expected cost of our hiring algorithm in terms of the number of times we hired an
applicant.
For this, Random variable X(s) is the number of applicants who are hired for a given input sequence s.
Indicator random variable Xi for applicant i will be 1 if applicant i is hired, 0 otherwise.

35. Probabilistic Analysis..
What is Indicator Random Variable?
It is a powerful technique that is used for computing the expected value of a random variable. Also, it is a convenient method for converting between
probabilities and also expectations. Indicator Random Variable takes only 2 values, which are 1 and 0.
Indicator Random Variable XA=I{A} for an event A of a sample space is defined as:
I{A} = 1 if A occurs
0 if A does not occur
The expected value of an indicator Random Variable is associated with an event A is equal to the probability that A occurs.
Indicator RV –Example
Problem: Determine the expected number of heads in one toss.
Sample space is s{H, T}
Indicator random variable
XA= I{ coin coming up with heads}=1/2
The expected number of heads obtained in one flip of the coin is equal to the expected value of the indicator random variable.
Therefore, E[XA] = 1/2
This is all about probabilistic analysis, Hiring problem, and the Indicator random variable. Do check the next article on Disjoint sets.

36. Amortized Analysis
This analysis is used when the occasional operation is very slow, but most of the operations which are
executing very frequently are faster. Data structures we need amortized analysis for Hash Tables, Disjoint
Sets etc.
In the Hash-table, the most of the time the searching time complexity is O(1), but sometimes it executes
O(n) operations. When we want to search or insert an element in a hash table for most of the cases it is
constant time taking the task, but when a collision occurs, it needs O(n) times operations for collision
resolution.
Aggregate Method
The aggregate method is used to find the total cost. If we want to add a bunch of data, then we need to find
the amortized cost by this formula.
For a sequence of n operations, the cost i

37. Amortized Analysis..
Let us consider an example of a simple hash table insertion. How do we decide table size? There is a trade-
off between space and time, if we make hash-table size big, search time becomes low, but space required
becomes high.

38. Amortized Analysis..
For the dynamic array, let = cost of ithinsertion.
The solution to this trade-off problem is to use Dynamic Table (or Arrays).
The idea is to increase size of table whenever it becomes full. Following are the steps to follow when table becomes full.
1) Allocate memory for a larger table of size, typically twice the old table.
2) Copy the contents of old table to new table.
3) Free the old table.
If the table has space available, we simply insert new item in available space.
What is the time complexity of n insertions using the above scheme?
If we use simple analysis, the worst case cost of an insertion is O(n). Therefore, worst case cost of n inserts is n * O(n) which is
O(n2). This analysis gives an upper bound, but not a tight upper bound for n insertions as all insertions don’t take Θ(n) time.