Module 2 - Midterm simulation test SOLUTIONS

This is the second DS MidTerm exam provided in December 2022.

Practical part

Excercise 3

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, the maximum element of the array moves to the end in each iteration. Therefore, it is called a bubble sort.

  1. The idea is to scan multiple times the list and when you find two elements in the wrong order you swap them.

  2. If at the end of a scan you did not swap any elements then your list is sorted

After the first scan the max is at the last position, at the second scan the “second max” is at the second-last position and so on.

Below you can see and example of the bubble sort execution

_images/bubb.png

Implement the bubble sort algorithm by filling the method below

Then, test it on a random array of 500 elements and check its correctness. Finally, analyze the time complexity of this algorithm.

Solution

[3]:

import random

class SortingAlgorithm:
    def __init__(self, data, verbose = True):
        self.data = data
        self.comparisons = 0
        self.operations = 0
        self.verbose = verbose

    def getData(self):
        return self.data

    def getOperations(self):
        return self.operations

    def getComparisons(self):
        return self.comparisons

    def sort(self):
        raise NotImplementedError

class BubbleSort(SortingAlgorithm):

    def sort(self):
        self.comparisons = 0
        self.operations = 0
        n = len(self.data)
        #stop if no no swaps are found in an iteration
        for i in range(n-1):
            swapped = False
            for j in range(0, n-i-1):
                if self.data[j] > self.data[j + 1]:
                    self.data[j], self.data[j + 1] = self.data[j + 1], self.data[j]
                    swapped = True
                    self.operations += 1

                self.comparisons += 1

            if not swapped:
                break


if __name__ == "__main__":

    d = [7, 5, 10, -11 ,3, -4, 99, 1]
    print("Before sorting:\n")
    print(d)
    bubSorter = BubbleSort(d, verbose = True)
    bubSorter.sort()
    print("After sorting:\n")
    print(d)
    d = []

    for i in range(0,1000):
        d.append(random.randint(0,1000))
    bubSorter = BubbleSort(d)
    bubSorter.sort()
    print("\nNumber of elements: {}".format(len(d)))
    print("Number of comparisons: {}".format(bubSorter.getComparisons()))
    print("Number of swaps: {}".format(bubSorter.getOperations()))

    d = []
    for i in range(0,2000):
        d.append(random.randint(0,1000))
    bubSorter = BubbleSort(d)
    bubSorter.sort()
    print("\nNumber of elements: {}".format(len(d)))
    print("Number of comparisons: {}".format(bubSorter.getComparisons()))
    print("Number of swaps: {}".format(bubSorter.getOperations()))

    test = True
    for el in range(0,len(d)-1):
        test = test and (d[el]<= d[el+1])
    print("\nSorting test passed? {}".format(test))

Before sorting:

[7, 5, 10, -11, 3, -4, 99, 1]
After sorting:

[-11, -4, 1, 3, 5, 7, 10, 99]

Number of elements: 1000
Number of comparisons: 499485
Number of swaps: 257146

Number of elements: 2000
Number of comparisons: 1997569
Number of swaps: 995732

Sorting test passed? True

Complexity O(n^2 )

Exercise 4

Given a binary search tree as the one provided in the code chunck below, implement the missing function search_interval(a, b) that given two values a and b, finds all values between a and b in the tree, returning them in an ordered data structure. For instance, calling search_interval(24, 33) on the following tree should return: [24, 26, 31, 32].

_images/Graph2.png

Solution

[4]:

class BinaryTree:
    def __init__(self, value):
        self.__data = value
        self.__right = None
        self.__left = None
        self.__parent = None
        self.__depth = 0

    def getDepth(self):
        return self.__depth
    def setDepth(self, newdepth):
        self.__depth = newdepth

    def getValue(self):
        return self.__data
    def setValue(self, newValue):
        self.__data = newValue

    def getParent(self):
        return self.__parent
    def setParent(self, tree):
        self.__parent = tree

    def getRight(self):
        return self.__right
    def getLeft(self):
        return self.__left

    def insertRight(self, tree):
        if self.__right == None:
            self.__right = tree
            tree.setParent(self)
            tree.setDepth(self.getDepth() + 1)
    def insertLeft(self, tree):
        if self.__left == None:
            self.__left = tree
            tree.setDepth(self.getDepth() + 1)
            tree.setParent(self)

    def deleteRight(self):
        self.__right = None
    def deleteLeft(self):
        self.__left = None

    def inOrderDFS(self):
        ret = []
        if self != None:
            r = self.getRight()
            l = self.getLeft()
            if l != None:
                ret.extend(l.inOrderDFS())
            ret.append(self.getValue())
            if r != None:
                ret.extend(r.inOrderDFS())
        return ret

    def search_interval(self, a, b):
        # implemented function!
        greaterThanMin = a < self.__data
        lowerThanMax = b > self.__data

        elements = []

        if greaterThanMin:
            if (self.__left != None):
                elements.extend(self.__left.search_interval(a, b))

        if (a <= self.__data <= b):
            elements.append(self.__data)

        if lowerThanMax:
            if (self.__right != None):
                elements.extend(self.__right.search_interval(a, b))

        return(elements)

def createBST(intList):
    BST = None
    if len(intList) > 0:
        BST = BinaryTree(intList[0])
        for el in intList[1:]:
            cur_el = BST
            alreadyPresent = False
            prev_el = None
            while cur_el != None:
                prev_el = cur_el
                cv = cur_el.getValue()
                if  cv > el:
                    cur_el = cur_el.getLeft()
                elif cv < el:
                    cur_el = cur_el.getRight()
                else:
                    # cv == el (el is already present)
                    # not allowed by rule c, so skip it
                    alreadyPresent = True
                    #print("El {} already present".format(el))
                    break

            if not alreadyPresent:
                node = BinaryTree(el)
                node.setParent(prev_el)
                if prev_el.getValue() > el:
                    prev_el.insertLeft(node)
                else:
                    prev_el.insertRight(node)

    return BST


def printTree(root):
    cur = root
    #each element is a node and a depth
    #depth is used to format prints (with tabs)
    nodes = [(cur,0)]
    tabs = ""
    lev = 0
    while len(nodes) >0:
        cur, lev = nodes.pop(-1)
        if cur.getRight() != None:
            print ("{}{} (r)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getRight().getValue()))
            nodes.append((cur.getRight(), lev+1))
        if cur.getLeft() != None:
            print ("{}{} (l)-> {}".format("\t"*lev,
                                          cur.getValue(),
                                          cur.getLeft().getValue()))
            nodes.append((cur.getLeft(), lev+1))


if __name__ == "__main__":
    import random

    inList = []
    for i in range(1000):
        inList.append(random.randint(0,1000))

    #printTree(createBST(inList[:20])) # to test tree creation...

    BST = createBST(inList)

    sorted = BST.search_interval(24, 33)
    print("Elements between 24 and 33 in the BST:")
    print(sorted)

Elements between 24 and 33 in the BST:
[24, 25, 26, 27, 28, 30, 31, 32]