Algorithms
FINAL
MO3AZ SAIF
Introduction to algorithms
What is an algorithm ?
A step-by-step process will be designed to solve the problem.
Algorithm must be ?
Correctness : Returns a correct output for every problem input.
Efficient : The minimal cost of the computational resources used by the algorithm.
What is the characteristics of an algorithm ?
Each step must be exact : Precisely described.
Algorithm Must be :
▪ Terminate : Contain a finite number of steps.
▪ Effective : Provide the correct answer to the problem.
▪ General : Solve every instance of the problem.
MO3AZ SAIF
Components of an algorithm ?
▪ Variables ▪ Documentation ▪ Selections
▪ Instructions ▪ Procedures ▪ Repetitions
What is the relationship between data and algorithm ?
The algorithm processes data to make it meaningful, the algorithm provides the logic, and the data provides
the values. this relationship is expressed as:
Program = algorithm + data structures
Design and analysis of algorithms ?
Analysis : Calculate the cost of the algorithm in terms of resources and performance.
Design : Design an algorithm at the minimize cost.
MO3AZ SAIF
Algorithm Design
What is Flowchart ?
A visual way of representing by diagrams that uses shapes, lines, and arrows to sequence steps.
Start & End Process Input & Output Conditions (IF) Directions
Oval Rectangle Parallelogram Diamond Arrows
What is Pseudocode ?
A description of the algorithm steps using a mixture of programming languages and English statements.
Pseudo-code differs from real code with ?
it disregards software engineering concerns and ignore issues related to data abstraction and error handling.
MO3AZ SAIF
Algorithm Analysis
What is algorithm efficiency ?
The amount of time and space resources required to execute it.
What is Time & Space complexity ?
Time Complexity : Relation between input size and taken time to solve the problem.
Space Complexity : Relation between input size and used space to solve the problem.
BIG-O Notation ?
- A mathematical notation that describes the complexity of your code.
Constant Logarithmic Linear Loglinear Polynomial Exponential Factorial
O( 1 ) O( log(n) ) O( n ) O( n log(n) ) O( 𝑛𝑎 ) O( 𝑎𝑛 ) O( n! )
MO3AZ SAIF
Recursive Function
What is Recursion ?
A function that calls itself directly or indirectly to solve a problem. It contains two cases:
Base Case ( Solution statement ) General Case ( Recursive function call )
Greatest Common Divisor ( GCD )
Brute Force Euclid’s Algorithm Recursive Method
function gcd(a, b): function gcd(a, b): function gcd(a, b):
gcd = 1 while b is not 0: if b = 0:
s = min(a, b) r=a%b return a
for i from 1 to s : a=b else:
b=r return gcd(b, a % b)
if a % i == 0 and b % i == 0:
return a
gcd = i
return gcd
) ده مثال الدكتور اتكلم فيه كتير مش القي ليه اي اهمية غير كان عايز يوصل ازاي ممكن نحسن الكود بطرق مختلفة (الجوريزم مختلف MO3AZ SAIF
FLOWCHART &
PSEUDOCODE
MO3AZ SAIF
Q1: Write an algorithm and draw a flowchart to sum two numbers.
Pseudocode Flowchart
START
READ n1,n2 Start
SET Sum n1+n2
PRINT Sum Read n1 , n2
END
Sum = n1 + n2
Print Sum
End
MO3AZ SAIF
Q2: Write an algorithm and draw flowchart to calculate area of rectangle the length L ,
and the width of the rectangle W.
Pseudocode Flowchart
START
READ L , W Start
SET Area L * W
PRINT Area Read L , W
END
Area = L * W
Print Area
End
MO3AZ SAIF
Q3: Write an algorithm and draw a flowchart to find the average of 3 integers.
Pseudocode Flowchart
START
READ n1,n2,n3 Start
SET Avg (n1+n2+n3)/3
PRINT Avg Read n1, n2 , n3
END
Avg = (n1 + n2 + n3 ) / 3
Print Avg
End
MO3AZ SAIF
Q4: Write an algorithm and draw a flowchart to find the largest of two numbers.
Pseudocode Flowchart
START
READ a , b Start
IF a > b THEN
PRINT a Read a , b
ELSE
PRINT b YES NO
a>b?
END IF
END
Print a Print b
End
MO3AZ SAIF
Q5: Write an algorithm and draw a flowchart to find the largest of three numbers.
Pseudocode Flowchart
START
Start
READ a , b , c
IF a >= b AND a >= c THEN Read a, b , c
PRINT a
ELSE NO
YES a >= b &&
IF b >= a AND b >= c THEN a >= c ?
b >= a &&
PRINT b b >= c ?
NO
ELSE
Print c YES
PRINT c
Print a Print b
END IF
END IF End
END
MO3AZ SAIF
Q6: Write an algorithm and draw flowchart to print natural numbers from 1 to 100.
Pseudocode Flowchart
START
SET i 1 Start
WHILE i <= 100 DO
PRINT i i=1
SET i i + 1
YES NO
END WHILE i <= 100 ?
END
Print i
i=i+1
End
MO3AZ SAIF
Q7: Write an algorithm and draw flowchart to print natural numbers from 1 to 100.
Pseudocode Flowchart
START
SET i 0 , Sum 0 Start
WHILE i <= 100 DO
SET Sum Sum + i i = 0 , Sum = 0
SET i i + 1
END WHILE YES NO
i <= 100 ?
PRINT Sum
END Sum = Sum + i Print Sum
i=i+1
End
MO3AZ SAIF
Q8: Write an algorithm and draw a flowchart to print even numbers from 16 to 48.
Pseudocode Flowchart
START
SET i 16
Start
WHILE i <= 48 DO
PRINT i
i = 16
SET i i + 2
END WHILE YES NO
i <= 48 ?
END
Print i
i=i+2
End
MO3AZ SAIF
Q9: Write an algorithm and draw a flowchart to calculate sum of the age of student and
print sum and average.
Pseudocode Flowchart
START Start
READ n
SET i 1 , Sum 0 Read n
WHILE i <= n DO
i = 1 , Sum = 0
READ Age
SET Sum Sum + Age
YES NO
i <= n ?
SET i i + 1
Read Age
END WHILE Avg = Sum / n
SET Avg Sum / n Sum = Sum + Age
Print Sum , Avg
PRINT Sum , Avg
i=i+1
END End
MO3AZ SAIF
Q10: Write an algorithm and draw a flowchart to find factorial of n.
Pseudocode Flowchart
START
Start
READ n
SET i 1 , Fact 1 Read n
WHILE i <= n DO
i = 1 , Fact = 1
SET Fact = Fact * i
SET i i + 1
YES NO
i <= n ?
END WHILE
PRINT Fact Fact = Fact * i
Print Fact
END
i=i+1
End
MO3AZ SAIF
TIME
COMPLEXITY
MO3AZ SAIF
EXAMPLE ( 1 ) :
Public int sum(int n){
int total;
total=n*(n+1)/2 ;
Return total;
}
F(n) = 1 + 1 = 2
O( F(n) ) = O(1)
MO3AZ SAIF
EXAMPLE ( 2 ) :
Public int sum (int n) {
int i , total;
total = 0;
For( i=1 ; i <= n ; i++ ){
total = total + i ;
}
Return total ;
}
F(n) = 1 + ( n + 1 ) + n + 1 = 2n + 3
O( F(n) ) = O(n)
MO3AZ SAIF
EXAMPLE ( 3 ) :
X=0;
for(int i = -2 ; i < n ; i++){
x=x+i;
y=x+2;
}
Print(x);
F(n) = 1+n+3+n+2+n+2+1= 3n+9
O( F(n) ) = O(n)
MO3AZ SAIF
EXAMPLE ( 4 ) :
Public int sum() {
int i , total;
total = 0 ;
for( i = 1 ; i <= 20 ; i++){
total = total + i ;
}
Return total ;
}
F(n) = 1 + 21 + 20 + 1 = 43
O( F(n) ) = O(1)
Execution time depends on the input size , no input in this code !
MO3AZ SAIF
EXAMPLE ( 5 ) :
int func(a[] ,n ){
int x = 5;
for(int i = 1 ; i <= n ; i++ ){
for(int j = 1 ; j < n ; j++ )
x=x+i+j;
print(x)
}
}
}
F(n) = 1+ n+1+ n*n + n(n-1)+ n(n-1) = 3𝒏𝟐 - n + 2
O( F(n) ) = O( 𝒏𝟐 )
MO3AZ SAIF
SORTING
ALGORITHMS
MO3AZ SAIF
Bubble Sort
The simplest sorting algorithm that works by repeatedly Example :
swapping the adjacent elements if they are in the wrong order.
3 1 4 2
Time Complexity in any case : O( 𝑛2 )
3 1 4 2 3 > 1 - Swap
Pseudocode : 1 3 4 2 3 > 4 - No Swap
1 3 4 2 4 > 2 - Swap
function bubbleSort(arr , n ):
for i from 0 to n-1: 1 3 2 4 1 > 3 - No Swap
for j from 0 to n-i-1: 1 3 2 4 3 > 2 - Swap
if arr[j] > arr[j+1]: 1 2 3 4 1 > 2 - No Swap
swap(arr[j], arr[j+1])
1 2 3 4
MO3AZ SAIF
Selection Sort
A simple sorting algorithm that works by repeatedly selecting Example :
the smallest element from the unsorted portion of an array and 3 1 4 2
Min = 3 3>1 => Min = 1
places it at the beginning. Min = 1 1>4 => Min = 1
Min = 1 1>2 => Min = 1
Time Complexity in any case : O( 𝑛2 )
Pass #1 : Min = 1 - Swap( 3 , 1 )
1 3 4 2
Pseudocode :
Min = 3 3 > 4 => Min = 3
Min = 3 3 > 2 => Min = 2
function selectionSort( arr , n )
Pass #2 : Min = 2 - Swap( 3 , 2 )
for i from 0 to n - 1
1 2 4 3
minIndex = i Min = 4 4 > 3 => Min = 3
for j from i+1 to n Pass #3 : Min = 3 - Swap( 4 , 3 )
if arr[j] < arr[minIndex] 1 2 3 4
minIndex = j
1 2 3 4
swap(arr[i], arr[minIndex])
MO3AZ SAIF
Insertion Sort
A sorting algorithm that works by considering one element at a Example :
time and inserting it into its correct position.
3 1 4 2
Time Complexity :
Best Case : O( n ) , [ array is already order ] 3 1 4 2
Worst Case : O( 𝑛2 ) , [ array in reversed order ] Shift element ( 3 ) and insert key (1)
into its correct position
Pseudocode :
1 3 4 2
function insertionSort(arr , n): No elements shifted and the key
for i from 1 to n: (4) is in the correct position
key = arr[i]
j=i-1 1 3 4 2
while j >= 0 and arr[j] > key: Shift elements ( 4 , 3 ) and insert
arr[j + 1] = arr[j] key (2) into its correct position
j=j-1
1 2 3 4
arr[j + 1] = key
MO3AZ SAIF
Pseudocode :
Merge Sort function MergeSort(arr , l , r ):
if l < r
A sorting algorithm that works by dividing an array into smaller m = ( l + r )/2
MergeSort(arr , l , m )
subarrays, sorting each subarray, and then merging the sorted MergeSort(arr , m+1 , r )
Merge(arr , l , m , r )
subarrays back together to form the final sorted array.
function Merge(arr , l , m , r ):
Time Complexity in any case : O( 𝑛 log(𝑛) ) n1 = m - l + 1 , n2 = r - m
left[n1] , right[n2]
for i from 0 to n1:
Example : left[i] = arr[l+i]
for j from 0 to n2:
3 1 4 2 right[j] = arr[m+j+1]
i=0,j=0,k=l
while i < n1 and j < n2
3 1 4 2
if left[i] <= right[j]
arr[k] = left[i] , i++
3 1 4 2 else
arr[k] = right[j] , j++
k++
1 3 2 4 while i < n1:
arr[k] = left[i] , i++ , k++
while j < n2:
1 2 3 4 arr[k] = right[j] , j++ , k++
MO3AZ SAIF
MISSION COMPLETED !
MO3AZ SAIF
