Design and Analysis of Algorithm
FALL 2024
Lecture No:01(A)
Introduction of Algorithms
Course Instructor: Ms. AQSA AQDUS
Today Topics
What is an algorithm
Properties of Algorithms
Algorithm’s Notations
2
At the End of Lecture
At the end of lecturer you will be able
To understand the features of algorithm
To understand the use of algorithm’s notation
How to design algorithms and Pseudo codes
3
What is an algorithm
An algorithm is a step by step procedure to solve a problem
– Plate form independent
– Can be implement in any procedural language
Simplest form (for experts) is Pseudo code
Pseudo code can be written in any language syntax, but here in this course we
will used C/C++ syntax
Two important factors
– Space Tradeoff (Refer to less use of memory i.e. RAM)
– Time Tradeoff (Refer to less time of Micro processor for execution)
4
Properties of algorithm
Complete
Finite
At least one Output
0,1 or more inputs
Correct
Clarity
5
An Algorithm (Example)
Algorithm SUM (No1, No2, Res)
{ This algorithm is used to read two numbers and print its sum }
Step-1 [ Read numbers No1 and No2]
Read(No1,No2)
Step-2 [Calculate the sum]
Res=No1+No2
Step-3 [Display the Result ]
Write(Res)
Step-4 {Finish]
C Language Program:
Exit
void main()
{
int no1, no2, res;
scanf(“%d%d”, &a, &b);
res = a+b;
printf(“Sum=%d”, res);
}
6
Algorithms Notations
Algorithm Name
– Should be in capital form
– Meaningful
Parameters
– Should be enclosed in parenthesis ( )
– Variable name comprises on more than one characters
– Scripting or looping variable are of single character
Introductory Comment
– Description and purpose of an algorithm
Steps
– Finite steps
7
Algorithms Notations (Cont !!!)
Comments
– Each step start with a comment
– Enclose in [ ]
– Define the purpose of step
Input Statements
– Read
– Scanf (if using C/C++)
Output statement
– Write
– Printf (if using C/C++)
8
Algorithms Notations (Cont !!!)
Selection statement
– If –Then –End If
– If – then ---Else --- End If
– Nested If
– Example
If ( a>b ) then
write ( a+”Is Large”)
Else
write ( b+”Is Large”)
End if
9
Algorithms Notations (Cont !!!)
Loops ( For, While, Until )
– Example-1 Note:- Purpose of
Repeat Step 2 For i=1, N, 1 all examples is
– Example-2 same i.e. to
Repeat Step 2 to Step 4 For i=1, N, 1 perform loop 10
– Example-3 times
Repeat Step 2 while i<=10
– Example-4
Repeat Step 2 Until i>10
10
Algorithms Notations (Cont !!!)
Finish
– Exit (Used in main algorithm)
– Return (Used in sub algorithm)
11
Example-1.
Write an algorithms or Pseudo code to read
two number and display the largest number.
12
Algorithm Example-1.
Algorithm LARGE(No1, No2, lar)
{ This algorithm is used to read two numbers and print the largest}
Step-1 [ Read numbers No1 and No2]
Read(No1,No2)
Step-2 [Find the largest]
if (No1 > No2) then
lar = No1
else
lar = No2
end if
13
Algorithm Example-1 (Cont !!!)
Step-3 [Display the Result ]
Write(lar)
Step-4 {Finish]
Exit
14
Algorithm Example-1 (Cont !!!)
Write the algorithms convention which are use in Example-1.
Algorithm Name (Large )
Parameters (No1, No2 and lar)
Input and Output Statement(Read, Write)
Selection Statement (if-else)
Comments (enclosed in [ ] before start of each step)
Introductory comments (enclosed in { } )
Finish (exit)
15
Pseudo code Example-1 (Cont !!!)
Large (a,b, lar)
{
// Find the largest number
if (a>b)
lar=a;
else
lar=b;
}
16
Example-2.
Write an algorithms or Pseudo code to read an
array of N integer values, calculate its sum and
then print the sum
17
Algorithm Example-2.
Algorithm SUM(Ary[ ], I, total, N)
{ This algorithm is used to read an array Ary of size N
and display its sum }
Step-1 [ Perform a loop to read the values of array]
Repeat step 2 for i=1,N,1
Step-2 [Read value ]
Read(Ary[i])
Step-3 [Initialize variable I and total]
a. I =1
b. total = 0
Step-4 [ Perform a loop to traverse the all elements of
array ary and add]
18
Repeat step 5 while i<=10
Algorithm Example-2 (Cont !!!)
Step-5 [Add the values]
total = total + ary [ I ]
Step-6 {Display the sum of values]
Write (total)
Step-7 {Finish]
Exit
19
Algorithm Example-2 (Cont !!!)
Write the algorithms convention which are use in Example-2.
Algorithm Name (SUM)
Parameters (ary[], I, N, total)
Input and Output Statement (Read, Write)
Loop Statement (for, while)
Assignment
Comments (enclosed in [ ] before start of each step)
Introductory comments (enclosed in { } )
Finish (exit)
20
Pseudo code Example-2(Cont !!!)
Large (Ary, N, I, Total)
{
for(i=0;i<=N-1;i++)
scanf(“%d”, Ary[i]);
i=0; total=0;
while(i<=N-1)
total=total+ Ary[i];
printf(“%d”, total);
}
21
Example-3.
Write an algorithms or Pseudo code to find the
factorial of number N using sub algorithm
approach.
22
Algorithm Example-3.
Algorithm FACTORIAL( No, Res)
{ This algorithm is used to read a number No and print its factorial }
Step-1 [ Read the number No]
Read (No)
Step-2 [Call Sub algorithm FACT]
SubAlgorithm FACT( NewNo, I, f)
Call Res = FACT(No) { This Sub algorithm is used to
Step-3 [ Display factorial ] receive an element from main
Write (Res) algorithm FACORIAL and return the
Step-4 [ Finish ] result }
Exit
Step 1. [ Initialize variable ]
f =1
Step2. [ Perform loop to calculate
factorial]
Repeat step 3 for i=1, NewNo, 1
Step 3. [Calculate f ]
f=f*I
Step 4 [ Finish ]
23 return ( f)
Algorithm Example-3 (Cont !!!)
Write the algorithms convention which are use in Example-3.
Algorithm Name (FACTORIAL)
Sub Algorithm Name (FACT)
Parameters of FACTORIAL (No, Res)
Parameters of FACT (NewNo, F, I)
Input and Output Statement (Read, Write)
Loop Statement (for, while)
Assignment
Comments (enclosed in [ ] before start of each step)
Introductory comments (enclosed in { } )
Finish (exit, return)
24
Pseudo code Example-3(Cont !!!)
Facorial(No, Res)
{
Res= Fact (No)
Printf(“%d”, Res)
Fact(NewNo)
}
{
for(i=1;i<=N;i++)
F=F* I
Return(f)
}
25
Summary
An algorithm is a step by step process to solve a problem.
An algorithm is platform Independent and you can make a computer program in any
language.
No of Inputs, outputs, completeness, accuracy , correctness and finite are the main
features of algorithms
Algorithms notation are used to design an algorithm
Pseudo code are used by experts
26