Data Structures and Algorithms

This assignment contains Python code implementing several data structures and algorithms. It includes a merge sort algorithm, a doubly linked list implementation with insert and remove functions, and a binary search tree implementation with insert, inorder traversal, and minimum value finding functions. The code demonstrates the practical application of these concepts, providing a working example for students to learn from. The website offers solved assignments and past papers to help students understand these concepts better.

arr= [1, 12,100, 9, 5,7,6,8]
crr= [3, 7, 15, 19, 20]
brr= [2, 12, 15, 20, 45]
drr= [2,5,8,10,16,77]
err= [1, 3,14, 19, 45, 66]
# making merge function
def merge(a, b, m, n):
c=[]
i=0
j=0
#print("Sorting:")
#print(a)
#print(b)
#print(m)
#print(n)
#print("while loop")
while(i<m and j<n):
#print(i)
#print(a)
#print(j)
#print(b)
if(a[i]<b[j]):
c.append(a[i])
i+=1
else :
c.append(b[j])

j+=1
if (i>(m-1)):
for x in range(j, len(b)):
c.append(b[x])
if (j>(n-1)):
for x in range(i, len(a)):
c.append(a[x])
#print("Return sorted: " ,c)
return c
#print (merge(brr, crr, len(brr), len(crr)) )
#print (merge(drr, err, len(drr), len(err)) )
def mergeSort(a, st, lt):
mid = int((st+lt)/2)
#print(st,lt,mid)
if (st ==mid):
return a
else :
left= a[st:mid]
right= a[mid:lt]
return merge(mergeSort(left, 0, len(left)), mergeSort(right, 0, len(right)), len(left),
len(right))
print(mergeSort(arr, 0, len(arr)))

class Node(object):
def __init__(self, value):
self.value=value
self.next=None
self.prev=None
class List(object):
def __init__(self):
self.head=None
self.tail=None
def insert(self,n,x):
#Not actually perfect: how do we prepend to an existing list?
if n!=None:
x.next=n.next
n.next=x
x.prev=n
if x.next!=None:
x.next.prev=x
if self.head==None:
self.head=self.tail=x
x.prev=x.next=None
elif self.tail==n:
self.tail=x
def remove(self, val):
"""Remove a node from the list."""
current = self.head

while current:
if current.value == val:
if current == self.head:
self.head = current.next
self.head.prev = None
return
elif current == self.tail:
self.tail = current.prev
self.tail.next = None
return
else:
current.prev.next = current.next
current.next.prev = current.prev
return
else:
current = current.next
raise ValueError("Data not in list")
def display(self):
values=[]
n=self.head
while n!=None:
values.append(str(n.value))
n=n.next

print ("List: ",",".join(values))
if __name__ == '__main__':
l=List()
l.insert(None, Node(4))
l.insert(l.head,Node(6))
l.insert(l.head,Node(8))
l.remove(8)
l.display()
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class List(object):
def __init__(self):
self.head = None
self.tail = None
def insert(self, n, x):
# Not actually perfect: how do we prepend to an existing list?
if n != None:
x.next = n.next
n.next = x
x.prev = n
if x.next != None:

x.next.prev = x
if self.head == None:
self.head = self.tail = x
x.prev = x.next = None
elif self.tail == n:
self.tail = x
def middleElement(self):
x = self.head
y = self.tail
cnt = 0
while(x != y):
if(cnt % 2 == 0):
x = x.next
else:
y = y.prev
cnt += 1
return x.value
def display(self):
values = []
n = self.head
while n != None:
values.append(str(n.value))
n = n.next
print("List: ", ",".join(values))
if __name__ == '__main__':

l = List()
l.insert(None, Node(4))
l.insert(l.head, Node(6))
l.insert(l.head, Node(8))
l.insert(l.head, Node(9))
l.insert(l.head, Node(3))
l.insert(l.head, Node(1))
l.display()
print(l.middleElement())
class BinTreeNode(object):
def __init__(self, value):
self.value=value
self.left=None
self.right=None
def tree_insert( tree, item):
if tree==None:
tree=BinTreeNode(item)
else:
if(item < tree.value):
if(tree.left==None):
tree.left=BinTreeNode(item)
else:
tree_insert(tree.left,item)

else:
if(tree.right==None):
tree.right=BinTreeNode(item)
else:
tree_insert(tree.right,item)
return tree
def postorder(tree):
if(tree.left!=None):
postorder(tree.left)
if(tree.right!=None):
postorder(tree.right)
print (tree.value)
def in_order(tree):
if(tree.left!=None):
in_order(tree.left)
print (tree.value)
if(tree.right!=None):
in_order(tree.right)
def minimumValue(tree):
if(tree.left!=None):
return minimumValue(tree.left)
return tree.value
if __name__ == '__main__':

t=tree_insert(None,6)
tree_insert(t,10)
tree_insert(t,5)
tree_insert(t,2)
tree_insert(t,3)
tree_insert(t,4)
tree_insert(t,11)
# in_order(t)
val=minimumValue(t)
print(val)