{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

cs1001.py , Tel Aviv University, Fall 2017-2018

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recitation 9" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We discussed two data structures: Linked lists and Binary search trees. \n", "Then, we solved two (challenging) recursion exercises: Choose-sets and N-queens.\n", "\n", "#### Takeaways:\n", "- When choosing a data structure (DS) for a specific application, consider the advantages and disadvantages of this DS and then evaluate whether it fits your application.\n", "- We have proved the correctness of inorder(), which is an important skill to learn for all algorithms that we implement. \n", "- Important properties of Linked lists: \n", " - Not stored continuously in memory.\n", " - Allow for detetion and insertion after a __given__ element in $O(1)$ time.\n", " - Accessing the $i$'th element takes $O(i)$ time.\n", " - Search takes $O(n)$ time (no random access $\\implies$ no $O(\\log{n})$ search).\n", "- Important properties of Binary search trees: \n", " - Insert and find take $O(h)$ time where $h$ is the height of the tree.\n", " - When a tree containing $n$ nodes is balanced, $h = O(\\log{n})$.\n", " - Many methods in this class are implemented using recursion.\n", "- Solve as many recursion questions as possible. It gets easier after about 100." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Linked Lists" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Code from class" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "class Node():\n", " def __init__(self, val):\n", " self.value = val\n", " self.next = None\n", " \n", " def __repr__(self):\n", " #return \"[\" + str(self.value) + \",\" + str(id(self.next))+ \"]\"\n", " \n", " #for today's recitation, we print the id of self instead of self.next\n", " return \"[\" + str(self.value) + \",\" + str(id(self))+ \"]\"\n", "\n", "\n", "\n", "class Linked_list():\n", "\n", " def __init__(self, seq=None):\n", " self.next = None\n", " self.len = 0\n", " if seq != None:\n", " for x in seq[::-1]:\n", " self.add_at_start(x)\n", " \n", "\n", " def __repr__(self):\n", " out = \"\"\n", " p = self.next\n", " while p != None:\n", " out += str(p) + \" \" #str envokes __repr__ of class Node\n", " p = p.next\n", " return out\n", "\n", " \n", " def __len__(self):\n", " ''' called when using Python's len() '''\n", " return self.len\n", " \n", " \n", " def add_at_start(self, val):\n", " ''' add node with value val at the list head '''\n", " p = self\n", " tmp = p.next\n", " p.next = Node(val)\n", " p.next.next = tmp\n", " self.len += 1\n", " \n", " def add_at_end(self, val):\n", " ''' add node with value val at the list tail '''\n", " p = self\n", " while (p.next != None):\n", " p = p.next\n", " p.next = Node(val)\n", " self.len += 1\n", " \n", " \n", " def insert(self, loc, val):\n", " ''' add node with value val after location 0<=loc" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Adding elements one by one. Try using Python tutor." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[b,2491465543576] [a,2491465542904] " ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l = Linked_list()\n", "l.add_at_start(\"a\")\n", "l.add_at_start(\"b\")\n", "l" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reversing a linked list in $O(1)$ additional memory. \n", "See the code and demo here" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[a,2491465701024] [b,2491465700968] [c,2491465700912] " ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[c,2491465700912] [b,2491465700968] [a,2491465701024] " ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Node():\n", " def __init__(self, val):\n", " self.value = val\n", " self.next = None\n", " \n", " def __repr__(self):\n", " #return \"[\" + str(self.value) + \",\" + str(id(self.next))+ \"]\"\n", " \n", " #for today's recitation, we print the id of self instead of self.next\n", " return \"[\" + str(self.value) + \",\" + str(id(self))+ \"]\"\n", "\n", "\n", "class Linked_list():\n", "\n", " def __init__(self, seq=None):\n", " self.next = None\n", " self.len = 0\n", " if seq != None:\n", " for x in seq[::-1]:\n", " self.add_at_start(x)\n", " \n", "\n", " def __repr__(self):\n", " out = \"\"\n", " p = self.next\n", " while p != None:\n", " out += str(p) + \" \" #str envokes __repr__ of class Node\n", " p = p.next\n", " return out\n", "\n", " \n", " def __len__(self):\n", " ''' called when using Python's len() '''\n", " return self.len\n", " \n", " \n", " def add_at_start(self, val):\n", " ''' add node with value val at the list head '''\n", " p = self\n", " tmp = p.next\n", " p.next = Node(val)\n", " p.next.next = tmp\n", " self.len += 1\n", " \n", " def add_at_end(self, val):\n", " ''' add node with value val at the list tail '''\n", " p = self\n", " while (p.next != None):\n", " p = p.next\n", " p.next = Node(val)\n", " self.len += 1\n", " \n", " \n", " def insert(self, loc, val):\n", " ''' add node with value val after location 0<=loc node.key:\n", " if node.right == None:\n", " node.right = Tree_node(key, val)\n", " else:\n", " insert_rec(node.right, key, val)\n", " return\n", " \n", " if self.root == None: #empty tree\n", " self.root = Tree_node(key, val)\n", " else:\n", " insert_rec(self.root, key, val)\n", "\n", "\n", " def minimum(self):\n", " ''' return node with minimal key '''\n", " if self.root == None:\n", " return None\n", " node = self.root\n", " left = node.left\n", " while left != None:\n", " node = left\n", " left = node.left\n", " return node\n", "\n", "\n", " def depth(self):\n", " ''' return depth of tree, uses recursion'''\n", " def depth_rec(node):\n", " if node == None:\n", " return -1\n", " else:\n", " return 1 + max(depth_rec(node.left), depth_rec(node.right))\n", "\n", " return depth_rec(self.root)\n", "\n", "\n", " def size(self):\n", " ''' return number of nodes in tree, uses recursion '''\n", " def size_rec(node):\n", " if node == None:\n", " return 0\n", " else:\n", " return 1 + size_rec(node.left) + size_rec(node.right)\n", "\n", " return size_rec(self.root)\n", " \n", " def inorder(self):\n", " '''prints the keys of the tree in a sorted order'''\n", " def inorder_rec(node):\n", " if node == None:\n", " return\n", " inorder_rec(node.left)\n", " print(node.key)\n", " inorder_rec(node.right)\n", "\n", " inorder_rec(self.root)\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "3\n", "4\n" ] } ], "source": [ "t = Binary_search_tree()\n", "t.insert(2,\"hi\")\n", "t.insert(4,\"tea\")\n", "t.insert(1,\"mother\")\n", "t.insert(3,\"CS\")\n", "t.insert(4,\"recursion\")\n", "\n", "t.inorder()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Proof of the correctness of the inorder function (can also be found here)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Choose sets" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[]]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[[2, 1], [3, 1], [4, 1], [3, 2], [4, 2], [4, 3]]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[[4, 3, 2, 1]]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def choose_sets(lst,k):\n", " if k==0:\n", " return [[]]\n", " elif len(lst)here.\n", "\n", "First try to understand the queens() and queens_rec() functions and then try to understand how the function legal() works.\n", "\n", "Some intuition for queens_rec:\n", "\n", "assume we can find a solution for placing $k