Data Structures And
Algorithms
Lecture 5
Expressing Algorithms
• English description
More easily expressed More precise
• Pseudocode
• 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
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
What is the "best" Algorithm
• You can considered an algorithm best on the base of 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.
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.
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
PesuedoCode-1
main()
{
Int a,b,c;
a=2;
b=3;
c=a+b;
printf(“%d”, c);
}
PesuedoCode-2
main()
{
int a,b;
a=2;
b=3;
printf(“%d”, a+b);
}
PesuedoCode-3.
main()
{
int a,b,c;
scanf(“%d%d”, &a, &b);
c=a+b;
printf(“%d”, c);
}
PesuedoCode-4
main()
{
int a,b;
scanf(“%d%d”, &a, &b);
printf(“%d”, a+b);
}
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 Statements 0 0 1 1
Output 1 1 1 1
Statements
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
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
N = b*10+a
printf(“%d”, N);
}
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
Example-2. Pseudo code about finding swapping the position of two
digits number (cont!!!)
main()
{
int N=54;
N = (N%10)*10 + (N/10)
printf(“%d”, N);
}
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
