Unit 2
Iterative Algorithm
• Iterative algorithm is a mathematical procedure that
uses an initial value to generate a sequence of
improving approximate solutions for a class of
problems, in which the ith approximation (called an
"iterate") is derived from the previous ones
2.1 GCD (Greatest common
divisor)
• The Greatest Common Divisor (GCD), also known as the
Highest Common Factor (HCF), is the greatest number
that divides a set of numbers without leaving a
remainder. For example, the GCD of 4 and 6 is 2, as it
divides both numbers and is the largest of all their
factors.
• The GCD of any two numbers is never negative or 0, and
the least positive integer common to any two numbers
is always 1.
Algorithm for GCD
1. Start
2. Read any two numbers m and n.
3. If n==0 , return the value of m as answer and stop.
4. If m==0, return the value of n as answer and stop.
5. Divide m % n and assign the value of remainder as r.
6. Assign the value of n to m and value of r to n.
7. Goto step 3.
8. Stop.
Pseudocode for GCD
GCD(m,n)
{ {
If (m==0); r = m%n;
Print” n as GCD”; m = n;
Elseif (n==0) n =r;
Print”m as GCD” }
Else Print “m as GCD”
{ }
While(n!=0) }
Analysis of GCD
• Since while loop executes at most n times so, time
complexity =O(n)
• In GCD space complexity (3 variables used to store data), so
space complexity =O(1)
Example . Find GCD of 33 and 12
Q A B R • Solution
m=33 , n=12
Iteration1:
2 33 12 9
r=33%12=9
m=n=12
1 12 9 3 n=r=9
Iteration2:
r=12%9=3
3 9 3 0
m=n=9
n=r=3
3 0 Iteration3:
r=9%3=0
m=n=3
n=r=0
Hence , GCD of 33 and 12 is 3
Class Work
•Find GCD of the following.
1.54 and 42
2.33 and 99
3.35 and 14
Fibonacci Number
• A Fibonacci number is a series of numbers in which
each Fibonacci number is obtained by adding the two
preceding numbers. It means that the next number in
the series is the addition of two previous numbers. Let
the first two numbers in the series be taken as 0 and
1. By adding 0 and 1, we get the third number as 1
Algorithm for Fibonacci number
1. Start
2. Set first_term = 0, Second_term =1, i=3;
3. Input the number of term of Fibonacci to be printed “say n”;
4. Print first_term , Second_term;
5. While(i<=n)
Temp=first_term+second_term;
first_term= second_term;
second_term=Temp;
6. Print the value of temp;
[Link].
Pseudocode for Fibonacci
series
Fibonacci(n)
{ {
ft=0; temp=ft+st;
st=1; ft=st;
st=temp;
i=2; ++i;
while (i<n) print “temp”
}
}
Analysis
• Time Complexity • Space Complexity
Since the while loop executer for n-2 The space complexity is constant .
times, sot time complexity is
Which gives O(1)
O(n)
Note:
Time Complexity is defined as order of Note:
growth of time taken in terms of input Space complexity is extra space
size rather than the total time taken. It (apart from input and output)
is because the total time taken also
depends on some external factors like
required for an algorithm.
the compiler used, the processor's
speed, etc.
THANK YOU
CLASS
Unit 2.2
Searching Algorithm
Searching is the fundamental
process of locating a specific
element or item within a collection
of data. This collection of data can
take various forms, such as arrays,
lists, trees, or other structured
representations.
Sequential Search (linear
Search)
• linear search or sequential search is a method for finding an element
within a list. It sequentially checks each element of the list until a
match is found or the whole list has been searched.
• In sequential search an array, arr[] of n integers, and an integer
element x is given, find whether element x is present in the array or
not. Return the index of the first occurrence of x in the array, or -1 if it
doesn't exist
Sequential search algorithm
1. Start
2. Read the search element from user
3. Compare the search element with the first element in the list
4. If both are matched, display “search successful” and stop.
5. If both are not matching then compare search with next element in the list.
6. Repeat step 4 and step 5 until the search element is compared with last
element in the array,
7. If last element in the array also do not match, then display “Search
unsuccessful” .
8. stop
Pseudo code
• Linear_search(A,n,key)
• {
• Flag=0;
• For(i=0;i<n;i++)
• {
• If(A[i]== key)
• Flag=1’
• }
• If(flag==1)
• Print “search successful”
• Else
• Print ”Search un-successful”
Pseudo code
Linear_search(A,n,key) • Analysis
{ • Time Complexity:
Flag=0; • Best Case: In the best case, the key might be
present at the first index. So, the best-case
For(i=0;i<n;i++) complexity is O(1)
{ • Worst Case: In the worst case, the key might
If(A[i]== key) be present at the last index i.e., opposite to
the end from which the search has started in
Flag=1’ the list. So, the worst-case complexity is O(n)
} where N is the size of the list.
If(flag==1) • Average Case: O(n/2)=O(n)
Print “search successful” • Space Complexity
Else Since array takes n memory space of space
complexity is =O(n)
Print ”Search un-successful”
Example:
Search data element 33 from following set of elements by using
sequential search. A[]={10,14,19,26,27,31,33,35,42,44}
10 14 19 26 27 31 33 35 42 44
=33
10 14 19 26 27 31 33 35 42 44
=33
.
.
.
10 14 19 26 27 31 33 35 42 44
=33
2.3
Sorting Algorithm
Sorting is the arrangement of data either in ascending order or
descending order. There are mainly two types of sorting
1. Internal sorting: it takes place within the main memory of computer
, it is applied to small amount of data.
2. External sorting: it is applied when large volume of data have to be
sorted in secondary memory
3. Sorting must consume less space and time and it should be easy to
learn and understand.
Bubble sort
• Bubble Sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in the wrong order. This algorithm
is not efficient for large data sets as its average and worst-case time
complexity are quite high.
• Sorts the array using multiple passes. After the first pass, the maximum goes
to end (its correct position). Same way, after second pass, the second largest
goes to second last position and so on.
• In every pass, process only those that have already not moved to correct
position. After k passes, the largest k must have been moved to the last k
positions.
• In a pass, we consider remaining elements and compare all adjacent and
swap if larger element is before a smaller element. If we keep doing this, we
get the largest (among the remaining elements) at its correct position.
Bubble sort algorithm
1. Start
2. For first iteration, compare all the elements (n), for subsequent
runs, compare (n-1) (n-2) and so on.
3. Compare each element with its right-side neighbors.
4. Swap the smaller element to the left.
5. Keep repeating steps 2 to 4 until whole list is covered
6. stop
Pseudo code for bubble sort
Bubblesort (A,n)
{
For (i=0;i<n-1;i++);
{
For(j=0;j<n-i-1; j++)
{
If(A[j]> A[i])
{
Temp=A[i];
A[i]=A[j+1];
A[j+1]= temp;
} } } }
Bubble sort analysis
• The best time complexity of bubble sort is O(n). The average and
worst time complexity is O(n2).
• The space complexity of bubble sort is O(n), because array A takes n
memory references.
Example.
• Sort the following data items using bubble sort
• A= [ 25, 57, 48, 37, 12, 92, 86, 33]
• Solution.
Array 0 1 2 3 4 5 6 7
position
Initial state 25 57 48 37 12 92 86 33
Pass 1 25 48 37 12 57 86 33 92
Pass 2 25 37 12 48 57 33 86 92
Pass 3 25 12 37 48 33 57 86 92
Pass 4 12 25 37 33 48 57 86 92
Pass 5 12 25 33 37 48 57 86 92
Pass 6 12 25 33 37 48 57 86 92
Pass 7 12 25 33 37 48 57 86 92
Pass 8 12 25 33 37 48 57 86 92
The sorted array is {12 ,25, 33, 37, 48, 57, 86, 92}
Note in bubble sort
#
number of pass is always equal to the number of data items.
2. Selection Sort
Selection sort is a sorting algorithm that repeatedly
finds the minimum element in the unsorted portion of
an array and swaps it with the element at the
beginning of the unsorted section. This process
continues until the entire array is sorted.
Algorithm for selection Sort
1. Start
2. Let the first element to be sorted and the rest to be unsorted
3. Assume the first element to be the smallest element
4. Check if the first element is smaller then each of the other elements
1. If yes , do nothing
2. If no, choose the other smaller element as minimum and repeat step 3.
5. After completion of one iteration through the list, swap the smallest element
with the first element of the list
6. Now consider the second element in the list to be smallest and so on till all the
elements in the list are covered.
7. Stop.
Pseudo code for selection sort
SelectionSort (A, n)
{
for(i=0; i<n; i++)
{
Least= A[i]
p=i;
for (j=i+1;J<n; j++) {
if(A[j]<A[i]
{
Least=A[i]
p=j; } }
Swap(A[i],A[p]); } }
Analysis of selection sort
• Inner loop executes for (n-1) times so
• time complexity= (n-1)+(n-2)+(n-3)……..+3+2+1= O(n2)
• Space complexityArray A takes n memory space = O(n)
Example : sort the following data items by using selection sort
A[]= { 25, 57, 48, 37, 12, 92, 86, 33}
Array 0 1 2 3 4 5 6 7
position
Initial stage 25 57 48 37 12 92 86 33
Pass 1 12 57 48 37 25 92 86 33
Pass 2 12 25 48 37 57 92 86 33
Pass 3 12 25 33 37 57 92 86 48
Pass 4 12 25 33 37 57 92 86 48
Pass 5 12 25 33 37 48 92 86 57
Pass 6 12 25 33 37 48 57 86 92
Pass 7 12 25 33 37 48 57 86 92
Pass 8 12 25 33 37 48 57 86 92
3. Insertion Sort
• Insertion sort is a simple sorting algorithm that works by
iteratively inserting each element of an unsorted list into its
correct position in a sorted portion of the list. It is like sorting
playing cards in your hands. You split the cards into two
groups: the sorted cards and the unsorted cards. Then, you
pick a card from the unsorted group and put it in the right
place in the sorted group.
Algorithm for insertion sort:
1. Start
2. If it is the first element, consider it is already sorted.
3. Compare with second element
a) If the second element <the first element , insert the element in correct
position of the sorted portion,
b) Else, leave it as it is.
4. Repeat steps 2 and 3 until all elements are sorted.
5. Stop.
Pseudo code for insertion sort
Insertionsort( A,n)
{
For(i=1; i<n; i++)
{
Temp=A[i]
J=i-1
While(j>=0 && A[j]>temp)
{
A[j+1]=A[j]
J=j-1
}
}
A[j+1]= temp
}
Analysis of insertion sort
Time complexity= O(n2)
space complexity= O(n)
# Insertion sort is generally quicker to execute than bubble sort,
especially on large data sets. Both insertion sort and bubble sort do not
take up much extra memory since both algorithms use the original list
of items when executing.
Example: Sort following data items using insertion sort
A[] = {25, 57, 48, 37, 12, 92, 86, 33}
Solution:
6 0 1 2 3 4 5 6 7
Initial stage 25 57 48 37 12 92 86 33
Pass 1 25 57 48 37 12 92 86 33
Pass 2 25 57 48 37 12 92 86 33
Pass 3 25 48 57 37 12 92 86 33
Pass 4 25 37 48 57 12 92 86 33
Pass 5 12 25 37 48 57 92 86 33
Pass 6 12 25 37 48 57 92 86 33
Pass 7 12 25 37 48 57 86 92 33
Pass 8 12 25 33 37 48 57 86 92
End of chapter 2
Thank You