02-03-2017

What is Algorithm?

 Name of a Persian mathematician Abu Jafar

Mohammed Ibn Musa Al Khowarizmi (ninth
century).

 Finite set of instructions that accomplishes a

particular task. (or)
 sequence of unambiguous instructions for solving a
problem

Characteristics:- Process for Design and Analysis of Algorithm

Understand the problem

Solution as an algorithm

 input Algorithm Design

 output technique
 definiteness: clear and unambiguous
 finiteness: terminate after a finite number of Prove Correctness
No
steps Yes
 effectiveness: instruction is basic enough to Analyse the algorithm
No
be carried out is it efficient
Yes

Code the algorithm

Fig: Process for design and analysis of algorithms

1
 02-03-2017

Algorithm Types Issues for Algorithm

• Approximate Algorithm: If it is infinite and repeating. 1. How to devise algorithm

2. How to express algorithm
• Probabilistic algorithm: If the solution of a problem is 3. How to validate algorithm
uncertain. Ex: Tossing of a coin. 4. How to analyze algorithm
5. How to test a program
• Infinite Algorithm: An algorithm which is not finite. i) Debugging
Ex: A complete solution of a chessboard, division by ii) Profiling (or) Performance Measuring
zero.

• Heuristic algorithm: Giving fewer inputs getting more

outputs. Ex: All Business Applications.

Specification of Algorithm Pseudo-Code for Expressing Algorithms

1. Comments begin with // and continue until the end of line.
Using natural language
2.A block of statements / compound statements are
Pseudocode represented using { and } for example if statement, while
loop, functions etc.,.
Example
Algorithm {
Statement 1;
Flow chart Statement 2;
.........
.........
Program (Using programming language) }

[Link] delimiters [;] are used at the end of the each statement.

2
 02-03-2017

Contd….. Contd…..
4. An identifier begins with a letter. Example: sum, 7. The conditional statement if-then or if-then-else is
sum5, a; but not in 5sum, 4a etc.,. written in the following form.
If (condition) then (statement)
5. Assignment of values to the variables is done using If (condition) then (statement-1) else (statement-2)
the assignment operators as := or . If a condition is true the particular block of
statements are execute.
6. A There are two Boolean values TRUE and FALSE. Example
Logical operators: AND, OR, NOT. if(a>b) then
{
Relational operators: <, , ≥,,=,.
write("a is big");
Arithmetic operators: +, -, *, /, %; }
else
{
write("b is big");
}

Contd….. case
Contd….. while <condition> do Example:
{ { i:=1;
<statement 1> while(i<=10)do
8. The Case statement :(condition -1): (statement-1) While <statement 2> {
:(condition -2): (statement-2)
........ write (i);//displaying numbers from 1 to 10
:(condition -n): (statement-n)
........ i:=1+1;
..............
<statement n> }
..............
}
else :(statement n+1);
}
Repeat -until
9. Loops for repeat Example
{ i:=1;
for variable:=value 1 to value n step do Example:
{ <statement 1> repeat
for i:=1 to 10 do
Statement -1; { <statement 2> {
Statement -1; write(i); //displaying numbers from 1 to 10 ...... write (i);
....... i:=i+1; ...... i:=i+1;
....... } <statement n> }
Statement -n;
} }until <condition> until (i>10);

3
 02-03-2017

Contd….. Contd…..
10. Break: this statement is exit from the loop. 13. Compound data-types can be formed with records
11. Elements of array are accessed using [ ].
Ex: if A is an one-dimensional array, then A[i]. If A
Example
is two-dimensional array, A[i,j]. Name = record
{ Employee =record
12. Procedures (functions): data-type -1 data 1; {
Syntax:
data-type -2 data 2; int no;
procedure name of the procedure data-type -n data n; char name[10];
} float salary;
Algorithm Name (<parameter list>)
}
Syntax: {
body of the procedure
}

Performance Analysis:
Need for analysis Complexity
 To determine resource consumption
 CPU time
 A measure of the performance of an algorithm
 Memory space
 Compare different methods for solving the same
 An algorithm’s performance depends on
problem before actually implementing them
 internal factors
and running the programs.
 external factors
 To find an efficient algorithm

4
 02-03-2017

External Factors
 Speed of the computer on which it is run Two ways of finding complexity
 Quality of the compiler
 Experimental study
 Size of the input to the algorithm
 Theoretical Analysis
Internal Factor
 The algorithm’s efficiency, in terms of:
 Time required to run
 Space (memory storage)required to run

Note:
Complexity measures the internal factors (usually
more interested in time than space)

Experimental study Limitations of Experiments

 Write a program implementing the algorithm  It is necessary to implement the algorithm, which may
 Run the program with inputs of varying size and be difficult.
composition  Results may not be indicative of the running time on
 Get an accurate measure of the actual running time other inputs not included in the experiment.
Use a method like [Link]()  In order to compare two algorithms, the same
 Plot the results
hardware and software environments must be used.
 Experimental data though important is not sufficient.

5
 02-03-2017

Theoretical Analysis
Space Complexity
 The space needed by an algorithm is the sum of a fixed part and a
variable part.
 Uses a high-level description of the algorithm instead  Space complexity S(P) = C + Sp (Instance characteristics)
of an implementation
 Characterizes running time as a function of the input  The fixed part includes space for
 Instructions
size, n.
 Simple variables
 Takes into account all possible inputs  Fixed size component variables
 Allows us to evaluate the speed of an algorithm  Space for constants, Etc..
independent of the hardware/software environment
 The variable part includes space for
 Component variables whose size is dependant on the particular problem
instance being solved
 Recursion stack space, Etc..

Examples Time Complexity

Algorithm NEC (float x, float y, float z)  The time complexity of a problem is
{  the number of steps that it takes to solve an instance of the
Return (X + Y +Y * Z + (X + Y +Z)) /(X+ Y) + 4.0; problem as a function of the size of the input (usually measured
in bits), using the most efficient algorithm.
}
 Priori analysis or compile time
 Posteriori analysis or run (execution) time.
Algorithm ADD ( float [], int n)
 Time complexity T(P) = C + TP(n)
{
 In general it can be two measured in ways:
sum := 0.0;
 By using equation count method.
for i:=1 to n do
 Example: TP(n) = CaADD(n)+ CsSUB(n)+ CmMUL(n)+
sum:=sum + X[i]; CdDIV(n)+……………..
return sum;  By using step count method.
}

6
 02-03-2017

Contd…. Contd….
2. Global variable count method:  Step count method have two approaches:
1. Global variable count method:
Statement S/e Frequency Total steps
Ex:
Example: Algorithm sum with count statement added
1. Algorithm Sum(a, n) 0 - 0
count:=0;
2. { 0 - 0 Algorithm Sum(a, n) Algorithm Sum(a,n)
{ {
3. s:=0; 1 1 s:=0;
1 s:=0;
4. for i:=1 to n do
count:=count+1;
1 n+1 n+1
for i:=1 to n do for i:=1 to n do
5. s:=s+a[i]; 1 n n { {
count:=count +1;
6. return s; 1 1 1 s:=s+a[i]; s:=s+a[i];
count:=count+1;
7. } 0 - 0
} }
count:=count+1; //for last time of for loop
count:=count+1; //for return statement
Total 2n+3 steps
return s; return s;
} }
Thus the total number of steps are 2n+3

Time complexity cases Asymptotic Notation

 Best Case: Inputs are provided in such a way that the  The exact number of steps will depend on exactly what
minimum time is required to process them. machine or language is being used.
 Average Case: The amount of time the algorithm takes  To avoid that problem, the Asymptotic notation is
on an average set of inputs. generally used.
 Worst Case: The amount of time the algorithm takes
on the worst possible set of inputs.  Running time of an algorithm as a function of input
size n for large n.
Example: Linear Search
 Expressed using only the highest-order term in the
3 4 5 6 7 9 10 12 15
expression for the exact running time.

A 1 2 3 4 5 6 7 8 9

7
 02-03-2017

Big - Oh notation: (O) Big - Omega notation: 

Let f(n) and g(n) be the two Let f(n) and g(n) be the two non-
non-negative functions. We say negative functions. We say that f(n)
that f(n) is said to be O(g(n)) if is said to be (g(n)) if and only if
and only if there exists a positive there exists a positive constant ‘c’
constant ‘c’ and ‘n0‘ such that, and ‘n0‘ such that, f(n) ≥ c*g(n) for
f(n)c*g(n) for all non-negative all non-negative values of n, where
values of n, where n≥n0. n≥n0.

Here, g(n) is the upper bound Here, g(n) is the lower bound for
for f(n). f(n).

Ex: --- Ex: ---

Big - Theta notation: 

Let f(n) and g(n) be the Amortized Analysis
two non-negetive functions. We
 Not just consider one operation, but a sequence of
say that f(n) is said to be (g(n)) operations on a given data structure.
if and only if there exists a  Average cost over a sequence of operations.
positive constants ‘c1’ and ‘c2’,
such that, c1g(n)  f(n)  c2g((n)  Probabilistic analysis:
for all non-negative values n,  Average case running time: average over all possible inputs for one
where n ≥ n0. algorithm (operation).
The above definition  If using probability, called expected running time.

states that the function f(n) lies

 Amortized analysis:
between ‘c1’times the function  No involvement of probability
g(n) and ‘c2’, times the function  Average performance on a sequence of operations, even some
g(n) where ‘c1’ and ‘c2’ are operation is expensive.
positive constants.  Guarantee average performance of each operation among the
sequence in worst case.

Ex: ---

8
 02-03-2017

Three Methods of Amortized Analysis Aggregate Analysis

 In fact, a sequence of n operations on an initially empty
 Aggregate analysis: stack cost at most O(n). Why?
 Total cost of n operations/n,

Each object can be POP only once (including in MULTIPOP) for each
 Accounting method: time it is PUSHed. #POPs is at most #PUSHs, which is at most n.
 Assign each type of operation an (different) amortized cost
 overcharge some operations,
 store the overcharge as credit on specific objects, Thus the average cost of an operation is O(n)/n = O(1).
 then use the credit for compensation for some later operations.

 Potential method: Amortized cost in aggregate analysis is defined to be average cost.

 Same as accounting method
 But store the credit as “potential energy” and as a whole.

Amortized Analysis: Accounting Method Accounting Method (cont.)

 Idea:  Conditions:
 Assign differing charges to different operations.  suppose actual cost is ci for the ith operation in the
 The amount of the charge is called amortized cost.
sequence, and amortized cost is ci',
 amortized cost is more or less than actual cost.  i=1n ci' i=1n ci should hold.
 When amortized cost > actual cost, the difference is  since we want to show the average cost per operation is small
saved in specific objects as credits. using amortized cost, we need the total amortized cost is an
upper bound of total actual cost.
 The credits can be used by later operations whose
 holds for all sequences of operations.
amortized cost < actual cost.
 Total credits is i=1n ci' - i=1n ci , which should be
 As a comparison, in aggregate analysis, all
nonnegative,
operations have same amortized costs.
 Moreover, i=1t ci' - i=1t ci ≥0 for any t>0.

9
 02-03-2017

Distinguish between Algorithm and Pseudocode.

The Potential Method
• An algorithm is a well-defined sequence of steps that
 Same as accounting method: something prepaid is provides a solution for a given problem, while a pseudocode
used later. is one of the methods that can be used to represent an
algorithm.
 Different from accounting method • Algorithms can be written in natural language, pseudocode
 The prepaid work not as credit, but as “potential energy”, is written in a format that is closely related to high level
or “potential”. programming language structures.
 The potential is associated with the data structure as a • Pseudocode does not use specific programming language
whole rather than with specific objects within the data syntax and therefore could be understood by programmers
structure. who are familiar with different programming languages.
• Transforming an algorithm presented in pseudocode to
programming code could be much easier than converting an
algorithm written in natural language.

Big-Oh vs Big-Omega Matrix Multiplication (STEP COUNT)

 Big oh notation is denoted by ‘O’, whereas Omega notation void multiply(int A[][N], int B[][N], int C[][N])
is denoted by ‘’.
{
 Big oh is used to represent the upper bound of an Step 1: for (int i = 0; i < N; i++)
algorithm’s running time, i.e. we can give largest amount of {
time taken by the algorithm to complete. But whereas Step 2: for (int j = 0; j < N; j++)
omega notation represent the lower bound of an {
algorithm’s running time, i.e. we can give smallest amount Step 3: C[i][j] = 0;
of time taken by the algorithm to complete. Step 4: for (int k = 0; k < N; k++) \
 Let f(n) and g(n) be the two non-negative functions. We {
say that f(n) is said to be O(g(n)) if and only if there exists a Step 5: C[i][j] += A[i][k]*B[k][j];
positive constant ‘c’ and ‘n0‘ such that, f(n)c*g(n) for all }
non-negative values of n, where n≥n0. But whereas }
function f(n)= (g(n)) (read as for of n is omega of g of n) }
if and only if there exist positive constants ‘c’ and ‘n0’ such }
that, f(n) ≥ c*g(n) for all n, n≥n0.

10