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