Design and Analysis of Algorithm

FALL 2024

Lecture No:01(B)
Introduction of Algorithms

Course Instructor: Ms. AQSA AQDUS

Expressing Algorithms

 English description
More easily More
expressed  Pseudocode precise

 High-level
programming
language
Analysis of algorithms

 Why analyze algorithms?

– evaluate algorithm performance
– compare different algorithms
 Analyze what about them?
– running time, memory usage, solution quality
– worst-case and “typical” case
 Computational complexity
– Classifying problems according to difficulty level
– algorithms provide upper bound scenario

3
Analysis of algorithms (Cont !!!)

– to show problem is hard or complete

– It requires at least a given amount of resources
– Transform problems to establish “equivalent” difficulty

4
What is the "best" Algorithm

 You can considered an algorithm best on the base answers of following questions.
– How fast does it run?
Refer to processing time
– How "complicated" is the algorithm
Time Complexity
Space Complexity
– How well is the algorithm documented
Written pseudo code should be clear , complete and well documented
– Can the machine used have influence on the results
Yes
Some good algorithms can not perform well on slow machines.

5
Important Point to note

 Programs depend on the operating systems, machine, compiler/interpreter used, etc.

 Analysis of algorithms compare algorithms and not programs.

 Performance of Algorithms should be measured before its implementation as program in any

language.
 Algorithms should be checked on different machines.

6
Example-1.

 Consider following four pseudo codes (in C)

 Purpose of all pseudo codes is same.

 We are analysing them on the base do time and space trade-off factors

7
PesuedoCode-1.
main()
{
Int a,b,c;
a=2;
b=3;
c=a+b; Facts:
printf(“%d”, c);
} 1.Three variables ( 6
bytes)
2.Three assignment
process
3.One Calculation
4.One output
statement

8
PesuedoCode-2.
main()
{
int a,b;
a=2;
b=3;
printf(“%d”, a+b); Facts:
}
1.Two variables ( 4
bytes)
2.Two assignment
process
3.One Calculation
4.One output
statement

9
PesuedoCode-3.
main()
{
int a,b,c;
scanf(“%d%d”, &a, &b);
c=a+b;
printf(“%d”, c); Facts:
}
1.Three variables ( 6
bytes)
2.One input
statement
3.One Assignment
4.One Calculation
5.One output
statement

10
PesuedoCode-4.
main()
{
int a,b;
scanf(“%d%d”, &a, &b);

}
printf(“%d”, a+b);
Facts:
1.Two variables ( 4
bytes)
2.One input
statement
3.One Calculation
4.One output
statement

11
Comparison of Pseudo codes

Facts Pseudo 1 Pseudo 2 Pseudo 3 Pseudo 4

Variables 3 (6 bytes) 2(4 bytes) 3 (6 bytes) 2 (4bytes)

No of 3 2 1 0
Assignments

No of 1 1 1 1
Calculation

Input 0 0 1 1
Statements

Output 1 1 1 1
Statements

12
Which one Pseudo code is best and
how?

 With respect to space trade of Pseudo code 2 and Pseudo code 4 are candidate for best
because in these pseudo codes 2 variables are used.
 But when focus on time tradoff/complexity then Pseudo 2 code will best
 Why not Pseudo code 4 is best though, you are entering dynamic data (through scanf )
– Because Some instruction access by microprocessor and some are executed by IO circuit of computer system.
– Switching between IO and Microprocessor takes extra time

13
Example-2. Pseudo code about
finding swapping the position of two
digits number
main()
{
int N,a,b;
N=54;
a= N/10;
b=N%10 Facts:
N = b*10+a

}
printf(“%d”, N); 1.variables ?
2.input statement ?
3.Calculation ?
4.output
statement ?
5.Assignments ?

14
Example-2. Pseudo code about
finding swapping the position of two
digits number (Cont!!!)

Facts:
1.variables ? 3 (6 bytes)
2.input statement ? 0
3.Calculation ? 3
4.output statement ? 1
5.Assignments ? 3

15
Example-2. Pseudo code about
finding swapping the position of two
digits number (Cont!!!) (Second
Pseudo code)
main()
{
int N=54;
N = (N%10)*10 + (N/10)

}
printf(“%d”, N);
Facts:
1.variables ?
2.input statement ?
3.Calculation ?
4.output
statement ?
5.Assignments ?

16
Example-2. Pseudo code about
finding swapping the position of two
digits number (Cont!!!)

Facts:
1.variables ? 1 (2 bytes)
2.input statement ? 0
3.Calculation ? 1
4.output statement ? 1
5.Assignments ? 1

17
Summary

 An algorithm or pseudo code will be

considered best if it full fill the time
and space trade off/ complexities.
 Performance of algorithm should be
measured and not of implemented
program.
 During writing algorithm or pseudo
code, you have to focus over the
extra use of data structure and
switching of instructions form CPU to
18 IO circuits and vise versa.