{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Module 2 - Midterm simulation test\n",
    "\n",
    "This is the second DS MidTerm exam provided in December 2023.\n",
    "\n",
    "Please, refer to Prof. Alessandro Romanel for any comments on the theoretical part.\n",
    "\n",
    "Solutions for the practical part will be provided later today (or tomorrow).\n",
    "\n",
    "## Theoretical part\n",
    "\n",
    "### Exercise 1\n",
    "Given a list 𝐿 of 𝑛≥3 integer elements, please compute the asymptotic computational complexity of the following function, explaining your reasoning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_fun(L):\n",
    "    for i in range(3, len(L)):\n",
    "        k = 0\n",
    "        R = L[i]\n",
    "        tmp = []\n",
    "        while k < 3:\n",
    "            if k % 2 == 1:\n",
    "                R = R - L[k]\n",
    "            else:\n",
    "                R = R + L[k]\n",
    "            k += 1\n",
    "        tmp.append(R)\n",
    "\n",
    "    return sum(tmp)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2\n",
    "What is the topological sorting of a directed acyclic graph (DAG)? Briefly describe an algorithm to compute it and provide a possible topological view of the following DAG.\n",
    "\n",
    "![](images/graph_1_sim.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Practical part\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3\n",
    "\n",
    "Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are in the intended order.\n",
    "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. \n",
    "Therefore, it is called a **bubble sort**.\n",
    "\n",
    "1. The idea is to scan multiple times the list (from the start) and every time when you find two elements in the wrong order you swap them. If they are in the right order you do nothing.\n",
    "2. If at the end of a scan you did not swap any elements then your list is sorted\n",
    "\n",
    "After the first scan the max is at the last position (green color), at the second scan the \"second max\" is at the second-last position and so on. \n",
    "\n",
    "Below you can see and example of the bubble sort execution \n",
    "\n",
    "![](images/bubb.png)\n",
    "\n",
    "**Implement the bubble sort algorithm by filling the sort method below**\n",
    "\n",
    "Then, test it on a random array of 500 elements and check its correctness.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before sorting:\n",
      "\n",
      "[7, 5, 10, -11, 3, -4, 99, 1]\n",
      "After sorting:\n",
      "\n",
      "[-11, -4, 1, 3, 5, 7, 10, 99]\n",
      "\n",
      "Number of elements: 1000\n",
      "Number of comparisons: 499290\n",
      "Number of swaps: 242981\n",
      "\n",
      "Number of elements: 2000\n",
      "Number of comparisons: 1998054\n",
      "Number of swaps: 985687\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "class SortingAlgorithm:\n",
    "    def __init__(self, data, verbose = True):\n",
    "        self.data = data\n",
    "        self.comparisons = 0\n",
    "        self.operations = 0\n",
    "        self.verbose = verbose\n",
    "        \n",
    "    def getData(self):\n",
    "        return self.data\n",
    "    \n",
    "    def getOperations(self):\n",
    "        return self.operations\n",
    "    \n",
    "    def getComparisons(self):\n",
    "        return self.comparisons\n",
    "\n",
    "    def sort(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "class BubbleSort(SortingAlgorithm):\n",
    "    \n",
    "    def sort(self):\n",
    "        self.comparisons = 0\n",
    "        self.operations = 0\n",
    "        n = len(self.data)\n",
    "        #stop if no no swaps are found in an iteration\n",
    "        for i in range(n-1):\n",
    "            swapped = False\n",
    "            for j in range(0, n-i-1):\n",
    "                if self.data[j] > self.data[j + 1]:\n",
    "                    self.data[j], self.data[j + 1] = self.data[j + 1], self.data[j]\n",
    "                    swapped = True\n",
    "                    self.operations += 1\n",
    "                \n",
    "                self.comparisons += 1\n",
    "\n",
    "            if not swapped:\n",
    "                break\n",
    "        \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    d = [7, 5, 10, -11 ,3, -4, 99, 1]\n",
    "    print(\"Before sorting:\\n\")\n",
    "    print(d)\n",
    "    bubSorter = BubbleSort(d, verbose = True)\n",
    "    bubSorter.sort()\n",
    "    print(\"After sorting:\\n\")\n",
    "    print(d)\n",
    "    d = []\n",
    "\n",
    "    for i in range(0,1000):\n",
    "        d.append(random.randint(0,1000))\n",
    "    bubSorter = BubbleSort(d)\n",
    "    bubSorter.sort()\n",
    "    print(\"\\nNumber of elements: {}\".format(len(d)))\n",
    "    print(\"Number of comparisons: {}\".format(bubSorter.getComparisons()))\n",
    "    print(\"Number of swaps: {}\".format(bubSorter.getOperations()))\n",
    "    \n",
    "    d = []\n",
    "    for i in range(0,2000):\n",
    "        d.append(random.randint(0,1000))\n",
    "    bubSorter = BubbleSort(d)\n",
    "    bubSorter.sort()\n",
    "    print(\"\\nNumber of elements: {}\".format(len(d)))\n",
    "    print(\"Number of comparisons: {}\".format(bubSorter.getComparisons()))\n",
    "    print(\"Number of swaps: {}\".format(bubSorter.getOperations()))\n",
    "    \n",
    "    test = True\n",
    "    for el in range(0,len(d)-1):\n",
    "        test = test and (d[el]<= d[el+1])\n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Binary Search Tree (BST) is a binary tree with the following properties:\n",
    "\n",
    "- The left subtree of a node contains only nodes with values lower than that of the node.\n",
    "- The right subtree of a node contains only nodes with values greater than the node’s.\n",
    "- No duplicate nodes are allowed.\n",
    "\n",
    "Look at the BST implemented in the code chunck below.\n",
    "From the input list, the function **createBST()**  generates a BST. \\\n",
    "Please check carefully how the class is implemented since it might slightly differ from the one you have seen during the practical class. \\\n",
    "The BST structure created by the script is shown below:\n",
    "\n",
    "![](images/BST_extraEx.png)\n",
    "\n",
    "**TO DO**\n",
    "\n",
    "\n",
    "Implement the **search_interval(self, a, b)** method for the provided **BinarySearchTree** class. \\\n",
    "This function takes the root node of a BST and two integers a and b (where a ≤ b), then returns a sorted list containing all values (nodes) in the tree that fall between a and b inclusive. \\\n",
    "Example:\n",
    "\n",
    "```BST.search_interval(3,10)``` will return [3, 5, 9] \n",
    " \n",
    "```BST.search_interval(18,26)``` will return [19, 21, 25]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**HINTS**\n",
    "\n",
    "- You can both use a **recursive** or **iterative** solutions\n",
    "\n",
    "- If you choose the iterative one, consider to use a stack to visit nodes (i.e. save the one to visit, similar to a iterative pre-order DFS).\n",
    "\n",
    "    - For each node, check if the node’s **value** falls within the interval **[a, b]**.\n",
    "\n",
    "    - If so, the value is **added** to the result list.\n",
    "\n",
    "    - The traversal continues to the **left** child if the current value is greater than **a**, and to the **right child** if the value is less than **b**.\n",
    "\n",
    "    - The result list is sorted before being returned to ensure ascending order.\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree:\n",
      "\n",
      "5 (r)-> 12\n",
      "5 (l)-> 2\n",
      "\t2 (r)-> 3\n",
      "\t2 (l)-> 1\n",
      "\t12 (r)-> 21\n",
      "\t12 (l)-> 9\n",
      "\t\t21 (r)-> 25\n",
      "\t\t21 (l)-> 19\n",
      "\n",
      "Values in interval [3,10]: [3, 5, 9]\n",
      "\n",
      "Values in interval [18,26]: [19, 21, 25]\n"
     ]
    }
   ],
   "source": [
    "class BinarySearchTree:\n",
    "    def __init__(self, value):\n",
    "        self.__data = value\n",
    "        self.__right = None\n",
    "        self.__left = None\n",
    "        self.__parent = None\n",
    "\n",
    "    def getValue(self):\n",
    "        return self.__data\n",
    "    def setValue(self, newValue):\n",
    "        self.__data = newValue\n",
    "\n",
    "    def getParent(self):\n",
    "        return self.__parent\n",
    "    def setParent(self, tree):\n",
    "        self.__parent = tree\n",
    "\n",
    "    def getRight(self):\n",
    "        return self.__right\n",
    "    def getLeft(self):\n",
    "        return self.__left\n",
    "\n",
    "    def insertRight(self, tree):\n",
    "        if self.__right == None:\n",
    "            self.__right = tree\n",
    "            tree.setParent(self)\n",
    "    def insertLeft(self, tree):\n",
    "        if self.__left == None:\n",
    "            self.__left = tree\n",
    "            tree.setParent(self)\n",
    "\n",
    "    # START CODING BELOW HERE:\n",
    "    def search_interval(self, a, b):\n",
    "\n",
    "        #iterative version:\n",
    "        result = []\n",
    "        if self.__data is None:\n",
    "            return result\n",
    "\n",
    "        stack = [self]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node is not None:\n",
    "                value = node.getValue()\n",
    "                if a <= value <= b:\n",
    "                    result.append(value)\n",
    "                if value > a:\n",
    "                    stack.append(node.getLeft())\n",
    "                if value < b:\n",
    "                    stack.append(node.getRight())\n",
    "\n",
    "        return sorted(result)\n",
    "        #recursive version:\n",
    "\n",
    "        # greaterThanMin = a < self.__data\n",
    "        # lowerThanMax = b > self.__data\n",
    "\n",
    "        # elements = []\n",
    "\n",
    "        # if greaterThanMin:\n",
    "        #     if (self.__left != None):\n",
    "        #         elements.extend(self.__left.search_interval(a, b))\n",
    "\n",
    "        # if (a <= self.__data <= b):\n",
    "        #     elements.append(self.__data)\n",
    "\n",
    "        # if lowerThanMax:\n",
    "        #     if (self.__right != None):\n",
    "        #         elements.extend(self.__right.search_interval(a, b))\n",
    "\n",
    "        # return(elements)\n",
    "\n",
    "\n",
    "\n",
    "def createBST(intList):\n",
    "    \n",
    "    BST = None\n",
    "    if len(intList) > 0:\n",
    "        BST = BinarySearchTree(intList[0])\n",
    "        for el in intList[1:]:\n",
    "            cur_el = BST\n",
    "            alreadyPresent = False\n",
    "            prev_el = None\n",
    "            while cur_el != None:\n",
    "                prev_el = cur_el\n",
    "                cv = cur_el.getValue()\n",
    "                if  cv > el:\n",
    "                    cur_el = cur_el.getLeft()\n",
    "                elif cv < el:\n",
    "                    cur_el = cur_el.getRight()\n",
    "                else:\n",
    "                    alreadyPresent = True\n",
    "                    break\n",
    "\n",
    "            if not alreadyPresent:\n",
    "                node = BinarySearchTree(el)\n",
    "                node.setParent(prev_el)\n",
    "                if prev_el.getValue() > el:\n",
    "                    prev_el.insertLeft(node)\n",
    "                else:\n",
    "                    prev_el.insertRight(node)\n",
    "\n",
    "    return BST\n",
    "\n",
    "\n",
    "def printTree(root):\n",
    "    cur = root\n",
    "    nodes = [(cur,0)]\n",
    "    tabs = \"\"\n",
    "    lev = 0\n",
    "    while len(nodes) >0:\n",
    "        cur, lev = nodes.pop(-1)\n",
    "        if cur.getRight() != None:\n",
    "            print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n",
    "                                          cur.getValue(),\n",
    "                                          cur.getRight().getValue()))\n",
    "            nodes.append((cur.getRight(), lev+1))\n",
    "        if cur.getLeft() != None:\n",
    "            print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n",
    "                                          cur.getValue(),\n",
    "                                          cur.getLeft().getValue()))\n",
    "            nodes.append((cur.getLeft(), lev+1))\n",
    "\n",
    "\n",
    "\n",
    "# DO NOT modify code below:\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    inList = [5,2,1,3,12,9,21,19,25]\n",
    "\n",
    "    BST = createBST(inList)\n",
    "\n",
    "    print(\"Tree:\\n\")\n",
    "    printTree(BST)\n",
    "\n",
    "    #CHECKS!\n",
    "    res = BST.search_interval(3,10)\n",
    "    print(\"\\nValues in interval [3,10]: {}\".format(res))\n",
    "    assert res == [3,5,9], \"Test failed!\"\n",
    "\n",
    "    res2 = BST.search_interval(18,26)\n",
    "    print(\"\\nValues in interval [18,26]: {}\".format(res2))\n",
    "    assert res2 == [19,21,25], \"Test failed!\"    \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "3.10.14",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.14"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}