Last active
October 30, 2019 19:19
-
-
Save steven-tey/52999fb4977dda7ed153160589007275 to your computer and use it in GitHub Desktop.
CS110 Session 8.2 Pre-Class Work
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "kernelspec": { | |
| "display_name": "Python 3", | |
| "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.6.5" | |
| }, | |
| "colab": { | |
| "name": "CS110 Session 8.2 Pre-Class Work.ipynb", | |
| "provenance": [], | |
| "collapsed_sections": [] | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "IMYTLD85-9d0", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n", | |
| "\n", | |
| "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "AQtr42GG-9d2", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "NAME = \"\"\n", | |
| "COLLABORATORS = \"\"" | |
| ], | |
| "execution_count": 0, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "nVgrHL1y-9eB", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "---" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "c87c76aab5414c691aa63dd316a3aad4", | |
| "grade": false, | |
| "grade_id": "cell-856b478addb28fe9", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| }, | |
| "id": "6A5GBiHJ-9eC", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "# CS110 Pre-class Work 8.2\n", | |
| "\n", | |
| "# Question 1. (Exercise 12.2-1, Cormen et al.)\n", | |
| "\n", | |
| "Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?\n", | |
| "\n", | |
| "a. 2, 252, 401, 398, 330, 344, 397, 363.\n", | |
| "\n", | |
| "b. 924, 220, 911, 244, 898, 258, 362, 363.\n", | |
| "\n", | |
| "c. 925, 202, 911, 240, 912, 245, 363.\n", | |
| "\n", | |
| "d. 2, 399, 387, 219, 266, 382, 381, 278, 363.\n", | |
| "\n", | |
| "e. 935, 278, 347, 621, 299, 392, 358, 363.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "caad0ddbf7180e6e9f1cf54ef809d5a8", | |
| "grade": true, | |
| "grade_id": "cell-4ba31a88562b2669", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "LdCa3FpZ-9eE", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "a. 2 < 363, goes to right child; 252 < 363, goes to right child; 401 > 363, goes to left child; 398 > 363, goes to left child; 330 < 363, goes to right child; 344 < 363, goes to right child; 397 > 363, goes to left child; 363.\n", | |
| "\n", | |
| "b. 924 > 363, goes to left child; 220 < 363, goes to right child; 911 > 363, goes to left child; 244 < 363, goes to right child; 898 > 363, goes to left child; 258 < 363, goes to right child; 362 < 363, goes to right child; 363.\n", | |
| "\n", | |
| "c. 925 > 363, goes to left child; 202 < 363, goes to right child; 911 > 363, goes to left child; 240 < 363, goes to right child; 912 > 363, goes to left child; 245 < 363, goes to right child; 363.\n", | |
| "\n", | |
| "d. 2 < 363, goes to right child; 399 > 363, goes to left child; 387 > 363, goes to left child; 219 < 363, goes to right child; 266 < 363, goes to right child; 382 > 363, goes to left child; 381 > 363, goes to left child; 278 < 363, goes to right child; 363.\n", | |
| "\n", | |
| "e. 935 > 363, goes to left child; 278 < 363, goes to right child; 347 < 363, goes to right child; 621 > 363, goes to left child; 299 < 363, goes to right child; 392 > 363, goes to left child; 358 < 363, goes to right child, 363.\n", | |
| "\n", | |
| "From the breakdown above, we notice that (c) is the incorrect answer because when we go to the left child from the 911 node, we land at 240 and then we we go to 240's right child, we land at 912. This is rather impossible because 912 cannot belog to the left subtree of 911 since it is greater than 911. Following this line of logic, (e) is also pretty improbable as well since after taking the right subtree of 347, we encounter a smaller value (299) two steps later.\n", | |
| "\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "2608634a994745e8cabbc68e04197aeb", | |
| "grade": false, | |
| "grade_id": "cell-e2fe6a81a328e94e", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| }, | |
| "id": "tou0zL7p-9eG", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Question 2. Comparing complexities\n", | |
| "Complete the following table with the average vs worst case complexities for the data structures in each row.\n", | |
| "\n", | |
| "You should copy the following table and paste and edit it in the cell below. \n", | |
| "\n", | |
| "Operations | BST | Hash table using open addressing | Min heap\n", | |
| "--- | --- | --- | ---\n", | |
| "Search | | |\n", | |
| "Find max | | |\n", | |
| "Find min | | |\n", | |
| "Max extraction | | |\n", | |
| "Min extraction | | |\n", | |
| "Find successor | | |\n", | |
| "Find predecessor | | |\n", | |
| "Insert | | |\n", | |
| "Delete | | |\n", | |
| "\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "b333dea7231946830dc83e0374b46384", | |
| "grade": true, | |
| "grade_id": "cell-103e7647a8a92a95", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "p1DpUm3k-9eI", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "Operations | Binary Search Tree* | Hash table using open addressing | Min heap\n", | |
| "--- | --- | --- | ---\n", | |
| "Search | $O(h)$ | $O(1)$ | $O(n)$\n", | |
| "Find max | $O(h)$ | $O(1)$ | $O(n)$\n", | |
| "Find min | $O(h)$ | $O(1)$ | $O(1)$\n", | |
| "Max extraction | $O(h)$ | $O(1)$ | $O(n)$\n", | |
| "Min extraction | $O(h)$ | $O(1)$ | $O(1)$\n", | |
| "Find successor | $O(h)$ | NaN | NaN\n", | |
| "Find predecessor | $O(h)$ |NaN | NaN\n", | |
| "Insert | $O(h)$ | $O(1)$ | $O(1)$**\n", | |
| "Delete | $O(h)$ | $O(1)$ | $O(log n)$\n", | |
| "\n", | |
| "*For BST, $O(h)$ is for when there is an incomplete tree. If the tree is complete, the time complexity is $O(logn)$.\n", | |
| "\n", | |
| "**Worst case is $O(log n)$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "350918858ed77bb73434c159714237a6", | |
| "grade": false, | |
| "grade_id": "cell-f0b8945e898ae4eb", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| }, | |
| "id": "B_k6ZDvD-9eJ", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Question 3. Programming a recursive BST\n", | |
| "The code given in the cell below, write python code for the corresponding functions:\n", | |
| "\n", | |
| "* function `search(self, value)`: searches a *non-empty* BST rooted at the node for a node with `data=value`, returns the node if found, None otherwise\n", | |
| "* function `delete(self, value)`: if a node with data = value is present in the tree rooted at Node, deletes that node and returns the root.\n", | |
| "* function `inorder(self)`: returns a list of all data in the tree rooted at root produced using an in order traversal. When correctly implemented on a BST, the produced list will be sorted in ascending order.\n", | |
| "\n", | |
| "You may find it useful to define additional helper functions.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "a121700c0f31a273a56d108bf20ce422", | |
| "grade": false, | |
| "grade_id": "cell-699ae21855637a38", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "T94UEyN5-9eL", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "## Binary Search Tree\n", | |
| "##\n", | |
| "class Node:\n", | |
| " def __init__(self, val):\n", | |
| " self.l_child = None\n", | |
| " self.r_child = None\n", | |
| " self.parent = None\n", | |
| " self.data = val\n", | |
| "\n", | |
| " def insert(self, node):\n", | |
| " \"\"\"inserts a node into a *non-empty* tree rooted at the node, returns\n", | |
| " the root\"\"\"\n", | |
| " if self.data > node.data:\n", | |
| " if self.l_child is None:\n", | |
| " self.l_child = node\n", | |
| " node.parent = self\n", | |
| " else:\n", | |
| " self.l_child.insert(node)\n", | |
| " else:\n", | |
| " if self.r_child is None:\n", | |
| " self.r_child = node\n", | |
| " node.parent = self\n", | |
| " else:\n", | |
| " self.r_child.insert(node)\n", | |
| " return self\n", | |
| " \n", | |
| " def minimum(self):\n", | |
| " node = self\n", | |
| " while node.l_child != None:\n", | |
| " node = node.l_child\n", | |
| " return node\n", | |
| "\n", | |
| " def search_data(self, value):\n", | |
| " \"\"\"searches a *non-empty* tree rooted at the node for a node with\n", | |
| " data = value, returns the value if found, None otherwise\"\"\"\n", | |
| " node = self.search(value)\n", | |
| " if node:\n", | |
| " return node.data\n", | |
| " else:\n", | |
| " return node\n", | |
| "\n", | |
| " def search(self, value):\n", | |
| " \"\"\"searches a non-empty BST rooted at the node for a node with \n", | |
| " data = value, returns the node if found, None otherwise\"\"\"\n", | |
| " if node == None or value == node.data: # If there is no root node or \n", | |
| " return node # if the value of the node is the value of the key\n", | |
| " if value < node.data: # if the value of the key is smaller than the value of the node\n", | |
| " return self.search(node.l_child, value) # perform search recursively on left child\n", | |
| " return self.search(node.r_child, value) # perform search recursively on right child\n", | |
| " \n", | |
| " def transplant(root, u, v): \n", | |
| " if u.parent == None: # If u is the root, make v the root\n", | |
| " root = v\n", | |
| " elif u == u.parent.l_child: # If u is the left child\n", | |
| " u.parent.l_child = v # make v the left child\n", | |
| " else: # If u is the right child\n", | |
| " u.parent.r_child = v # make v the left child\n", | |
| " if v != None: # If v is non-nil\n", | |
| " v.parent = u.parent \n", | |
| " return root\n", | |
| " \n", | |
| " def delete(self, value):\n", | |
| " \"\"\" if a node with data = value is present in the tree rooted \n", | |
| " at Node, deletes that node and returns the root.\"\"\"\n", | |
| " node = self.search(root, value)\n", | |
| " if node == None: # If the node is empty\n", | |
| " return root # return None\n", | |
| " elif node.l_child == None: # If the node has no left child\n", | |
| " root = self.transplant(root, node, node.r_child) # replaces the root with the right child\n", | |
| " elif node.r_child == None: # If the node has no right child\n", | |
| " root = self.transplant(root, node, node.l_child) # replaces the root with the left child\n", | |
| " else: # If the node has both left and right children\n", | |
| " y = self.minimum(node.r_child) # we will have to get the smallest element in the right subtree\n", | |
| " # and insert it into the position of the root\n", | |
| " if y.parent != node: \n", | |
| " self.transplant(root, y, y.r_child)\n", | |
| " y.r_child = node.r_child\n", | |
| " y.r_child.parent = y\n", | |
| " root = self.transplant(root, node, y) \n", | |
| " y.l_child = node.l_child\n", | |
| " y.l_child.parent = y\n", | |
| " return root\n", | |
| "\n", | |
| " def inorder(self, root): \n", | |
| " \"\"\"returns a list of all data in the tree rooted at root produced \n", | |
| " using an in order traversal. When correctly implemented on a BST, \n", | |
| " the produced list will be sorted in ascending order.\"\"\"\n", | |
| " left = []\n", | |
| " right = []\n", | |
| " if root.l_child != None: # if there is a left child\n", | |
| " left = inorder(root.l_child) # do inorder recursively\n", | |
| " if root.r_child != None: # if there is a right child\n", | |
| " right = inorder(root.r_child) # do inorder recursively\n", | |
| " return left + [root.data] + right # combine all the data\n" | |
| ], | |
| "execution_count": 0, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "8b126b45ed170734c6d243dbde6ec892", | |
| "grade": false, | |
| "grade_id": "cell-6e99c15ebbccbcff", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| }, | |
| "id": "iVn5O7SX-9eR", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "## Question 4. Validating the BST python code\n", | |
| "\n", | |
| "### Question 4a.\n", | |
| "\n", | |
| "It is good practice to make the necessary tests in your code to ensure it produces the intended outputs. In the cells below, implement slow, but simple:\n", | |
| "* inserts,\n", | |
| "* searches,\n", | |
| "* deletes.\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "2e246944222ceb6db976ba1af84f791a", | |
| "grade": false, | |
| "grade_id": "cell-8ffe02954ab45b77", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "-MsiUUTn-9eS", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "def inorder(root): \n", | |
| " \"\"\"returns a list of all data in the tree rooted at root produced \n", | |
| " using an in order traversal. When correctly implemented on a BST, \n", | |
| " the produced list will be sorted in ascending order.\"\"\"\n", | |
| " left = []\n", | |
| " right = []\n", | |
| " if root.l_child != None: \n", | |
| " left = inorder(root.l_child)\n", | |
| " if root.r_child != None: \n", | |
| " right = inorder(root.r_child)\n", | |
| " return left + [root.data] + right\n", | |
| "\n", | |
| "def list_insert(lst, value):\n", | |
| " \"\"\"inserts value into lst in sorted order\"\"\"\n", | |
| " lst = []\n", | |
| " if len(lst) == 0:\n", | |
| " lst.append(value)\n", | |
| " elif len(lst) == 1:\n", | |
| " if value > lst[0]:\n", | |
| " lst += [value]\n", | |
| " else:\n", | |
| " lst = [value] + lst\n", | |
| " else:\n", | |
| " for i in range(1, len(lst)):\n", | |
| " if lst[i-1] <= value <= lst[i]:\n", | |
| " lst = lst[:i-1] + [value] + lst[i:]\n", | |
| " # lst.insert(i, value)" | |
| ], | |
| "execution_count": 0, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "id": "0R582vi5iUbc", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 514 | |
| }, | |
| "outputId": "82c8059e-311b-4905-9e81-27df9d5b761a" | |
| }, | |
| "source": [ | |
| "import random\n", | |
| "\n", | |
| "bst = None # bst is a misnormer, this variable contains the Node that is the root of the BST of interest\n", | |
| "lst = []\n", | |
| "\n", | |
| "# sampling with replacement\n", | |
| "for x in [Node(random.randint(0,10)) for _ in range(10)]:\n", | |
| " print('Inserting the following node: ', x.data)\n", | |
| " if not bst:\n", | |
| " bst = x\n", | |
| " else:\n", | |
| " bst.insert(x)\n", | |
| " list_insert(lst, x.data)\n", | |
| "\n", | |
| "print('In order traversal: ', bst.inorder(lst))" | |
| ], | |
| "execution_count": 44, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Inserting the following node: 8\n", | |
| "Inserting the following node: 3\n", | |
| "Inserting the following node: 6\n", | |
| "Inserting the following node: 0\n", | |
| "Inserting the following node: 8\n", | |
| "Inserting the following node: 6\n", | |
| "Inserting the following node: 4\n", | |
| "Inserting the following node: 2\n", | |
| "Inserting the following node: 9\n", | |
| "Inserting the following node: 4\n" | |
| ], | |
| "name": "stdout" | |
| }, | |
| { | |
| "output_type": "error", | |
| "ename": "AttributeError", | |
| "evalue": "ignored", | |
| "traceback": [ | |
| "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", | |
| "\u001b[0;31mAttributeError\u001b[0m Traceback (most recent call last)", | |
| "\u001b[0;32m<ipython-input-44-0c79401cb798>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0mlist_insert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdata\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'In order traversal: '\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbst\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minorder\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", | |
| "\u001b[0;32m<ipython-input-15-f794071f7e23>\u001b[0m in \u001b[0;36minorder\u001b[0;34m(self, root)\u001b[0m\n\u001b[1;32m 86\u001b[0m \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 87\u001b[0m \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 88\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0mroot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0ml_child\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 89\u001b[0m \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0minorder\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mroot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0ml_child\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 90\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mroot\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mr_child\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;31mAttributeError\u001b[0m: 'list' object has no attribute 'l_child'" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "99cadda3119181ec5d6c967d7ea15090", | |
| "grade": false, | |
| "grade_id": "cell-0e246c5c19ef7b80", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "nGFyAeYy-9eW", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "def list_delete(lst, value):\n", | |
| " \"\"\" deletes first instance of value from lst if it present\"\"\"\n", | |
| " for i in range(len(lst)):\n", | |
| " if lst[i] == value:\n", | |
| " del lst[i]\n", | |
| " return" | |
| ], | |
| "execution_count": 0, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "024018f03e113eced89d464c96d522f6", | |
| "grade": false, | |
| "grade_id": "cell-f6b55b9878c6fdf1", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "vHC7JBt4-9eb", | |
| "colab_type": "code", | |
| "colab": {} | |
| }, | |
| "source": [ | |
| "def list_search(lst, value): \n", | |
| " \"\"\" searches lst for value and returns value if present, None if it is not present\"\"\"\n", | |
| " for ele in lst:\n", | |
| " if ele == value:\n", | |
| " return ele\n", | |
| " return None" | |
| ], | |
| "execution_count": 0, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "4b67b5285b803538fc34c696acb4fce3", | |
| "grade": false, | |
| "grade_id": "cell-50a5730f995c1ec5", | |
| "locked": true, | |
| "schema_version": 1, | |
| "solution": false | |
| }, | |
| "id": "Y_1jvKp3-9ef", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "### Question 4b. \n", | |
| "Run the testing code provided in the cell below to generate a sequence of random inserts, followed by a sequence of random deletes, and finally followed by a sequence of random searches. Apply this sequence to both your BST implementation and the sorted list implementation. Do the final results both match? Does this mean your code is free of bugs? Provide your answer to these questions in the cell below the Python-code cell." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "eec63c47c423432f249945ffb72bc820", | |
| "grade": true, | |
| "grade_id": "cell-ebddd4da79a3da28", | |
| "locked": true, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": false | |
| }, | |
| "id": "8C9PNBba-9eg", | |
| "colab_type": "code", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 424 | |
| }, | |
| "outputId": "66598e01-7e2b-47ac-b990-18e3294e6a21" | |
| }, | |
| "source": [ | |
| "### Testing Code\n", | |
| "###\n", | |
| "\n", | |
| "import random\n", | |
| "\n", | |
| "bst = None # bst is a misnormer, this variable contains the Node that is the root of the BST of interest\n", | |
| "lst = []\n", | |
| "\n", | |
| "# sampling with replacement\n", | |
| "for x in [Node(random.randint(0,10)) for _ in range(10)]:\n", | |
| " print('Inserting the following node: ', x.data)\n", | |
| " if not bst:\n", | |
| " bst = x\n", | |
| " else:\n", | |
| " bst.insert(x)\n", | |
| " list_insert(lst, x.data)\n", | |
| "\n", | |
| "print('In order traversal: ', bst.inorder())\n", | |
| "\n", | |
| "for x in [random.randint(0,10) for _ in range(4)]:\n", | |
| " print('Look for the following node: ', x)\n", | |
| " if bst.search_data(x):\n", | |
| " print(' Node exists, hence removing the Node...')\n", | |
| " bst = bst.delete(x)\n", | |
| " else:\n", | |
| " print(' Node does not exist and cannot be removed!')\n", | |
| " if list_search(lst, x):\n", | |
| " print(' Element exists in list, hence removing it...!')\n", | |
| " list_delete(lst,x)\n", | |
| " else:\n", | |
| " print(' Element does not exist in list, and cannot be removed!')\n", | |
| "\n", | |
| "print('In order traversal of final BST: ', bst.inorder())\n", | |
| "print('Final list: ', lst)\n" | |
| ], | |
| "execution_count": 22, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "text": [ | |
| "Inserting the following node: 8\n", | |
| "Inserting the following node: 9\n", | |
| "Inserting the following node: 9\n", | |
| "Inserting the following node: 0\n", | |
| "Inserting the following node: 4\n", | |
| "Inserting the following node: 10\n", | |
| "Inserting the following node: 1\n", | |
| "Inserting the following node: 7\n", | |
| "Inserting the following node: 9\n", | |
| "Inserting the following node: 5\n" | |
| ], | |
| "name": "stdout" | |
| }, | |
| { | |
| "output_type": "error", | |
| "ename": "TypeError", | |
| "evalue": "ignored", | |
| "traceback": [ | |
| "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", | |
| "\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", | |
| "\u001b[0;32m<ipython-input-22-9863ab106f8c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[0mlist_insert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdata\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 15\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 16\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'In order traversal: '\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbst\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minorder\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 17\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 18\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mrandom\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrandint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;31mTypeError\u001b[0m: inorder() missing 1 required positional argument: 'root'" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "11743c20bdd473ed59d8b90c514f6176", | |
| "grade": true, | |
| "grade_id": "cell-1af64135f3359698", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| }, | |
| "id": "9gtpz6Z9-9ei", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "I didn't manage to get my code to work :( " | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment