GANGA INSTITUTE OF TECHNOLOGY

AND MANAGEMENT, KABLANA

DEPARTMENT OF COMPUTER SCIENCE & APPLICATIONS

Software Lab: 7
Based on 21MCA24C1

Submitted To: Submitted By:

Name:

Roll no:
 INDEX
Sr.
Title Date Signature
No.

1 Write a Program in Python to Compute the GCD of two

numbers.

2 Write a Program in Python to find the square root of a

number by using Newton’s Method.

3 Write a Program in Python to find the Power of a Number.

Write a Program in Python to find the Maximum of a list of

4 Numbers.

5 Write a Program in Python to Implement Linear Search.

6 Write a Program in Python to Implement Binary Search.

7 Write a Program in Python to Implement Selection Sort.

8 Write a Program in Python to Implement Insertion Sort.

9 Write a Program in Python to Implement Merge Sort.

10 Write a Program in Python to find first n Prime Numbers.

EXPERIMENT NO. 1

AIM: To Compute the GCD of two numbers

REQUIREMENTS: PC with window operating system and PYTHON software.
THEORY:

The greatest common divisor (GCD) of two or more numbers is the greatest common factor
number that divides them, exactly. It is also called the highest common factor (HCF). For
example, the greatest common factor of 15 and 10 is 5, since both the numbers can be divided by
5.
15/5 = 3
10/5 = 2
If a and b are two numbers then the greatest common divisor of both the numbers is denoted by
gcd(a, b). To find the gcd of numbers, we need to list all the factors of the numbers and find the
largest common factor.

PYTHON CODE

%Programto Compute the GCD of two numbers

num1 = int(input("Enter First Number: "))
num2 = int(input("Enter Second Number: "))
i=1
while(i<=num1 and i<=num2):
if(num1%i==0 and num2%i==0):
gcd=i
i=i+1
print("GCD is",gcd)
Output:
 EXPERIMENT NO. 2

AIM: To find the square root of a number by using Newton’s Method.

REQUIREMENTS: PC with window operating system and PYTHON software.
THEORY:
Newton’s Method: 
Let N be any number then the square root of N can be given by the formula: 
root = 0.5 * (X + (N / X)) where X is any guess which can be assumed to be N or 1.  
 In the above formula, X is any assumed square root of N and root is the correct
square root of N.
 Tolerance limit is the maximum difference between X and root allowed.

Approach: The following steps can be followed to compute the answer: 

 
1. Assign X to the N itself.
2. Now, start a loop and keep calculating the root which will surely move towards the
correct square root of N.
3. Check for the difference between the assumed X and calculated root, if not yet
inside tolerance, then update root and continue.
4. If the calculated root comes inside the tolerance allowed then break out of the loop.
5. Print the root.

PYTHON CODE

a = int (input ("Enter Number: "))

m = 0.0000001
x=a
count = 0
while(m):
count += 1
root = 0.5*(x+(a/x))
if(abs(root-x)<m):
break
x=root
print(x)

Output: -
 EXPERIMENT NO. 3

AIM: To find the Power of a Number.

REQUIREMENTS: PC with window operating system and PYTHON software.
THEORY:
In Python, the pow() function calculates the power of any positive integer.
It returns the value of x to the power of y (x^y).
Syntax
pow(x,y)
Parameters
 x - It is the numerical value (base value)
 y - It is the power of numerical value (exponent value)

Algorithm (Steps)
Following are the Algorithm/steps to be followed to perform the desired task –.
 Create a variable to store the input number.
 Create another variable to store the exponent/power value.
 Use the pow() function to print the resultant power of a number i.e, inputNumber
^ inputPower by passing the number, and exponent values as arguments to it and
print the resultant power.

PYTHON CODE

x = int(input("Enter the Number whose power has to be calculated: "))

y = int(input("Enter the Value raised to Compute Power: "))
p = x**y
print(x,"raised to power",y,"is",p)
Output: -
 EXPERIMENT NO. 4

AIM:To find the Maximum of a list of Numbers.

REQUIREMENTS:PC with window operating system and PYTHON software.
THEORY:
Here first we take input of list of the numbers then simply by using max() function we can
easily find the maximum number between list of the numbers . And we can also find maximum
without using max()  .For this first we assume that first element of the list is maximum and
compare it with all the numbers one by one and if it is less than any number then max_number 
is equal to that number. By using this we can simply find the maximum among list of
numbers. 

PYTHON CODE

list1 = []
num = int(input("Enter Number of Elements in List: "))
for i in range(1,num+1):
e = int(input("Enter Elements: "))
list1.append(e)
print("Largest Element is: ",max(list1))
Output: -
 EXPERIMENT NO. 5

AIM: To Implement Linear Search.

REQUIREMENTS: PC with window operating system and PYTHON software.
THEORY:
Linear Search is defined as a sequential search algorithm that starts at one end and goes
through each element of a list until the desired element is found, otherwise the search continues
till the end of the data set.

A simple approach is to do a linear search, i.e

 Start from the leftmost element of arr[] and one by one compare x with each element of
arr[]
 If x matches with an element, return the index.
 If x doesn’t match with any of the elements, return -1. 

PYTHON CODE

def lsearch(L,x):
for i in range(len(L)):
if L[i] ==x:
return i
return -1
# Function call
L=[]
for i in range(0,10):
n = int(input("Enter item Of List: "))
L.append(n)
x = int(input("Enter the Element you want to search: "))
result = lsearch(L,x)

if(result == -1):
print("Element is not present in Array")
else:
print("Element is present at index: ",result)
Output:
 EXPERIMENT NO. 6

AIM: To Implement Binary Search

REQUIREMENTS: PC with window operating system and PYTHON software.
THEORY:
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search
interval in half. The idea of binary search is to use the information that the array is sorted and
reduce the time complexity to O(Log n). 

Approach:
1. Compare x with the middle element.
2. If x matches with the middle element, we return the mid index.
3. Else if x is greater than the mid element, then x can only lie in the right (greater) half
subarray after the mid element. Then we apply the algorithm again for the right half.
4. Else if x is smaller, the target x must lie in the left (lower) half. So we apply the
algorithm for the left half

PYTHON CODE

def bsearch(L,x):
low = 0
high = len(L)-1
mid = 0
while low<=high:
mid = (high+low)//2
if L[mid]<x:
low = mid+1
elif L[mid]>x:
high = mid-1
else:
return mid
return -1
# Function call
L=[]
for i in range(0,5):
n = int(input("Enter item Of List: "))
L.append(n)
x = int(input("Enter the Element you want to search: "))
result = bsearch(L,x)
if(result != -1):
print("Element is present at index: ",str(result))
else:
print("Element is not present in the List")
Output:
 EXPERIMENT NO. 7

AIM: To Implement Selection Sort.

REQUIREMENTS: PC with window operating system and PYTHON software.

THEORY:

The selection sort algorithm sorts an array by repeatedly finding the minimum element

(considering ascending order) from the unsorted part and putting it at the beginning. 
The algorithm maintains two subarrays in a given array.
 The subarray which already sorted. 
 The remaining subarray was unsorted.
In every iteration of the selection sort, the minimum element (considering ascending order)
from the unsorted subarray is picked and moved to the sorted subarray. 

PYTHON CODE

def Ssort(L):
for i in range(0,len(L)):
s=L[i]
p=i
for j in range(i+1,len(L)):
if L[j]<s:
s=L[j]
p=j
L[i],L[p]=L[p],L[i]
print(L)
# Function call
L=[]
m=int(input("Enter Size of List: "))
for k in range(0,m):
n=int(input("Enter item of List: "))
L.append(n)
Ssort(L)
Output:
 EXPERIMENT NO.8

AIM: To Implement Insertion Sort.

REQUIREMENTS:PC with window operating system and PYTHON software.

THEORY:

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing
cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from
the unsorted part are picked and placed at the correct position in the sorted part.

PYTHON CODE

def Isort(L):
for i in range(0,len(L)):
temp=L[i]
j=i-1
while (j>=0 and temp<L[j]):
L[j+1] = L[j]
j -= 1
L[j+1] = temp
print(L)
# Function call
L=[]
m=int(input("Enter Size of List: "))
for k in range(0,m):
n=int(input("Enter item of List: "))
L.append(n)
Isort(L)
Output: -
 EXPERIMENT NO.9

AIM: To Implement Merge Sort.

REQUIREMENTS: PC with window operating system and PYTHON software.

THEORY:

The Merge Sort algorithm is a sorting algorithm that is based on the Divide and

Conquer paradigm. In this algorithm, the array is initially divided into two equal halves and then
they are combined in a sorted manner.

Think of it as a recursive algorithm continuously splits the array in half until it cannot be further
divided. This means that if the array becomes empty or has only one element left, the dividing
will stop, i.e. it is the base case to stop the recursion. If the array has multiple elements, split the
array into halves and recursively invoke the merge sort on each of the halves. Finally, when both
halves are sorted, the merge operation is applied. Merge operation is the process of taking two
smaller sorted arrays and combining them to eventually make a larger one.

PYTHON CODE

def merge(arr,l,m,r):
n1 = m-l+1
n2 = r-m
L = [0]*(n1)
R = [0]*(n2)
for i in range(0,n1):
L[i] = arr[l+i]
for j in range(0,n2):
R[j] = arr[m+1+j]
i=0
j=0
k=l
while i<n1 and j<n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i<n1:
arr[k] = L[i]
i += 1
k += 1
while j<n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr,l,r):
if l<r:
m = (l+(r-1))//2
mergeSort(arr,l,m)
mergeSort(arr,m+1,r)
merge(arr,l,m,r)
# Function call
arr = []
q = int(input("Enter size of Array: "))
for z in range(0,q):
t = int(input("Enter items in Array: "))
arr.append(t)
n = len(arr)
print("Given array is")
for i in range(n):
print("%d" %arr[i]),
mergeSort(arr,0,n-1)
print("\n Sorted array is")
for i in range(n):
print("%d" %arr[i]),
Output: -
 EXPERIMENT NO.10

AIM: To find first n Prime Numbers

REQUIREMENTS: PC with window operating system and PYTHON software.

THEORY:

Prime Numbers are the numbers that have only 2 factors 1 and the number itself. It is only
defined for the number which is greater than ‘1’.
Approach:
 Our program will take integer input from the user. This integer is the number limit till
where we need to find all prime numbers.
 We need to iterate through every number below that input integer and check if it is a
prime number or not simultaneously.
 If the iterated number is found prime number then print that number as an output.

PYTHON CODE
i=1
x = int(input("Enter the Number: "))
counter = 0
while True:
c=0
for j in range(1,i+1,1):
a = i%j
if a==0:
c = c+1
if c==2:
print(i)
counter = counter+1
if counter>=x:
break
i = i+1
Output: -