Analysis of Algorithms and Researching Computing Seat

No: 2086553

University Department of Computer

Science

University of Mumbai

Practical Journal of

Analysis of Algorithms and Research

Computing

By

Mohammed Daniyal Qureshi

UDCS MSc Part I [2019-2020] Page 1

Analysis of Algorithms and Researching Computing Seat
No: 2086553

University Department of Computer

Science

University of Mumbai

Certificate

This is to certify that, Mr / Ms Mohammed Daniyal Qureshi, Seat

No: UDCS 2086553 Studying in MSc Computer Science, Semester- I
has satisfactorily completed the practical in the course “Analysis of
Algorithms and Researching Computing” as prescribed by University
of Mumbai during the academic year 2019-2020.

__________________ __________________

Course In-charge Dr Ambuja

Salgaonkar

Head, Dept. of
Computer science

UDCS MSc Part I [2019-2020] Page 2

Analysis of Algorithms and Researching Computing Seat
No: 2086553

_________________

Examiner

Declaration

I state that the term work submitted here for the Course: Analysis
of Algorithms and Researching Computing has been the outcome of
my own studies, experimentation, and analysis and is per the
guidance that we received in the Semester I of MSc Computer
Science Programme during July to December 2019.

I undertake that this work has not been copied from anywhere nor
been submitted to anywhere else than for the credit of the above
referred Programme.

To the best of my knowledge, the original source has been cited

and a due credit has been given to the references that have been
used.

I am aware that abide by the University norms my admission and

credits of this Course may stand invalid if I am proved false in
stating this.

Mohammed Daniyal Qureshi

UDCS MSc Part I [2019-2020] Page 3

 Analysis of Algorithms and Researching Computing Seat
No: 2086553

INDEX

Sr Topic Page No
No
.
1 Write a program to implement insertion sort and find the running time of the 5
algorithm.

2 Write a program to implement merge sot algorithm. Compare the time and memory 7
complexity.

3 Given an array of numbers of length l. Write a program to generate a random 10

permutation of the array using (i) permute-by-sorting() and(ii) permute-by-cyclic().

4 Write a program to implement Longest Common Subsequence (LCS) algorithm 12

5 Write a program to implement Huffman’s code algorithm 13

6 Write a program to implement Kruskal’s algorithm. 15

7 Write a program to implement Dijkstrass’s algorithm 18

8 Write a program to implement Euclid’s algorithm to implement gcd of two non 21

negative integers a and b. Extend the algorithm to find x and y such that gcd(a,b) =
ax+by. Compare the running time and recursive calls made in each case.

9 Write a program to verify (i) Euclid’s theorem (ii) Fermat’s theorem. 23

10 Write a program to implement greedy set cover algorithm to solve set covering 25

UDCS MSc Part I [2019-2020] Page 4

Analysis of Algorithms and Researching Computing Seat
No: 2086553
problem.

Practical No:- 01
Problem statement:- Write a program to implement insertion sort and find the running time
of the algorithm.

Insertion Sort :-

Pseudocode:-
INSERTION-SORT(A)

for j=2 to A.length

key = A[j]
//Insert A[j] into the sorted sequence A[1…j-1]
i = j-1
while i < 0 and A[i]>key
A[i+1] = A[i]
i = i-1
A[i+1] = key

Code:-

def insertionSort(alist):

UDCS MSc Part I [2019-2020] Page 5

Analysis of Algorithms and Researching Computing Seat
No: 2086553
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [55,23,98,14,69,28,47,51,21]
insertionSort(alist)
print(alist)

Output:-

UDCS MSc Part I [2019-2020] Page 6

Analysis of Algorithms and Researching Computing Seat
No: 2086553

Practical No:- 02

Problem statement:- Write a program to implement merge sot algorithm. Compare the time
and memory complexity.

Merge Sort :-

Code:-
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:

UDCS MSc Part I [2019-2020] Page 7

Analysis of Algorithms and Researching Computing Seat
No: 2086553
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Output:-

UDCS MSc Part I [2019-2020] Page 8

Analysis of Algorithms and Researching Computing Seat
No: 2086553

Practical No:- 03

UDCS MSc Part I [2019-2020] Page 9

Analysis of Algorithms and Researching Computing Seat
No: 2086553

Problem statement:- Given an array of numbers of length l. Write a program to generate a

random permutation of the array using (i) permute-by-sorting() and(ii) permute-by-cyclic().

Code:-
(ii) permute-by-cyclic()

from random import randint

s = list(range(10))
#print("Start")
def permute_by_cyclic(a):
n = len(a)
z = [0 for i in range(n)]
oset = randint(1, n)
for i in range(n):
dest = (i+oset) % n
z[dest] = a[i]
#print("mid")
return z
p = permute_by_cyclic(s)
#print("end")
print (p)

Output :-

(i) permute-by-sorting()

UDCS MSc Part I [2019-2020] Page 10

Analysis of Algorithms and Researching Computing Seat
No: 2086553

import random
def bogosort(a):
n = len(a)
while(is_sorted(a)== False):
shuffle(a)
def is_sorted(a):
n = len(a)
for i in range(0,n-1):
if(a[i]<a[i+1]):
return False
return True
def shuffle(a):
n = len(a)
for i in range(0,n):
r=random.randint(0,n-1)
a[i], a[r] = a[r], a[i]
a= [3,4,1,5,2]
bogosort(a)
print("Sorting")
for i in range(len(a)):
print("%d"%a[i])

Output:-

Practical No:- 04
UDCS MSc Part I [2019-2020] Page 11
Analysis of Algorithms and Researching Computing Seat
No: 2086553

Problem statement:- Write a program to implement Longest Common Subsequence (LCS)

algorithm

Concept analysis:-
Code:-
def lcs(M, N, a, b):
if a == 0 or b == 0:
return 0;
elif M[a-1] == N[b-1]:
return 1 + lcs(M, N, a-1, b-1);
else:
return max(lcs(M, N, a, b-1), lcs(M, N, a-1, b));
M = "PMMTPB"
N = "MXTXPYB"
print ("Length of LCS is ", lcs(M , N, len(M), len(N)))

Output:-

Practical No:- 05

UDCS MSc Part I [2019-2020] Page 12

Analysis of Algorithms and Researching Computing Seat
No: 2086553

Problem statement:- Write a program to implement Huffman’s code algorithm

Huffman’s code:-

Psuedocode:-

HUFFMAN(C)
1 n = |C|
2Q=C
3 for i = 1 to n - 1
4 allocate a new node
5 z.left = x = EXTRACT-MIN(Q)
6 z.right = y = EXTRACT-MIN(Q)
7 z.freq= x:freq + y:freq
8 INSERT(Q,z)
9 return EXTRACT-MIN(Q) //return the root of the tree

Code:-
import heapq
from collections import defaultdict
def encode(frequency):
heap = [[weight, [symbol, '']] for symbol, weight in frequency.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

UDCS MSc Part I [2019-2020] Page 13

Analysis of Algorithms and Researching Computing Seat
No: 2086553
data = "Pradnya santosh sable manali"
frequency = defaultdict(int)
for symbol in data:
frequency[symbol] += 1

huff = encode(frequency)
print ("Symbol".ljust(10) + "Weight".ljust(10) + "Huffman Code")
for p in huff:
print (p[0].ljust(10) + str(frequency[p[0]]).ljust(10) + p[1])

Output:-

Program No:-06

UDCS MSc Part I [2019-2020] Page 14

Analysis of Algorithms and Researching Computing Seat
No: 2086553

Problem statement:- Write a program to implement Kruskal’s algorithm.

Kruskal’s algorithm:-

Pseudocode

T (the final spanning tree) is defined to be the empty set;

For each vertex v of G, make the empty set out of v;
Sort the edges of G in ascending (non-decreasing) order;
For each edge (u, v) from the sored list of step 3.
If u and v belong to different sets
Add (u,v) to T;
Get together u and v in one single set;
Return T
Time Complexity:-
Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time,
where E is the number of edges in the graph and V is the number of vertices, all with simple
data structures.
Code:-
from collections import defaultdict
class Graph:
def __init__(self,vertices):
self.V= vertices
self.graph = []

def addEdge(self,u,v,w):
self.graph.append([u,v,w])

def find(self, parent, i):

if parent[i] == i:
return i
return self.find(parent, parent[i])

UDCS MSc Part I [2019-2020] Page 15

Analysis of Algorithms and Researching Computing Seat
No: 2086553

def union(self, parent, rank, x, y):

xroot = self.find(parent, x)
yroot = self.find(parent, y)

if rank[xroot] < rank[yroot]:

parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot

else :
parent[yroot] = xroot
rank[xroot] += 1

def KruskalMST(self):
result =[]
i=0
e=0
self.graph = sorted(self.graph ,key=lambda item: item[2])
parent = [] ; rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V -1 :
u,v,w = self.graph[i]
i=i+1
x = self.find(parent, u)
y = self.find(parent ,v)

if x != y:
e=e+1

UDCS MSc Part I [2019-2020] Page 16

Analysis of Algorithms and Researching Computing Seat
No: 2086553
result.append([u,v,w])
self.union(parent, rank, x, y)
print ("Following are the edges in the constructed MST")
for u,v,weight in result:
print ("%d -- %d == %d" % (u,v,weight))

g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
g.KruskalMST()

Output:-

Practical No :- 07

UDCS MSc Part I [2019-2020] Page 17

Analysis of Algorithms and Researching Computing Seat
No: 2086553
Problem statement:- Write a program to implement Dijkstrass’s algorithm

Concept analysis:-
Dijkstrass’s algorithm:-

Pseudocode:-

DIJKSTRA(G, w, s)

1 INITIALIZE-SINGLE-SOURCE(G, s)

2S=0

3 Q = G,V

4 while Q != 0

5 u = EXTRACT-MIN(Q)

6 S = S U {u}

7 for each vertex v belongsto G.Adj[u]

8 RELAX(u,v,w)

Code:-
from collections import defaultdict
class Graph:
def minDistance(self,dist,queue):
min = float("Inf")
min_index = -1
for i in range(len(dist)):
if dist[i] < min and i in queue:
min = dist[i]
min_index = i

UDCS MSc Part I [2019-2020] Page 18

Analysis of Algorithms and Researching Computing Seat
No: 2086553
return min_index
def printPath(self, parent, j):
if parent[j] == -1 :
print (j,)
return
self.printPath(parent , parent[j])
print (j,)
def printSolution(self, dist, parent):
src = 0
print("Vertex \t\tDistance from Source\tPath")
for i in range(1, len(dist)):
print("\n%d --> %d \t\t%d \t\t\t\t\t" % (src, i, dist[i])),
self.printPath(parent,i)
def dijkstra(self, graph, src):
row = len(graph)
col = len(graph[0])
dist = [float("Inf")] * row
parent = [-1] * row
dist[src] = 0
queue = []
for i in range(row):
queue.append(i)
while queue:
u = self.minDistance(dist,queue)
queue.remove(u)
for i in range(col):
if graph[u][i] and i in queue:
if dist[u] + graph[u][i] < dist[i]:
dist[i] = dist[u] + graph[u][i]
parent[i] = u
self.printSolution(dist,parent)
g= Graph()

UDCS MSc Part I [2019-2020] Page 19

Analysis of Algorithms and Researching Computing Seat
No: 2086553
graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
g.dijkstra(graph,0)

Output:-

UDCS MSc Part I [2019-2020] Page 20

Analysis of Algorithms and Researching Computing Seat
No: 2086553
Practical No :- 08

Problem statement:- Write a program to implement Euclid’s algorithm to implement gcd of

two non negative integers a and b. Extend the algorithm to find x and y such that gcd(a,b) =
ax+by. Compare the running time and recursive calls made in each case.

Code:-
def gcdExtended(a, b, x, y):
if a == 0 :
x=0
y=1
return b
x1 = 1
y1 = 1 # To store results of recursive call
gcd = gcdExtended(b%a, a, x1, y1)
x = y1 - (b/a) * x1
y = x1
return gcd
x=1
y=1
a = 70
b = 58
g = gcdExtended(a, b, x, y)
print("gcd(", a , "," , b, ") = ", g)
print("Extended Form")
print(a ," * " ,x ," + " ,b ," * ", y, " = ", g)

UDCS MSc Part I [2019-2020] Page 21

Analysis of Algorithms and Researching Computing Seat
No: 2086553
Output:-

UDCS MSc Part I [2019-2020] Page 22

Analysis of Algorithms and Researching Computing Seat
No: 2086553
Practical No :- 09

Problem statement:- Write a program to verify (i) Euclid’s theorem (ii) Fermat’s theorem.

Code:-
Euclid’s theorem:-

def gcd(a,b):
if a==0:
return b
return gcd(b%a,a)
a=5
b=10
print("gcd(",a,",",b,")= ",gcd(a,b))

a=35
b=10
print("gcd(",a,",",b,")= ",gcd(a,b))

a=31
b=2
print("gcd(",a,",",b,")= ",gcd(a,b))
Output:-

UDCS MSc Part I [2019-2020] Page 23

Analysis of Algorithms and Researching Computing Seat
No: 2086553
Fermat’s Theorem

def testSomeNumbers(limit, n) :
if (n < 3):
return
for a in range(1, limit + 1):
for b in range(a, limit + 1):
pow_sum = pow(a, n) + pow(b, n)
c = pow(pow_sum, 1.0 / n)
c_pow = pow(int(c), n)
if (c_pow == pow_sum):
print("Count example found")
return
print("No counter example within given range and data")
testSomeNumbers(3, 4)

Output:-

UDCS MSc Part I [2019-2020] Page 24

Analysis of Algorithms and Researching Computing Seat
No: 2086553
Practical No :- 10

Problem statement:- Write a program to implement greedy set cover algorithm to solve set
covering problem.

Code:-
def set_cover(universe, subsets):
"""Find a family of subsets that covers the universal set"""
elements = set(e for s in subsets for e in s)
# Check the subsets cover the universe
if elements != universe:
return None
covered = set()
cover = []
# Greedily add the subsets with the most uncovered points
while covered != elements:
subset = max(subsets, key=lambda s: len(s - covered))
cover.append(subset)
covered |= subset

return cover

def main():
universe = set(range(1, 11))
subsets = [set([1, 2, 3, 8, 9, 10]),
set([1, 2, 3, 4, 5]),
set([4, 5, 7]),
set([5, 6, 7]),
set([6, 7, 8, 9, 10])]
cover = set_cover(universe, subsets)
print(cover)

UDCS MSc Part I [2019-2020] Page 25

Analysis of Algorithms and Researching Computing Seat
No: 2086553
if __name__ == '__main__':
main()
Output:-

UDCS MSc Part I [2019-2020] Page 26