diff options
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java')
17 files changed, 2074 insertions, 0 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/README.txt b/Data_Structures_and_Algorithms_in_Java/README.txt new file mode 100644 index 00000000..4b659a4b --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/README.txt @@ -0,0 +1,10 @@ +Contributed By: Jatin Pavagadhi +Course: mca +College/Institute/Organization: Indian Institute of Engineering Bombay +Department/Designation: System Administrator +Book Title: Data Structures and Algorithms in Java +Author: Robert Lafore +Publisher: Sams Publishing +Year of publication: 2003 +Isbn: 0672324539 +Edition: 2nd
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch1.ipynb b/Data_Structures_and_Algorithms_in_Java/ch1.ipynb new file mode 100644 index 00000000..c62ab0cb --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch1.ipynb @@ -0,0 +1,86 @@ +{ + "metadata": { + "name": "ch1" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": [ + "Chapter 1 : Overview" + ] + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": [ + "Example 1.1 Page No : 17" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "'''\n", + "demonstrates basic OOP syntax\n", + "to run this program: python BankApp\n", + "'''\n", + "\n", + "class BankAccount:\n", + " def __init__(self,openingBalance): # constructor\n", + " self.balance = openingBalance\n", + "\n", + " def deposit(self,amount): # makes deposit\n", + " self.balance = self.balance + amount; \n", + " \n", + " def withdraw(self,amount): # makes withdrawal\n", + " self.balance = self.balance - amount; \n", + "\n", + " def display(self):\n", + " # displays balance \n", + " print 'balance=' , self.balance\n", + "\n", + "# end class BankAccount\n", + "\n", + "ba1 = BankAccount(100.00) # create acct\n", + "print 'Before transactions, ',\n", + "ba1.display()\n", + "# display balance\n", + "ba1.deposit(74.35)\n", + "ba1.withdraw(20.00)\n", + "print 'After transactions, ' ,\n", + "ba1.display()" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "Before transactions, balance= 100.0\n", + "After transactions, balance= 154.35\n" + ] + } + ], + "prompt_number": 1 + }, + { + "cell_type": "code", + "collapsed": false, + "input": [], + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch10.ipynb b/Data_Structures_and_Algorithms_in_Java/ch10.ipynb new file mode 100644 index 00000000..cf44793a --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch10.ipynb @@ -0,0 +1,43 @@ +{ + "metadata": { + "name": "ch10" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 10 : 2-3-4 Trees and External Storage" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 10.1 Page No : 478" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 10.1\ndemonstrates 234 tree\n'''\nclass DataItem:\n def __init__(self,dd):\n self.dData = dd\n\n def displayItem(self):\n print '/' ,self.dData\n\nclass Node:\n def __init__(self):\n self.ORDER = 4\n self.numItems = 0\n self.parent = None\n self.childArray = [None,None,None,None]\n self.itemArray = [None,None,None]\n\n def connectChild(self,childNum,child):\n self.childArray[childNum] = child\n if(child != None):\n child.parent = self\n\n def disconnectChild(self,childNum):\n tempNode = self.childArray[childNum]\n self.childArray[childNum] = None\n return tempNode\n\n def getChild(self,childNum):\n return self.childArray[childNum]\n\n def getParent(self):\n return self.parent\n\n def isLeaf(self):\n if self.childArray[0]==None:\n return True \n return False \n\n def getNumItems(self):\n return self.numItems\n\n def getItem(self,index): # get DataItem at index\n return self.itemArray[index] \n\n def isFull(self):\n if self.numItems==self.ORDER-1:\n return True\n return False\n\n def findItem(self,key): # return index of # item (within node)\n for j in range(self.ORDER-1): \n if(self.itemArray[j] == None):\n break\n elif(self.itemArray[j].dData == key):\n return j\n return -1\n\n def insertItem(self,newItem):\n #assumes node is not full\n self.numItems += 1 # will add new item\n newKey = newItem.dData # key of new item\n j = self.ORDER - 2\n while j>=0:\n if(self.itemArray[j] == None):\n continue\n else:\n itsKey = self.itemArray[j].dData\n if(newKey < itsKey):\n self.itemArray[j+1] = self.itemArray[j]\n else:\n self.itemArray[j+1] = newItem\n return j+1 # return index to\n j -= 1\n\n self.itemArray[0] = newItem # insert new item\n return 0\n\n def removeItem(self): # remove largest item\n temp = self.itemArray[self.numItems-1] # save item\n self.itemArray[self.numItems-1] = None # disconnect it\n self.numItems -= 1 # one less item\n return temp # return item\n\n def displayNode(self):\n for j in range(self.numItems):\n self.itemArray[j].displayItem()\n print ''\n\nclass Tree234:\n def __init__(self):\n self.root = Node() # make root node\n\n def find(self,key):\n curNode = self.root\n childNumber = 0\n while(True):\n childNumber=curNode.findItem(key) \n if(childNumber != -1):\n return childNumber # found it\n elif( curNode.isLeaf() ):\n return -1 # cant find it\n else: # search deeper\n curNode = getNextChild(curNode, key)\n\n def insert(self,dValue):\n curNode = self.root\n tempItem = DataItem(dValue)\n while(True):\n if( curNode.isFull() ):\n split(curNode)\n curNode = curNode.getParent()\n curNode = getNextChild(curNode, dValue)\n elif( curNode.isLeaf() ): # if node is leaf,\n break\n else:\n curNode = getNextChild(curNode, dValue)\n curNode.insertItem(tempItem)\n\n def split(self,thisNode): # split the node\n # assumes node is full\n itemC = thisNode.removeItem() # remove items from\n itemB = thisNode.removeItem() # this node\n child2 = thisNode.disconnectChild(2) # remove children\n child3 = thisNode.disconnectChild(3) # from this nodeJava Code for a 2-3-4 Tree\n newRight = Node() # make new node\n if(thisNode==self.root):\n self.root = Node()\n parent = self.root\n self.root.connectChild(0, thisNode)\n else:\n parent = thisNode.getParent()\n itemIndex = parent.insertItem(itemB) # item B to parent\n n = parent.getNumItems()\n j = n-1\n while j > itemIndex:\n temp = parent.disconnectChild(j) # one child\n parent.connectChild(j+1, temp)\n j -= 1\n\n parent.connectChild(itemIndex+1, newRight) # deal with newRight\n newRight.insertItem(itemC) # item C to newRight\n newRight.connectChild(0, child2) # connect to 0 and 1\n newRight.connectChild(1, child3) # on newRight\n\n def getNextChild(self,theNode,theValue):\n # assumes node is not empty, not full, not a leaf\n numItems = theNode.getNumItems() \n for j in range(numItems): # for each item in node\n if( theValue < theNode.getItem(j).dData ):\n return theNode.getChild(j) # return left child\n return theNode.getChild(j)\n\n def displayTree(self):\n self.recDisplayTree(self.root, 0, 0)\n\n def recDisplayTree(self,thisNode,level, childNumber):\n print 'level=' ,level ,' child=',childNumber , ' '\n thisNode.displayNode()\n numItems = thisNode.getNumItems()\n for j in range(numItems+1):\n nextNode = thisNode.getChild(j)\n if(nextNode != None):\n self.recDisplayTree(nextNode, level+1, j)\n else:\n return\ntheTree = Tree234()\ntheTree.insert(50)\ntheTree.insert(40)\ntheTree.insert(60)\ntheTree.insert(30)\ntheTree.insert(70)\nwhile(True):\n print 'Enter first letter of show, '\n print 'insert, find, or display: ',\n choice = raw_input()\n if choice == 's':\n theTree.displayTree()\n elif choice == 'i':\n print 'Enter value to insert: '\n value = int(raw_input())\n theTree.insert(value)\n elif choice == 'f':\n print 'Enter value to find: ',\n value = int(raw_input())\n found = theTree.find(value)\n if(found != -1):\n print 'Found: ', value\n else:\n print 'Could not find', value \n else:\n print 'Invalid entry'\n", + "language": "python", + "metadata": {}, + "outputs": [], + "prompt_number": "*" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch11.ipynb b/Data_Structures_and_Algorithms_in_Java/ch11.ipynb new file mode 100644 index 00000000..5756b776 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch11.ipynb @@ -0,0 +1,96 @@ +{ + "metadata": { + "name": "ch11" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 11 : Hash Tables" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 11.1 Page No : 535" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 11.1\ndemonstrates hash table with linear probing\n'''\nclass DataItem:\n def __init__(self,ii):\n self.iData = ii\n\n def getKey(self):\n return self.iData\n\nclass HashTable:\n def __init__(self,size):\n self.hashArray = [] # array is the hash table\n for i in range(size):\n self.hashArray.append(DataItem(0))\n self.arraySize = size\n self.nonItem = None # for deleted items\n\n def displayTable(self):\n print 'Table: ',\n for j in range(self.arraySize):\n if(self.hashArray[j] != None):\n print self.hashArray[j].getKey() ,\n else:\n print '** ' ,\n print ''\n\n\n def hashFunc(self,key):\n return key % self.arraySize\n\n # insert a DataItem\n def insert(self,item):\n key = item.getKey() # extract key\n hashVal = self.hashFunc(key) # hash the key\n while(self.hashArray[hashVal] != None and self.hashArray[hashVal].getKey() != -1):\n hashVal += 1\n hashVal %= self.arraySize # wraparound if necessary\n self.hashArray[hashVal] = item # insert item\n\n def delete(self,key): # delete a DataItem\n hashVal = hashFunc(key) # hash the key\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n temp = self.hashArray[hashVal] # save item\n self.hashArray[hashVal] = nonItem # delete item\n return temp # return item\n hashVal += 1\n hashVal %= self.arraySize # for wraparound\n return None # cant find item\n\n def find(self,key): # find item with key\n # (assumes table not full)\n hashVal = hashFunc(key) # hash the key\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n return self.hashArray[hashVal] # yes, return item\n hashVal += 1 # add the step\n hashVal %= self.arraySize\n # for wraparound\n return None # cant find item\n\nprint 'Enter size of hash table: ',\nsize = int(raw_input())\nprint 'Enter initial number of items: ',\nn = int(raw_input()) # make table\ntheHashTable = HashTable(size)\nkeysPerCell = 10\nimport random\nfor j in range(n): # insert data\n aKey = int(random.random() * keysPerCell * size)\n aDataItem = DataItem(aKey) \n theHashTable.insert(aDataItem)\n\nwhile(True):\n print 'Enter first letter of show, '\n print 'insert, find, delete, or traverse: ',\n choice = raw_input()\n if choice == 's':\n theHashTable.displayTable()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n aDataItem = DataItem(aKey)\n theHashTable.insert(aDataItem)\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n\n elif choice=='d':\n print 'Enter key value to delete: ',\n value = int(raw_input())\n theHashTable.delete(value)\n else:\n print 'Invalid entry'\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter size of hash table: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "12\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter initial number of items: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "8\n" + } + ], + "prompt_number": "*" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 11.2 Page no: 546" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 11.2\ndemonstrates hash table with double hashing\n'''\nclass DataItem:\n def __init__(self,ii):\n self.iData = ii\n\n def getKey(self):\n return self.iData\n\nclass HashTable:\n def __init__(self,size):\n self.hashArray = [] # array is the hash table\n for i in range(size):\n self.hashArray.append(DataItem(0))\n self.arraySize = size\n self.nonItem = None # for deleted items\n\n def displayTable(self):\n print 'Table: ',\n for j in range(self.arraySize):\n if(self.hashArray[j] != None):\n print self.hashArray[j].getKey() ,\n else:\n print '** ' ,\n print ''\n\n def hashFunc1(self,key):\n return key % self.arraySize\n\n def hashFunc2(self,key):\n # non-zero, less than array size, different from hF1\n # array size must be relatively prime to 5, 4, 3, and 2\n return 5 - key % 5\n \n # insert a DataItem\n def insert(self,key,item):\n # (assumes table not full)\n hashVal = self.hashFunc1(key) # hash the key\n stepSize = self.hashFunc2(key) # get step size\n # until empty cell or -1\n while(self.hashArray[hashVal] != None and self.hashArray[hashVal].getKey() != -1):\n hashVal += stepSize # add the step\n hashVal %= self.arraySize # for wraparound\n self.hashArray[hashVal] = item # insert item\n\n def delete(self,key): # delete a DataItem\n hashVal = hashFunc1(key) # hash the key\n stepSize = hashFunc2(key) # get step size\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n temp = self.hashArray[hashVal] # save item\n self.hashArray[hashVal] = nonItem # delete item\n return temp # return item\n hashVal += stepSize # add the step\n hashVal %= self.arraySize # for wraparound\n return None # cant find item\n\n def find(self,key): # find item with key\n # (assumes table not full)\n hashVal = hashFunc1(key) # hash the key\n stepSize = hashFunc2(key) # get step size\n while(self.hashArray[hashVal] != None): # until empty cell,\n # is correct hashVal?\n if(self.hashArray[hashVal].getKey() == key):\n return self.hashArray[hashVal] # yes, return item\n hashVal += stepSize # add the step\n hashVal %= self.arraySize\n # for wraparound\n return None # cant find item\n\nprint 'Enter size of hash table: ',\nsize = int(raw_input())\nprint 'Enter initial number of items: ',\nn = int(raw_input()) # make table\ntheHashTable = HashTable(size)\nimport random\nfor j in range(n): # insert data\n aKey = int(random.random() * 2 * size)\n aDataItem = DataItem(aKey) \n theHashTable.insert(aKey, aDataItem)\n\nwhile(True):\n print 'Enter first letter of show, '\n print 'insert, find, delete, or traverse: ',\n choice = raw_input()\n if choice == 's':\n theHashTable.displayTable()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n aDataItem = DataItem(aKey)\n theHashTable.insert(aKey, aDataItem)\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n\n elif choice=='d':\n print 'Enter key value to delete: ',\n value = int(raw_input())\n theHashTable.delete(value)\n else:\n print 'Invalid entry'\n", + "language": "python", + "metadata": {}, + "outputs": [], + "prompt_number": "*" + }, + { + "cell_type": "heading", + "level": 2, + "metadata": {}, + "source": "Example 11.3 Page no : 555" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 11.3\ndemonstrates hash table with separate chaining\n'''\n\nclass Link:\n def __init__(self,ii):\n self.iData = ii\n\n def getKey(self):\n return self.iData\n\n def displayLink(self):\n print self.iData ,\n\nclass SortedList:\n def __init__(self):\n self.first = None\n\n def insert(self,theLink): # insert link, in order\n key = theLink.getKey()\n self.previous = None # start at self.first\n current = self.first # until end of list,\n while( current != None and key > current.getKey() ): # or current > key,\n self.previous = current \n current = current.next # go to next item\n if(self.previous==None): # if beginning of list,\n self.first = theLink\n else: # not at beginning,\n self.previous.next = theLink\n theLink.next = current # new link --> current\n\n def delete(self,key): # delete link\n # (assumes non-empty list)\n self.previous = None # start at self.first\n current = self.first # until end of list,\n while( current != None and key != current.getKey() ): # or key == current,\n self.previous = current\n current = current.next # go to next link\n if(self.previous==None):\n self.first = self.first.next\n else:\n self.previous.next = current.next \n\n def find(self,key): # find link\n current = self.first # start at self.first\n # until end of list,\n while(current != None and current.getKey() <= key): # or key too small,\n if(current.getKey() == key):# is this the link?\n return current # found it, return link\n current = current.next # go to next item\n return None # didnt find it\n\n def displayList(self):\n print 'List (self.first-->last): ',\n current = self.first # start at beginning of list\n while(current != None): # until end of list,\n current.displayLink() # print data\n current = current.next # move to next link\n print ''\n\nclass HashTable:\n def __init__(self,size):\n self.hashArray = [] # array is the hash table\n for i in range(size):\n self.hashArray.append(SortedList())\n self.arraySize = size\n self.nonItem = None # for deleted items\n\n def displayTable(self):\n print 'Table: ',\n for j in range(self.arraySize):\n print j, \n self.hashArray[j].displayList()\n\n def hashFunc(self,key):\n return key % self.arraySize\n\n def insert(self,theLink):\n key = theLink.getKey()\n hashVal = self.hashFunc(key)\n self.hashArray[hashVal].insert(theLink)\n\n def delete(self,key): # delete a DataItem\n hashVal = self.hashFunc(key) # hash the key\n self.hashArray[hashVal].delete(key) # delete link\n\n def find(self,key): # find link\n hashVal = self.hashFunc(key)# hash the key\n theLink = self.hashArray[hashVal].find(key) # get link\n return theLink # return link\n\nkeysPerCell = 100 \nprint 'Enter size of hash table: ',\nsize = int(raw_input())\nprint 'Enter initial number of items: ',\nn = int(raw_input()) # make table\ntheHashTable = HashTable(size)\nimport random\nfor j in range(n): # insert data\n aKey = int(random.random() * 2 * size)\n aDataItem = Link(aKey) \n theHashTable.insert(aDataItem)\n\nwhile(True):\n print 'Enter self.first letter of show, '\n print 'insert, find, delete, or show: ',\n choice = raw_input()\n if choice == 's':\n theHashTable.displayTable()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n aDataItem = Link(aKey)\n theHashTable.insert(aDataItem)\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n\n elif choice=='d':\n print 'Enter key value to delete: ',\n value = int(raw_input())\n theHashTable.delete(value)\n else:\n print 'Invalid entry'\n", + "language": "python", + "metadata": {}, + "outputs": [], + "prompt_number": "*" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch12.ipynb b/Data_Structures_and_Algorithms_in_Java/ch12.ipynb new file mode 100644 index 00000000..8343fffc --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch12.ipynb @@ -0,0 +1,158 @@ +{ + "metadata": { + "name": "ch12" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 12 : Heaps " + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 12.1 Page no : 592" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 12.1\ndemonstrates heaps\n'''\n\nclass Node: \n def __init__(self,key):\n # constructorJava Code for Heaps\n self.iData = key\n \n def getKey(self):\n return self.iData\n\n def setKey(self,i):\n self.iData = i\n\nclass Heap:\n def __init__(self,mx):\n self.maxSize = mx\n self.currentSize = 0\n self.heapArray = []\n for i in range(self.maxSize):\n self.heapArray.append(Node(0))\n\n def isEmpty(self):\n return self.currentSize==0\n\n def insert(self,key):\n if(self.currentSize==self.maxSize):\n return False\n newNode = Node(key)\n self.heapArray[self.currentSize] = newNode\n self.trickleUp(self.currentSize)\n self.currentSize += 1\n return True\n\n def trickleUp(self,index):\n parent = (index-1) / 2\n bottom = self.heapArray[index]\n while( index > 0 and self.heapArray[parent].getKey() < bottom.getKey() ):\n self.heapArray[index] = self.heapArray[parent] # move it down\n index = parent\n parent = (parent-1) / 2\n self.heapArray[index] = bottom\n\n def remove(self): # delete item with max key\n # (assumes non-empty list)\n root = self.heapArray[0]\n self.currentSize -= 1\n self.heapArray[0] = self.heapArray[self.currentSize]\n self.trickleDown(0)\n return root\n\n def trickleDown(self,index):\n top = self.heapArray[index] # save root\n while(index < self.currentSize/2): # while node has at\n leftChild = 2*index+1\n rightChild = leftChild+1 # find larger child\n if(rightChild < self.currentSize and self.heapArray[leftChild].getKey() < self.heapArray[rightChild].getKey()):\n largerChild = rightChild\n else:\n largerChild = leftChild\n if( top.getKey() >= self.heapArray[largerChild].getKey() ):\n break\n # shift child up\n self.heapArray[index] = self.heapArray[largerChild]\n index = largerChild # go down\n\n self.heapArray[index] = top # root to indexJava Code for Heaps\n \n def change(self,index,newValue):\n if(index<0 or index>=self.currentSize):\n return False\n oldValue = self.heapArray[index].getKey() # remember old\n self.heapArray[index].setKey(newValue) # change to new\n if(oldValue < newValue): # if raised,\n trickleUp(index) # trickle it up\n else: # if lowered,\n trickleDown(index) # trickle it down\n return True\n\n def displayHeap(self):\n print 'self.heapArray: ', # array format\n for m in range(self.currentSize):\n if(self.heapArray[m] != None):\n print self.heapArray[m].getKey(),\n else:\n print '-- ' ,\n print ''\n nBlanks = 32\n itemsPerRow = 1\n column = 0\n j = 0\n # current item\n dots = '...............................'\n print dots+dots\n # dotted top line\n while(self.currentSize > 0):\n if(column == 0):\n for k in range(nBlanks):\n print ' ' ,\n print self.heapArray[j].getKey() ,\n j += 1 \n if(j == self.currentSize):\n break # done?\n column += 1\n if(column==itemsPerRow): # end of row?\n nBlanks /= 2 # half the blanks\n itemsPerRow *= 2 # twice the items\n column = 0 # start over on\n print ''\n else: # next item on row\n for k in range(nBlanks*2-2):\n print ' ', # interim blanks\n print '\\n' +dots+dots \n\ntheHeap = Heap(31) # make a Heap max size 31\ntheHeap.insert(70)\ntheHeap.insert(40)\ntheHeap.insert(50)\ntheHeap.insert(20)\ntheHeap.insert(60)\ntheHeap.insert(100)\ntheHeap.insert(80)\ntheHeap.insert(30)\ntheHeap.insert(10)\ntheHeap.insert(90)\nwhile(True):\n print 'Enter first letter of show, insert, remove, change: ',\n choice = raw_input()\n if choice == 's':\n theHeap.displayHeap()\n elif choice == 'i':\n print 'Enter value to key to insert: '\n value = int(raw_input())\n success = theHeap.insert(value)\n if not success:\n print \"Can't insert heap full\"\n elif choice == 'f':\n print 'Enter key value to find: ',\n value = int(raw_input())\n aDataItem = theHashTable.find(aKey)\n if(aDataItem != None):\n print 'Found ' , aKey\n else:\n print 'Could not find ' , aKey\n elif choice=='r':\n if not theHeap.isEmpty():\n theHeap.remove()\n else:\n print \"Can't remove heap empty\"\n elif choice=='c':\n print 'Enter current index of item: ',\n value = int(raw_input())\n print \"Enter new key: \",\n value2 = int(raw_input())\n success = theHeap.change(value, value2)\n if( not success ):\n print 'Invalid index'\n else:\n print \"Invalid entry\"\n break ", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, insert, remove, change: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "s\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " self.heapArray: 100 90 80 30 60 50 70 20 10 40 \n..............................................................\n 100 \n 90 80 \n 30 60 50 70 \n 20 10 40 \n..............................................................\nEnter first letter of show, insert, remove, change: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "i\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter value to key to insert: \n" + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "53\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter first letter of show, insert, remove, change: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "s\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " self.heapArray: 100 90 80 30 60 50 70 20 10 40 53 \n..............................................................\n 100 \n 90 80 \n 30 60 50 70 \n 20 10 40 53 \n..............................................................\nEnter first letter of show, insert, remove, change: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "r\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, insert, remove, change: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "s\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " self.heapArray: 90 60 80 30 53 50 70 20 10 40 \n..............................................................\n 90 \n 60 80 \n 30 53 50 70 \n 20 10 40 \n..............................................................\nEnter first letter of show, insert, remove, change: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Invalid entry\n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 12.2 Page no : 605" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 12.2\ndemonstrates heap sort\n'''\nclass Node: \n def __init__(self,key):\n # constructorJava Code for Heaps\n self.iData = key\n \n def getKey(self):\n return self.iData\n\n def setKey(self,i):\n self.iData = i\n\nclass Heap:\n def __init__(self,mx):\n self.maxSize = mx\n self.currentSize = 0\n self.heapArray = []\n for i in range(self.maxSize):\n self.heapArray.append(Node(0))\n\n def isEmpty(self):\n return self.currentSize==0\n\n def insert(self,key):\n if(self.currentSize==self.maxSize):\n return False\n newNode = Node(key)\n self.heapArray[self.currentSize] = newNode\n self.trickleUp(self.currentSize)\n self.currentSize += 1\n return True\n\n def remove(self): # delete item with max key\n # (assumes non-empty list)\n root = self.heapArray[0]\n self.currentSize -= 1\n self.heapArray[0] = self.heapArray[self.currentSize]\n self.trickleDown(0)\n return root\n\n def trickleDown(self,index):\n top = self.heapArray[index] # save root\n while(index < self.currentSize/2): # while node has at\n leftChild = 2*index+1\n rightChild = leftChild+1 # find larger child\n if(rightChild < self.currentSize and self.heapArray[leftChild].getKey() < self.heapArray[rightChild].getKey()):\n largerChild = rightChild\n else:\n largerChild = leftChild\n if( top.getKey() >= self.heapArray[largerChild].getKey() ):\n break\n # shift child up\n self.heapArray[index] = self.heapArray[largerChild]\n index = largerChild # go down\n self.heapArray[index] = top # root to indexJava Code for Heaps\n\n def displayHeap(self):\n print 'self.heapArray: ', # array format\n for m in range(self.currentSize):\n if(self.heapArray[m] != None):\n print self.heapArray[m].getKey(),\n else:\n print '-- ' ,\n print ''\n nBlanks = 32\n itemsPerRow = 1\n column = 0\n j = 0\n # current item\n dots = '...............................'\n print dots+dots\n # dotted top line\n while(self.currentSize > 0):\n if(column == 0):\n for k in range(nBlanks):\n print ' ' ,\n print self.heapArray[j].getKey() ,\n j += 1 \n if(j == self.currentSize):\n break # done?\n column += 1\n if(column==itemsPerRow): # end of row?\n nBlanks /= 2 # half the blanks\n itemsPerRow *= 2 # twice the items\n column = 0 # start over on\n print ''\n else: # next item on row\n for k in range(nBlanks*2-2):\n print ' ', # interim blanks\n print '\\n' +dots+dots \n \n def displayArray(self):\n for j in range(self.maxSize):\n print self.heapArray[j].getKey() ,\n print ''\n\n def insertAt(self,index,newNode):\n self.heapArray[index] = newNode\n\n def incrementSize(self):\n self.currentSize += 1\n\n\nprint 'Enter number of items: ',\nsize = int(raw_input())\ntheHeap = Heap(size)\nimport random\nfor j in range(size): # fill array with\n r = int(random.random()*100)\n newNode = Node(r)\n theHeap.insertAt(j, newNode)\n theHeap.incrementSize()\nprint 'Random: ',\ntheHeap.displayArray() # display random array\nj = size/2 - 1\nwhile j >= 0:\n theHeap.trickleDown(j)\n j -= 1\nprint 'Heap: ',\ntheHeap.displayArray()\ntheHeap.displayHeap()\nj = size - 1\nwhile j >= 0:\n biggestNode = theHeap.remove()\n theHeap.insertAt(j, biggestNode)\n j -= 1\n \nprint 'Sorted: ',\ntheHeap.displayArray()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter number of items: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "10\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Random: 21 55 43 65 70 16 47 22 51 73 \nHeap: 73 70 47 65 55 16 43 22 51 21 \nself.heapArray: 73 70 47 65 55 16 43 22 51 21 \n..............................................................\n 73 \n 70 47 \n 65 55 16 43 \n 22 51 21 \n..............................................................\nSorted: 16 21 22 43 47 51 55 65 70 73 \n" + } + ], + "prompt_number": 3 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch13.ipynb b/Data_Structures_and_Algorithms_in_Java/ch13.ipynb new file mode 100644 index 00000000..cab6d6e8 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch13.ipynb @@ -0,0 +1,112 @@ +{ + "metadata": { + "name": "ch13" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 13 : Graphs" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 13.1 Page no: 631" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 13.1\ndemonstrates depth-first search\n'''\nclass StackX:\n def __init__(self):\n self.st = [] # make array\n self.top = -1\n\n def push(self,j): # put item on stack\n self.top += 1\n self.st.append(j)\n\n def pop(self): # take item off stack\n self.top -= 1\n return self.st.pop()\n\n def peek(self): # peek at top of stack\n return self.st[self.top]\n \n def isEmpty(self): # true if nothing on stack-\n return self.top == -1\n\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = False\n\nclass Graph:\n def __init__(self):\n self.vertexList = [] # adjacency matrix\n self.adjMat = []\n self.nVerts = 0\n for j in range(20): # set adjacency\n l = []\n for k in range(20):\n l.append(0)\n self.adjMat.append(l)\n self.theStack = StackX()\n\n def addVertex(self,lab):\n self.vertexList.append( Vertex(lab))\n self.nVerts += 1\n\n def addEdge(self,start, end):\n self.adjMat[start][end] = 1\n self.adjMat[end][start] = 1\n\n def displayVertex(self,v):\n print self.vertexList[v].label ,\n\n def dfs(self): # depth-first search # begin at vertex 0\n self.vertexList[0].wasVisited = True # mark it\n self.displayVertex(0) # display it\n self.theStack.push(0) # push it\n while( not self.theStack.isEmpty() ): # until stack empty,\n # get an unvisited vertex adjacent to stack top\n v = self.getAdjUnvisitedVertex( self.theStack.peek() )\n if(v == -1): # if no such vertex,\n self.theStack.pop()\n else: # if it exists,\n self.vertexList[v].wasVisited = True # mark it\n self.displayVertex(v) # display it\n self.theStack.push(v) # push it\n\n # stack is empty, so we're done\n for j in range(self.nVerts): # reset flags\n self.vertexList[j].wasVisited = False # end dfs\n\n def getAdjUnvisitedVertex(self,v):\n for j in range(self.nVerts):\n if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):\n return j\n return -1\n\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for dfs)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1)\ntheGraph.addEdge(1,2)\ntheGraph.addEdge(0,3)\ntheGraph.addEdge(3,4)\nprint 'Visits: ',\ntheGraph.dfs() # depth-first search", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Visits: A B C D E\n" + } + ], + "prompt_number": 1 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 13.2 Page no : 639" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 13.2\ndemonstrates breadth-first search\n'''\nclass Queue:\n def __init__(self): # constructor\n self.SIZE = 20\n self.queArray = []\n for i in range(20):\n self.queArray.append(0)\n self.front = 0\n self.rear = -1\n\n def insert(self,j): # put item at self.rear of queue\n if(self.rear == self.SIZE-1):\n self.rear = -1\n self.rear += 1\n self.queArray[self.rear] = j\n\n def remove(self): # take item from front of queue\n temp = self.queArray[self.front]\n self.front += 1\n if(self.front == self.SIZE):\n self.front = 0\n return temp\n\n def isEmpty(self): # true if queue is empty\n return ( self.rear+1==self.front or (self.front+self.SIZE-1==self.rear) )\n\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = False\n\nclass Graph:\n def __init__(self):\n self.vertexList = [] # adjacency matrix\n self.adjMat = []\n self.nVerts = 0\n for j in range(20): # set adjacency\n l = []\n for k in range(20):\n l.append(0)\n self.adjMat.append(l)\n self.theQueue = Queue()\n\n def addVertex(self,lab):\n self.vertexList.append( Vertex(lab))\n self.nVerts += 1\n\n def addEdge(self,start, end):\n self.adjMat[start][end] = 1\n self.adjMat[end][start] = 1\n\n def displayVertex(self,v):\n print self.vertexList[v].label ,\n\n def bfs(self): # breadth-first search\n # begin at vertex 0\n self.vertexList[0].wasVisited = True # mark it\n self.displayVertex(0) # display it\n self.theQueue.insert(0) # insert at tail\n while( not self.theQueue.isEmpty() ): # until queue empty,\n v1 = self.theQueue.remove() # remove vertex at head\n # until it has no unvisited neighbors\n while( self.getAdjUnvisitedVertex(v1) != -1 ):\n v2 = self.getAdjUnvisitedVertex(v1)\n self.vertexList[v2].wasVisited = True # mark it\n self.displayVertex(v2) # display it\n self.theQueue.insert(v2) # insert it\n for j in range(self.nVerts): # reset flags\n self.vertexList[j].wasVisited = False\n\n def getAdjUnvisitedVertex(self,v):\n for j in range(self.nVerts):\n if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):\n return j\n return -1\n\n\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for dfs)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1)\ntheGraph.addEdge(1,2)\ntheGraph.addEdge(0,3)\ntheGraph.addEdge(3,4)\nprint 'Visits: ',\ntheGraph.bfs() # breadth-first search", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Visits: A B D C E\n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 13.3 Page no : 645" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 13.3\ndemonstrates minimum spanning tree\n'''\nclass StackX:\n def __init__(self):\n self.st = [] # make array\n self.top = -1\n\n def push(self,j): # put item on stack\n self.top += 1\n self.st.append(j)\n\n def pop(self): # take item off stack\n self.top -= 1\n return self.st.pop()\n\n def peek(self): # peek at top of stack\n return self.st[self.top]\n \n def isEmpty(self): # true if nothing on stack-\n return self.top == -1\n\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = False\n\nclass Graph:\n def __init__(self):\n self.vertexList = [] # adjacency matrix\n self.adjMat = []\n self.nVerts = 0\n for j in range(20): # set adjacency\n l = []\n for k in range(20):\n l.append(0)\n self.adjMat.append(l)\n self.theStack = StackX()\n\n def addVertex(self,lab):\n self.vertexList.append( Vertex(lab))\n self.nVerts += 1\n\n def addEdge(self,start, end):\n self.adjMat[start][end] = 1\n self.adjMat[end][start] = 1\n\n def displayVertex(self,v):\n print self.vertexList[v].label ,\n\n def mst(self): # minimum spanning tree (depth first)\n # start at 0\n self.vertexList[0].wasVisited =True\n # mark it\n self.theStack.push(0)\n # push it\n while(not self.theStack.isEmpty() ):\n # until stack empty\n # get stack top\n currentVertex = self.theStack.peek()\n # get next unvisited neighbor \n v = self.getAdjUnvisitedVertex(currentVertex)\n if(v == -1):\n # if no more neighbors\n self.theStack.pop()\n else:\n # got a neighbor\n self.vertexList[v].wasVisited = True # mark it\n self.theStack.push(v)\n # push it\n # display edge\n self.displayVertex(currentVertex)\n # from currentV\n self.displayVertex(v)\n # to v\n print ' ',\n for j in range(self.nVerts):\n # reset flags\n self.vertexList[j].wasVisited = False\n\n def getAdjUnvisitedVertex(self, v):\n for j in range(self.nVerts):\n if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):\n return j\n return -1\n\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for mst)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3Topological Sorting with Directed Graphs\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1) \ntheGraph.addEdge(0,2)\ntheGraph.addEdge(0,3) \ntheGraph.addEdge(0,4) \ntheGraph.addEdge(1,2) \ntheGraph.addEdge(1,3)\ntheGraph.addEdge(1,4) \ntheGraph.addEdge(2,3) \ntheGraph.addEdge(2,4) \ntheGraph.addEdge(3,4) \nprint 'Minimum spanning tree: ',\ntheGraph.mst() # minimum spanning tree", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Minimum spanning tree: A B B C C D D E \n" + } + ], + "prompt_number": 3 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 13.4 page No : 657" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 13.4\ndemonstrates topological sorting\n'''\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = False\n\nclass Graph:\n def __init__(self):\n self.vertexList = [] # adjacency matrix\n self.adjMat = []\n self.nVerts = 0\n for j in range(20): # set adjacency\n l = []\n for k in range(20):\n l.append(0)\n self.adjMat.append(l)\n\n def addVertex(self,lab):\n self.vertexList.append( Vertex(lab))\n self.nVerts += 1\n\n def addEdge(self,start, end):\n self.adjMat[start][end] = 1\n self.adjMat[end][start] = 1\n\n def displayVertex(self,v):\n print self.vertexList[v].label ,\n\n def topo(self): # topological sort\n orig_nVerts = self.nVerts # remember how many verts\n while(self.nVerts > 0): # while vertices remain,\n # get a vertex with no successors, or -1\n currentVertex = self.noSuccessors()\n if(currentVertex == -1):\n # must be a cycleTopological Sorting with Directed Graphs\n print 'ERROR: Graph has cycles'\n return\n\n # insert vertex label in sorted array (start at end)\n self.sortedArray[nVerts-1] = self.vertexList[currentVertex].label\n self.deleteVertex(currentVertex)\n print 'Topologically sorted order: '\n for j in range(orig_nVerts):\n print sortedArray[j] ,\n print ''\n\n def noSuccessors(self): # returns vert with no successors\n # (or -1 if no such verts)\n isEdge = None\n for row in range(self.nVerts): # for each vertex,\n isEdge = False\n # check edges\n for col in range(self.nVerts):\n if( self.adjMat[row][col] > 0 ): # if edge to\n # another,\n isEdge = True\n break\n if( not isEdge ):\n # if no edges,\n return row\n return -1\n\n def deleteVertex(self,delVert):\n if(delVert != self.nVerts-1):\n # if not last vertex,\n # delete from vertexList\n for j in range(self.nVerts-1):\n self.vertexList[j] = self.vertexList[j+1]\n # delete row from adjMat\n for row in range(self.nVerts-1):\n self.moveRowUp(row, nVerts)\n # delete col from adjMat\n for col in range(self.nVerts-1):\n self.moveColLeft(col, nVerts-1)\n self.nVerts -= 1\n\n def moveRowUp(self,row,length):\n for col in range(length):\n self.adjMat[row][col] = self.adjMat[row+1][col]\n\n def moveColLeft(self,col, length):\n for row in range(self.length):\n self.adjMat[row][col] = self.adjMat[row][col+1]\n\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addVertex('F') # 5\ntheGraph.addVertex('G') # 6\ntheGraph.addVertex('H') # 7Connectivity in Directed Graphs\ntheGraph.addEdge(0,3)\ntheGraph.addEdge(0,4)\ntheGraph.addEdge(1,4)\ntheGraph.addEdge(2,5)\ntheGraph.addEdge(3,6)\ntheGraph.addEdge(4,6)\ntheGraph.addEdge(5,7)\ntheGraph.addEdge(6,7)\ntheGraph.topo() # do the sort", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "ERROR: Graph has cycles\n" + } + ], + "prompt_number": 4 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch14.ipynb b/Data_Structures_and_Algorithms_in_Java/ch14.ipynb new file mode 100644 index 00000000..7895bf4f --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch14.ipynb @@ -0,0 +1,63 @@ +{ + "metadata": { + "name": "ch14" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 14 : Weighted Graphs" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 14.1 Page no: 681" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 14.1\ndemonstrates minimum spanning tree with weighted graphs\n'''\nclass Edge:\n def __init__(self,sv,dv,d): # constructor\n self.srcVert = sv\n self.destVert = dv\n self.distance = d\n\nclass PriorityQ:\n def __init__(self):\n # constructor\n self.queArray = []\n self.size = 0\n def insert(self,item): # insert item in sorted order\n self.queArray.append(item)\n b = self.size\n for j in range(self.size): # find place to insert\n if( item.distance >= self.queArray[j].distance ):\n b = j\n break\n for k in range(self.size-1,b-1,-1):#=self.size-1 k>=j k--) # move items up\n self.queArray[k+1] = self.queArray[k]\n self.queArray[b] = item\n # insert item\n self.size += 1\n\n def removeMin(self): # remove minimum item\n self.size -= 1\n return self.queArray[self.size] \n\n def removeN(self,n): # remove item at n\n for j in range(n,self.size-1): # move items down\n self.queArray[j] = self.queArray[j+1]\n self.size -= 1\n\n def peekMin(self): # peek at minimum item\n return self.self.queArray[self.size-1] \n\n def size(self): # return number of items\n return self.size\n\n def isEmpty(self): # true if queue is empty\n return (self.size==0) \n\n def peekN(self,n): # peek at item n\n return self.queArray[n]\n\n def find(self,findDex): # find item with specified\n # self.destVert value\n for j in range(self.size-1):\n if(self.queArray[j].destVert == findDex):\n return j\n return -1\n\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.isInTree = False\n\nclass Graph:\n def __init__(self):\n self.vertexList = [] # adjacency matrix\n self.adjMat = []\n self.nVerts = 0\n for j in range(20): # set adjacency\n l = []\n for k in range(20):\n l.append(1000000)\n self.adjMat.append(l)\n self.thePQ = PriorityQ()\n self.nTree = 0\n self.currentVert = 0\n\n def addVertex(self,lab):\n self.vertexList.append( Vertex(lab))\n self.nVerts += 1\n\n def addEdge(self,start, end,weight):\n self.adjMat[start][end] = weight\n self.adjMat[end][start] = weight\n\n\n def displayVertex(self,v):\n print self.vertexList[v].label ,\n\n def mstw(self):\n self.currentVert = 0 # minimum spanning tree\n # start at 0\n while(self.nTree < self.nVerts-1): # while not all verts in tree\n # put self.currentVert in tree\n self.vertexList[self.currentVert].isInTree = True\n self.nTree += 1\n # insert edges adjacent to self.currentVert into PQ\n for j in range(self.nVerts): # for each vertex,\n if(j==self.currentVert): # skip if its us\n continue\n if(self.vertexList[j].isInTree): # skip if in the tree\n continue\n self.distance = self.adjMat[self.currentVert][j]\n if( self.distance == 1000000): # skip if no edge\n continue\n self.putInPQ(j, self.distance) # put it in PQ (maybe)\n if(self.thePQ.size==0): # no vertices in PQ?\n print 'GRAPH NOT CONNECTED',\n return\n # remove edge with minimum self.distance, from PQ\n theEdge = self.thePQ.removeMin()\n sourceVert = theEdge.srcVert\n self.currentVert = theEdge.destVert\n # display edge from source to current\n print self.vertexList[sourceVert].label ,self.vertexList[self.currentVert].label, \" \",\n\n for j in range(self.nVerts): # unmark vertices\n self.vertexList[j].isIsTree = False\n\n def putInPQ(self,newVert,newDist): # is there another edge with the same destination vertex?\n queueIndex = self.thePQ.find(newVert)\n if(queueIndex != -1): # got edges index\n tempEdge = self.thePQ.peekN(queueIndex) # get edge\n oldDist = tempEdge.distance\n if(oldDist > newDist): # if new edge shorter,\n self.thePQ.removeN(queueIndex) # remove old edge\n theEdge = Edge(self.currentVert, newVert, newDist)\n self.thePQ.insert(theEdge)# insert new edge\n # else no action just leave the old vertex there\n else: # no edge with same destination vertex\n # so insert new one\n theEdge = Edge(self.currentVert, newVert, newDist)\n self.thePQ.insert(theEdge)\n\n\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for mst)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addVertex('F') # 5\ntheGraph.addEdge(0, 1, 16) # AB\ntheGraph.addEdge(0, 3, 24) # AD\n\ntheGraph.addEdge(1,2,1)\ntheGraph.addEdge(1,3,5)\ntheGraph.addEdge(1,4,2)\ntheGraph.addEdge(2,3,6)\ntheGraph.addEdge(2,4,8)\ntheGraph.addEdge(2,5,26)\ntheGraph.addEdge(3,4,142)\ntheGraph.addEdge(4,5,17)\n\nprint 'Minimum spanning tree: ',\ntheGraph.mstw() # minimum spanning tree", + "language": "python", + "metadata": {}, + "outputs": [] + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 14.2 Page 703" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 14.2\ndemonstrates shortest path with weighted, directed graphs\n'''\nclass DistPar:\n def __init__(self,pv,d): # constructor\n self.distance = d\n self.parentVert = pv\n\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.isInTree = False\n\nclass Graph:\n def __init__(self): # constructor\n self.vertexList = [] # adjacency matrix\n self.adjMat = []\n self.nVerts = 0\n self.nTree = 0\n for j in range(20): # set adjacency\n l = []\n for k in range(20):\n l.append(1000000)\n self.adjMat.append(l)\n self.currentVert = 0\n self.sPath = [] # shortest paths\n self.startToCurrent = 0\n\n def addVertex(self,lab):\n self.vertexList.append( Vertex(lab))\n self.nVerts += 1\n\n def addEdge(self,start, end,weight):\n self.adjMat[start][end] = weight\n\n\n def displayVertex(self,v):\n print self.vertexList[v].label ,\n\n def path(self): # find all shortest paths\n startTree = 0 # start at vertex 0\n self.vertexList[startTree].isInTree = True\n self.nTree = 1 # put it in tree\n # transfer row of distances from adjMat to sPath\n for j in range(self.nVerts):\n tempDist = self.adjMat[startTree][j]\n try:\n self.sPath[j] = DistPar(startTree, tempDist)\n except:\n self.sPath.append(DistPar(startTree, tempDist))\n # until all vertices are in the tree\n while(self.nTree < self.nVerts):\n indexMin = self.getMin() # get minimum from sPath\n minDist = self.sPath[indexMin].distance\n if(minDist == 1000000): # if all infinite\n # or in tree,\n print 'There are unreachable vertices'\n break # sPath is complete\n else:\n # reset self.currentVert\n self.currentVert = indexMin # to closest vert\n self.startToCurrent = self.sPath[indexMin].distance\n # minimum distance from startTree is\n # to self.currentVert, and is self.startToCurrent\n # put current vertex in tree\n self.vertexList[self.currentVert].isInTree = True\n self.nTree += 1\n self.adjust_sPath() # update sPath[] array\n\n self.displayPaths() # display sPath[] contents\n self.nTree = 0 # clear tree\n for j in range(self.nVerts):\n self.vertexList[j].isInTree = False \n\n def getMin(self): # get entry from sPath\n minDist = 1000000 # assume minimum\n indexMin = 0\n for j in range(self.nVerts): # for each vertex,\n # if its in tree and\n if( not self.vertexList[j].isInTree and self.sPath[j].distance < minDist ):\n minDist = self.sPath[j].distance\n indexMin = j # update minimum\n return indexMin\n\n def adjust_sPath(self):\n # adjust values in shortest-path array sPath\n column = 1\n # skip starting vertex\n while(column < self.nVerts): # go across columns\n # if this columns vertex already in tree, skip it\n if( self.vertexList[column].isInTree ):\n column += 1\n continue\n # calculate distance for one sPath entry get edge from self.currentVert to column\n currentToFringe = self.adjMat[self.currentVert][column]\n # add distance from start\n startToFringe = self.startToCurrent + currentToFringe\n # get distance of current sPath entry\n sPathDist = self.sPath[column].distance\n # compare distance from start with sPath entry\n if(startToFringe < sPathDist): # if shorter,\n # update sPath\n self.sPath[column].parentVert = self.currentVert\n self.sPath[column].distance = startToFringe\n column += 1\n\n def displayPaths(self):\n for j in range(self.nVerts): # display contents of sPath[]\n print self.vertexList[j].label ,' =' \n if(self.sPath[j].distance == 1000000):\n print 'inf', # inf\n else:\n print self.sPath[j].distance , # 50\n parent = self.vertexList[ self.sPath[j].parentVert ].label\n print '(' , parent , ')' , # (A)\n print ''\n \ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start)\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1,50)\ntheGraph.addEdge(0,3,80)\ntheGraph.addEdge(1,2,60)\ntheGraph.addEdge(1,3,90)\ntheGraph.addEdge(2,4,40)\ntheGraph.addEdge(3,2,20)\ntheGraph.addEdge(3,4,70)\ntheGraph.addEdge(4,1,50)\nprint 'Shortest paths' ,\ntheGraph.path() # shortest paths", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Shortest paths A =\ninf ( A ) C =\n50 ( A ) B =\n100 ( D ) D =\n80 ( A ) E =\n140 ( B ) \n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch2.ipynb b/Data_Structures_and_Algorithms_in_Java/ch2.ipynb new file mode 100644 index 00000000..545d8433 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch2.ipynb @@ -0,0 +1,133 @@ +{ + "metadata": { + "name": "ch2" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 2 : Arrays" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 2.1 Page no :41" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 2.1\ndemonstrates arrays/lists\n'''\n\nnElems = 0\narr = [77,99,44,55,22,88,11,00,66,33]\n\nfor j in range(len(arr)):\n # display items\n print arr[j] ,\nprint ''\n\nsearchKey = 66\n# find item with key 66\nfor j in range(len(arr)):\n if(arr[j] == searchKey):\n break\nif(j == len(arr)):\n print 'Cant find ', searchKey\nelse:\n print 'Found ' ,searchKey\n\nsearchKey = 55\nfor j in arr:\n if(j == searchKey):\n arr.remove(searchKey)\n\n\nfor j in range(len(arr)):\n # display items\n print arr[j] ,\nprint ''\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "77 99 44 55 22 88 11 0 66 33 \nFound 66\n77 99 44 22 88 11 0 66 33 \n" + } + ], + "prompt_number": 1 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 2.2 Page No : 44" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 2.2\n'''\n\nclass LowArray:\n def __init__(self,size):\n self.a = []\n for i in range(size):\n self.a.append(0.0)\n \n def setElem(self,index,value):\n # set value\n self.a[index] = value\n\n def getElem(self,index):\n return self.a[index]\n\narr = LowArray(100)\narr.setElem(0,77)\narr.setElem(1,99)\narr.setElem(2,44)\narr.setElem(3,55)\narr.setElem(4,22)\narr.setElem(5,88)\narr.setElem(6,11)\narr.setElem(7,00)\narr.setElem(8,66)\narr.setElem(9,33)\nnElems = 10\n\n# now 10 items in array\nfor j in range(nElems):\n # display items\n print arr.getElem(j) ,\n\nprint ''\n\nsearchKey = 26\nfind = False\n# search for data item\nfor j in range(nElems):\n # for each element,\n if(arr.getElem(j) == searchKey): # found item?\n find = True\n break\nif(not find):\n print \"Can't find \" , searchKey\nelse:\n print \"Found \" , searchKey\n\nfor j in range(nElems):\n if(arr.getElem(j) == 55):\n arr.a.remove(55)\n nElems -= 1\n\nfor j in range(nElems):\n # display items\n print arr.getElem(j) ,\n ", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "77 99 44 55 22 88 11 0 66 33 \nCan't find 26\n77 99 44 22 88 11 0 66 33\n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 2.3 Page No : 49" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 2.3\n'''\n\nclass HighArray:\n def __init__(self,size):\n self.a = []\n self.nElems = 0\n for i in range(size):\n self.a.append(0.0)\n \n def insert(self,value):\n # set value\n self.a[self.nElems] = value\n self.nElems += 1\n\n def find(self,searchKey):\n for j in range(self.nElems):\n if(self.a[j] == searchKey):\n return True\n return False\n \n def delete(self,value):\n for j in range(self.nElems):\n # look for it\n if (value == self.a[j]):\n self.a.remove(value)\n self.nElems -= 1\n \n def display(self):\n for j in range(self.nElems+1):\n print self.a[j] , \n print ''\n\narr = HighArray(100)\narr.insert(77)\narr.insert(99)\narr.insert(44)\narr.insert(55)\narr.insert(22)\narr.insert(88)\narr.insert(11)\narr.insert(00)\narr.insert(66)\narr.insert(33)\n\narr.display()\n\nsearchKey = 35\nif( arr.find(searchKey) ):\n print \"Found \" , searchKey\nelse:\n print \"Can't find \" , searchKey\narr.delete(00)\narr.delete(55)\narr.delete(99)\narr.display()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "77 99 44 55 22 88 11 0 66 33 0.0 \nCan't find 35\n77 44 22 88 11 66 33 \n" + } + ], + "prompt_number": 3 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 2.4 Page no : 59" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 2.4\n'''\n\nclass OrdArray:\n def __init__(self,m):\n self.a = []\n self.nElems = 0\n \n def size(self):\n return self.nElems\n\n def find(self,searchKey):\n lowerBound = 0\n upperBound = self.nElems-1\n while True:\n curIn = (lowerBound + upperBound ) / 2\n if(self.a[curIn]==searchKey):\n return curIn\n elif(lowerBound > upperBound):\n return self.nElems\n else:\n if(self.a[curIn] < searchKey):\n lowerBound = curIn + 1\n else:\n upperBound = curIn - 1 \n\n def insert(self,value):\n self.a.append(value)\n self.a.sort()\n self.nElems += 1\n\n def delete(self,value):\n j = self.find(value)\n if(j==self.nElems):\n return False\n else:\n self.a.remove(value)\n self.nElems -=1\n \n def display(self):\n for i in self.a:\n print i ,\n print ''\n\nmaxSize = 100\narr = OrdArray(maxSize)\narr.insert(77)\narr.insert(99) \narr.insert(44) \narr.insert(55) \narr.insert(22) \narr.insert(88) \narr.insert(11) \narr.insert(00) \narr.insert(66) \narr.insert(33) \nsearchKey = 55\nif( arr.find(searchKey) != arr.size() ):\n print 'Found ' , searchKey\nelse:\n print \"Can't find \" , searchKey\n \narr.display()\narr.delete(00)\narr.delete(55) \narr.delete(99) \narr.display()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Found 55\n0 11 22 33 44 55 66 77 88 99 \n11 22 33 44 66 77 88 \n" + } + ], + "prompt_number": 4 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 2.5 Page no : 66" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 2.5\n'''\n\nclass Person:\n def __init__(self,last,first,a):\n self.lastName = last\n self.firstName = first\n self.age = a\n\n def displayPerson(self):\n print \"Last name: \" , self.lastName ,\", First name: \" , self.firstName ,\n print \", Age: \" , self.age\n\n def getLast(self):\n return self.lastName\n\nclass ClassDataArray:\n def __init__(self,m):\n self.a = []\n self.nElems = 0\n\n def find(self,searchName):\n f = False\n for j in range(self.nElems):\n if( self.a[j].getLast() ==searchName ) :\n f = True\n break \n if(not f):\n return None\n else:\n return self.a[j]\n\n def insert(self,last,first,age):\n self.a.append(Person(last, first, age))\n self.nElems += 1\n\n def delete(self,searchName):\n f = False\n for j in range(self.nElems):\n if( self.a[j].getLast() == searchName) :\n self.a.remove(self.a[j])\n f = True\n self.nElems -= 1\n break\n if(not f):\n return False\n else:\n return True\n \n def displayA(self):\n for j in range(self.nElems):\n self.a[j].displayPerson()\n\nmaxSize = 100\narr = ClassDataArray(maxSize)\narr.insert(\"Evans\", \"Patty\", 24)\narr.insert(\"Smith\", \"Lorraine\", 37)\narr.insert(\"Yee\", \"Tom\", 43)\narr.insert(\"Adams\", \"Henry\", 63)\narr.insert(\"Hashimoto\", \"Sato\", 21)\narr.insert(\"Stimson\", \"Henry\", 29)\narr.insert(\"Velasquez\", \"Jose\", 72)\narr.insert(\"Lamarque\", \"Henry\", 54)\narr.insert(\"Vang\", \"Minh\", 22)\narr.insert(\"Creswell\", \"Lucinda\", 18)\narr.displayA()\nsearchKey = \"Stimson\"\nfound=arr.find(searchKey)\nif(found != None ):\n print \"Found \" ,\n found.displayPerson()\nelse:\n print \"Can't find \" , searchKey\nprint \"Deleting Smith, Yee, and Creswell\"\narr.delete(\"Smith\")\narr.delete(\"Yee\")\narr.delete(\"Creswell\")\narr.displayA()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Last name: Evans , First name: Patty , Age: 24\nLast name: Smith , First name: Lorraine , Age: 37\nLast name: Yee , First name: Tom , Age: 43\nLast name: Adams , First name: Henry , Age: 63\nLast name: Hashimoto , First name: Sato , Age: 21\nLast name: Stimson , First name: Henry , Age: 29\nLast name: Velasquez , First name: Jose , Age: 72\nLast name: Lamarque , First name: Henry , Age: 54\nLast name: Vang , First name: Minh , Age: 22\nLast name: Creswell , First name: Lucinda , Age: 18\nFound Last name: Stimson , First name: Henry , Age: 29\nDeleting Smith, Yee, and Creswell\nLast name: Evans , First name: Patty , Age: 24\nLast name: Adams , First name: Henry , Age: 63\nLast name: Hashimoto , First name: Sato , Age: 21\nLast name: Stimson , First name: Henry , Age: 29\nLast name: Velasquez , First name: Jose , Age: 72\nLast name: Lamarque , First name: Henry , Age: 54\nLast name: Vang , First name: Minh , Age: 22\n" + } + ], + "prompt_number": 5 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch3.ipynb b/Data_Structures_and_Algorithms_in_Java/ch3.ipynb new file mode 100644 index 00000000..1cce57db --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch3.ipynb @@ -0,0 +1,336 @@ +{ + "metadata": { + "name": "ch3" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": [ + "Chapter 3 : Simple Sorting" + ] + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": [ + "Example 3.1 Page No : 85" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "'''\n", + "Example 3.1\n", + "Bubble Sort\n", + "'''\n", + "\n", + "class ArrayBub:\n", + " def __init__(self,m):\n", + " self.a = []\n", + " self.nElems = 0\n", + " \n", + " def insert(self,value):\n", + " # put element into array\n", + " self.a.append(value)\n", + " self.nElems += 1\n", + "\n", + " def display(self):\n", + " # displays array contents\n", + " for j in range(self.nElems):\n", + " print self.a[j] ,\n", + " print ''\n", + "\n", + " def bubbleSort(self):\n", + " out = self.nElems - 1\n", + " while out > 1 :\n", + " for i in range(out): \n", + " if( self.a[i] > self.a[i+1] ):\n", + " self.a[i],self.a[i+1] = self.a[i+1],self.a[i] \n", + " out -= 1\n", + "\n", + "maxSize = 100 # array size\n", + "arr = ArrayBub(maxSize) # create the array\n", + "arr.insert(77) # insert 10 items\n", + "arr.insert(99) \n", + "arr.insert(44) \n", + "arr.insert(55) \n", + "arr.insert(22) \n", + "arr.insert(88) \n", + "arr.insert(11) \n", + "arr.insert(00) \n", + "arr.insert(66) \n", + "arr.insert(33) \n", + "arr.display() # display items\n", + "arr.bubbleSort() # bubble sort them\n", + "arr.display()" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "77 99 44 55 22 88 11 0 66 33 \n", + "0 11 22 33 44 55 66 77 88 99 \n" + ] + } + ], + "prompt_number": 5 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": [ + "Example 3.2 Page No : 93" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "'''\n", + "Example 3.2\n", + "Selection Sort\n", + "'''\n", + "\n", + "class ArraySel:\n", + " def __init__(self,m):\n", + " self.a = []\n", + " self.nElems = 0\n", + " \n", + " def insert(self,value):\n", + " # put element into array\n", + " self.a.append(value)\n", + " self.nElems += 1\n", + "\n", + " def display(self):\n", + " # displays array contents\n", + " for j in range(self.nElems):\n", + " print self.a[j] ,\n", + " print ''\n", + "\n", + " def selectionSort(self):\n", + " for out in range(self.nElems-1):\n", + " for i in range(out,self.nElems): \n", + " if( self.a[i] < self.a[out] ):\n", + " self.a[i],self.a[out] = self.a[out],self.a[i] \n", + "\n", + "maxSize = 100 # array size\n", + "arr = ArraySel(maxSize) # create the array\n", + "arr.insert(77) # insert 10 items\n", + "arr.insert(99) \n", + "arr.insert(44) \n", + "arr.insert(55) \n", + "arr.insert(22) \n", + "arr.insert(88) \n", + "arr.insert(11) \n", + "arr.insert(00) \n", + "arr.insert(66) \n", + "arr.insert(33) \n", + "arr.display() # display items\n", + "arr.selectionSort() # bubble sort them\n", + "arr.display()" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "77 99 44 55 22 88 11 0 66 33 \n", + "0 11 22 33 44 55 66 77 88 99 \n" + ] + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": [ + "Example 3.3 Page No : 101" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "'''\n", + "Example 3.3\n", + "demonstrates insertion sort\n", + "'''\n", + "class ArrayIns:\n", + " def __init__(self,m):\n", + " self.a = [] # create the array\n", + " self.nElems = 0 # no items yet\n", + "\n", + " def insert(self,value): # put element into array\n", + " self.a.append(value) # insert it\n", + " self.nElems += 1 # increment size\n", + "\n", + " def display(self): # displays array contents\n", + " for j in range(self.nElems): # for each element,\n", + " print self.a[j] , # display it\n", + " print ''\n", + "\n", + " def insertionSort(self):\n", + " for out in range(self.nElems):\n", + " temp = self.a[out]\n", + " i = out\n", + " while (i>0 and self.a[i-1] >= temp):\n", + " self.a[i] = self.a[i-1]\n", + " i -= 1\n", + " self.a[i] = temp\n", + "\n", + "maxSize = 100 # array size\n", + "arr = ArrayIns(maxSize) # create the array\n", + "arr.insert(77) # insert 10 items\n", + "arr.insert(99) \n", + "arr.insert(44) \n", + "arr.insert(55) \n", + "arr.insert(22) \n", + "arr.insert(88) \n", + "arr.insert(11) \n", + "arr.insert(00) \n", + "arr.insert(66) \n", + "arr.insert(33) \n", + "arr.display() # display items\n", + "arr.insertionSort() # insertion-sort them\n", + "arr.display()" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "77 99 44 55 22 88 11 0 66 33 \n", + "0 11 22 33 44 55 66 77 88 99 \n" + ] + } + ], + "prompt_number": 3 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": [ + "Example 3.4 Page No : 104" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "'''\n", + "Example 3.4\n", + "demonstrates sorting objects (uses insertion sort)\n", + "'''\n", + "class Person:\n", + " def __init__(self,last,first,a):\n", + " # constructor\n", + " self.lastName = last\n", + " self.firstName = first\n", + " self.age = a\n", + "\n", + " def displayPerson(self):\n", + " print 'Last name: ', self.lastName , ', First name: ',self.firstName , ', Age: ' , self.age\n", + "\n", + " def getLast(self): # get last name\n", + " return self.lastName \n", + "\n", + "class ArrayInOb:\n", + " def __init__(self,m):\n", + " self.a = [] # create the array\n", + " self.nElems = 0 # no items yet\n", + " \n", + " def insert(self,last,first,age):\n", + " self.a.append(Person(last, first, age))\n", + " self.nElems += 1 # increment size\n", + "\n", + " def display(self): # displays array contents\n", + " for j in range(self.nElems): # for each element,\n", + " self.a[j].displayPerson() # display it\n", + " print ''\n", + "\n", + " def insertionSort(self):\n", + " for out in range(1,self.nElems):\n", + " temp = self.a[out]\n", + " i = out\n", + " while(i>0 and self.a[i-1].getLast() > temp.getLast()):\n", + " self.a[i] = self.a[i-1] # shift item to the right\n", + " i -= 1 # go left one position\n", + " self.a[i] = temp\n", + "maxSize = 100 # array size\n", + "arr = ArrayInOb(maxSize) # create the array\n", + "arr.insert('Evans', 'Patty', 24)\n", + "arr.insert('Smith', 'Doc', 59)\n", + "arr.insert('Smith', 'Lorraine', 37)\n", + "arr.insert('Smith', 'Paul', 37)\n", + "arr.insert('Yee', 'Tom', 43)\n", + "arr.insert('Hashimoto', 'Sato', 21)\n", + "arr.insert('Stimson', 'Henry', 29)\n", + "arr.insert('Velasquez', 'Jose', 72)\n", + "arr.insert('Vang', 'Minh', 22)\n", + "arr.insert('Creswell', 'Lucinda', 18)\n", + "print 'Before sorting:'\n", + "arr.display() # display items\n", + "arr.insertionSort() # insertion-sort them\n", + "print 'After sorting:'\n", + "arr.display() # display them again" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "Before sorting:\n", + "Last name: Evans , First name: Patty , Age: 24\n", + "Last name: Smith , First name: Doc , Age: 59\n", + "Last name: Smith , First name: Lorraine , Age: 37\n", + "Last name: Smith , First name: Paul , Age: 37\n", + "Last name: Yee , First name: Tom , Age: 43\n", + "Last name: Hashimoto , First name: Sato , Age: 21\n", + "Last name: Stimson , First name: Henry , Age: 29\n", + "Last name: Velasquez , First name: Jose , Age: 72\n", + "Last name: Vang , First name: Minh , Age: 22\n", + "Last name: Creswell , First name: Lucinda , Age: 18\n", + "\n", + "After sorting:\n", + "Last name: Creswell , First name: Lucinda , Age: 18\n", + "Last name: Evans , First name: Patty , Age: 24\n", + "Last name: Hashimoto , First name: Sato , Age: 21\n", + "Last name: Smith , First name: Doc , Age: 59\n", + "Last name: Smith , First name: Lorraine , Age: 37\n", + "Last name: Smith , First name: Paul , Age: 37\n", + "Last name: Stimson , First name: Henry , Age: 29\n", + "Last name: Vang , First name: Minh , Age: 22\n", + "Last name: Velasquez , First name: Jose , Age: 72\n", + "Last name: Yee , First name: Tom , Age: 43\n", + "\n" + ] + } + ], + "prompt_number": 4 + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch4.ipynb b/Data_Structures_and_Algorithms_in_Java/ch4.ipynb new file mode 100644 index 00000000..bfba5c3b --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch4.ipynb @@ -0,0 +1,284 @@ +{ + "metadata": { + "name": "ch4" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 4 : Stacks and Queues" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Exmaple 4.1 Page no : 120" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 4.1\nStack implemantation\n'''\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\ntheStack = StackX(10) # make new stack\ntheStack.push(20)\ntheStack.push(40)\ntheStack.push(60)\ntheStack.push(80)\nwhile( not theStack.isEmpty() ):\n value = theStack.pop()\n print value,", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "80 60 40 20\n" + } + ], + "prompt_number": 1 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.2 Page No : 124" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 4.2\nStack implemantation\n'''\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\n\nclass Reverser:\n def __init__(self,i):\n self.input = i\n self.output = ''\n self.theStack = None\n\n def doRev(self):\n stackSize = len(self.input)\n self.theStack = StackX(stackSize)\n for j in range(stackSize):\n ch = self.input[j]\n self.theStack.push(ch)\n while( not self.theStack.isEmpty() ):\n ch = self.theStack.pop()\n self.output = self.output + ch\n return self.output\n\n\nwhile(True):\n print \"Enter a string: \" ,\n i = raw_input() \n if( i == \"\"):\n break\n theReverser = Reverser(i)\n output = theReverser.doRev()\n print \"Reversed: \" , output", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter a string: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "part\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Reversed: trap\nEnter a string: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": "\n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.3 Page No : 128" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 4.3\n'''\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\nclass BracketChecker:\n def __init__(self,i):\n self.input = i \n self.theStack = None\n\n def check(self):\n stackSize = len(self.input)\n self.theStack = StackX(stackSize)\n for j in range(stackSize):\n ch = self.input[j]\n if (ch == '{' or ch == '[' or ch=='('):\n self.theStack.push(ch)\n elif (ch=='}' or ch==']' or ch==')'):\n if( not self.theStack.isEmpty() ):\n chx = self.theStack.pop()\n if( (ch=='}' and chx!='{') or (ch==']' and chx!='[') or (ch==')' and chx!='(') ):\n print \"Error: \" , ch , \" at \" , j \n else:\n print 'Error: ', ch , ' at ' ,j\n else:\n pass\n if( not self.theStack.isEmpty() ):\n print 'Error: missing right delimiter'\n\nwhile(True):\n print 'Enter string containing delimiters: '\n i = raw_input()\n if( i == ''):\n break\n theChecker = BracketChecker(i)\n theChecker.check()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter string containing delimiters: \n" + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "a{b(c]d}e\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": "Error: ] at 5\nEnter string containing delimiters: \n" + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter string containing delimiters: \n" + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + } + ], + "prompt_number": 4 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.4 Page No : 138" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 4.4\n'''\nclass Queue:\n def __init__(self,s):\n self.maxSize = s\n self.queArray = []\n for i in range(s):\n self.queArray.append(0)\n self.front = 0\n self.rear = -1\n self.nItems = 0\n\n def insert(self,j):\n if(self.rear == self.maxSize-1):\n self.rear = -1\n self.rear += 1\n self.queArray[self.rear] = j\n self.nItems += 1\n\n def remove(self):\n temp = self.queArray[self.front]\n #self.queArray.remove(temp)\n self.front += 1\n if(self.front == self.maxSize):\n # deal with wraparound\n self.front = 0\n self.nItems-=1\n return temp\n\n def peekFront(self):\n return self.queArray[self.front]\n\n def isEmpty(self):\n # true if queue is empty\n return (self.nItems==0)\n\n def isFull(self):\n # true if queue is full\n return (self.nItems==self.maxSize)\n\n def size(self):\n # number of items in queue\n return self.nItems\n\ntheQueue = Queue(5) # queue holds 5 items\ntheQueue.insert(10) # insert 4 items\ntheQueue.insert(20) \ntheQueue.insert(30) \ntheQueue.insert(40) \ntheQueue.remove() # remove 3 items\ntheQueue.remove() \ntheQueue.remove()\ntheQueue.insert(50) # insert 4 more items\ntheQueue.insert(60)\ntheQueue.insert(70)\ntheQueue.insert(80)\nwhile( not theQueue.isEmpty() ): # // remove and display\n n = theQueue.remove()\n print n ,", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "40 50 60 70 80\n" + } + ], + "prompt_number": 5 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.5 Page No : 141" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 4.5\n'''\nclass Queue:\n def __init__(self,s):\n self.maxSize = s\n self.queArray = []\n for i in range(s):\n self.queArray.append(0)\n self.front = 0\n self.rear = -1\n\n def insert(self,j):\n if(self.rear == self.maxSize-1):\n self.rear = -1\n self.rear += 1\n self.queArray[self.rear] = j\n\n def remove(self):\n temp = self.queArray[self.front]\n #self.queArray.remove(temp)\n self.front += 1\n if(self.front == self.maxSize):\n # deal with wraparound\n self.front = 0\n return temp\n\n def peek(self):\n return self.queArray[self.front]\n\n def isEmpty(self):\n # true if queue is empty\n return ( self.rear+1==self.front or (self.front+self.maxSize-1==self.rear) )\n\n def isFull(self):\n # true if queue is full\n return ( self.rear+2==self.front or (self.front+self.maxSize-2==self.rear) )\n\n def size(self):\n # number of items in queue\n if(self.rear >= self.front):\n # contiguous sequence\n return self.rear-self.front+1\n else:\n # broken sequence\n return (self.maxSize-self.front) + (self.rear+1)", + "language": "python", + "metadata": {}, + "outputs": [], + "prompt_number": 6 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.6 Page No : 147" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 4.6\n'''\n\nclass PriorityQ:\n # array in sorted order, from max at 0 to min at size-1\n def __init__(self,s):\n self.maxSize = s\n self.queArray = []\n for i in range(s):\n self.queArray.append(0)\n self.nItems = 0\n\n def insert(self,item):\n # insert item\n if(self.nItems==0):\n self.queArray[self.nItems] = item\n self.nItems += 1\n else:\n # if items,\n j = self.nItems\n while j >= 0:\n if( item > self.queArray[j] ):\n self.queArray[j+1] = self.queArray[j] # shift upward\n else:\n break\n j -= 1\n self.queArray[j+1] = item\n self.nItems += 1\n\n def remove(self):\n # remove minimum item\n self.nItems -= 1\n return self.queArray[self.nItems]\n\n def peekMin(self):\n # peek at minimum item\n return self.queArray[self.nItems-1]\n\n def isEmpty(self):\n # true if queue is empty\n return (self.nItems==0)\n\n def isFull(self):\n # true if queue is full\n return (self.nItems == self.maxSize)\n\nthePQ = PriorityQ(6)\nthePQ.insert(30)\nthePQ.insert(50)\nthePQ.insert(10)\nthePQ.insert(40)\nthePQ.insert(20)\nwhile(not thePQ.isEmpty() ):\n item = thePQ.remove()\n print item ,", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "10 20 30 40 50\n" + } + ], + "prompt_number": 7 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.7 Page No : 161" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 4.7\ninfix : converts infix arithmetic expressions to postfix\n'''\n\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\n def peekN(self,n): # return item at index n\n return self.stackArray[n]\n \n def size(self): # return size\n return self.top+1\n \n def displayStack(self,s):\n print s\n print 'Stack (bottom-->top): ',\n for j in range(self.size()):\n print self.peekN(j) ,\n print ''\n\nclass InToPost:\n # infix to postfix conversion\n def __init__(self,i):\n self.input = i\n self.stackSize = len(self.input)\n self.theStack = StackX(self.stackSize)\n self.output = ''\n\n def doTrans(self):\n # do translation to postfix\n for j in range(self.stackSize):\n ch = self.input[j]\n self.theStack.displayStack(\"For \"+ ch +\" \") # *diagnostic*\n if ch=='+' or ch=='-':\n self.gotOper(ch, 1)\n elif ch=='*' or ch=='/':\n self.gotOper(ch, 2)\n elif ch=='(':\n self.theStack.push(ch)\n elif ch==')':\n self.gotParen(ch)\n else:\n self.output = self.output + ch # write it to output\n while( not self.theStack.isEmpty() ): # pop remaining opers\n self.theStack.displayStack('While ') # *diagnostic*\n self.output = self.output + self.theStack.pop() # write to output\n self.theStack.displayStack(\"End\")\n return self.output\n\n def gotOper(self,opThis, prec1):\n # got operator from input\n while( not self.theStack.isEmpty() ):\n opTop = self.theStack.pop()\n if( opTop == '(' ):\n self.theStack.push(opTop)\n break\n else:\n prec2 = 0\n if(opTop=='+' or opTop=='-'): # find new op prec\n prec2 = 1\n else:\n prec2 = 2\n if(prec2 < prec1): # if prec of new op less\n self.theStack.push(opTop)\n break;\n else:\n self.output = self.output + opTop # than prec of old\n self.theStack.push(opThis)\n\n def gotParen(self,ch):\n # got right paren from input\n while( not self.theStack.isEmpty() ):\n chx = self.theStack.pop()\n if( chx == '(' ):\n # if popped '('\n break\n # we're done\n else:\n # if popped operator\n self.output = self.output + chx # output it\n\nwhile(True):\n print 'Enter infix: ',\n i = raw_input()\n # read a string from kbd\n if( i == ''):\n # quit if [Enter]\n break\n theTrans = InToPost(i)\n output = theTrans.doTrans() # do the translation\n print \"Postfix is \" , output", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter infix: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "A*(B+C)-D/(E+F)\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " For A \nStack (bottom-->top): \nFor * \nStack (bottom-->top): \nFor ( \nStack (bottom-->top): * \nFor B \nStack (bottom-->top): * ( \nFor + \nStack (bottom-->top): * ( \nFor C \nStack (bottom-->top): * ( + \nFor ) \nStack (bottom-->top): * ( + \nFor - \nStack (bottom-->top): * \nFor D \nStack (bottom-->top): - \nFor / \nStack (bottom-->top): - \nFor ( \nStack (bottom-->top): - / \nFor E \nStack (bottom-->top): - / ( \nFor + \nStack (bottom-->top): - / ( \nFor F \nStack (bottom-->top): - / ( + \nFor ) \nStack (bottom-->top): - / ( + \nWhile \nStack (bottom-->top): - / \nWhile \nStack (bottom-->top): - \nEnd\nStack (bottom-->top): \nPostfix is ABC+*DEF+/-\nEnter infix: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": "\n" + } + ], + "prompt_number": 8 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 4.8 Page No : 168" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 4.8\n'''\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n for i in range(s):\n self.stackArray.append(0.0)\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray[self.top] = j #.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\n def peekN(self,n): # return item at index n\n return self.stackArray[n]\n \n def size(self): # return size\n return self.top+1\n \n def displayStack(self,s):\n print s ,\n print 'Stack (bottom-->top): ',\n for j in range(self.top+1):\n print self.peekN(j) ,\n print ''\n\nclass ParsePost:\n # infix to postfix conversion\n def __init__(self,i):\n self.input = i\n self.theStack = None\n\n def doParse(self):\n self.theStack = StackX(20)\n interAns = 0\n for j in range(len(self.input)):\n ch = self.input[j]\n self.theStack.displayStack(ch + ' ')\n if(ch >= '0' and ch <= '9'):\n self.theStack.push( ord(ch)-ord('0') )\n else:\n num2 = self.theStack.pop()\n num1 = self.theStack.pop()\n if ch=='+':\n interAns = num1 + num2\n elif ch=='-':\n interAns = num1 - num2\n elif ch=='*':\n interAns = num1 * num2\n elif ch=='/':\n interAns = num1 / num2\n else:\n interAns = 0\n self.theStack.push(interAns)\n interAns = self.theStack.pop()\n return interAns\n\nwhile(True):\n print 'Enter postfix: ',\n i = raw_input()\n # read a string from kbd\n if( i == ''):\n # quit if [Enter]\n break\n aParser = ParsePost(i)\n output = aParser.doParse() # do the evaluation\n print \"Evaluates to \" , output", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter postfix: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "345+*612+/-\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " 3 Stack (bottom-->top): \n4 Stack (bottom-->top): 3 \n5 Stack (bottom-->top): 3 4 \n+ Stack (bottom-->top): 3 4 5 \n* Stack (bottom-->top): 3 9 \n6 Stack (bottom-->top): 27 \n1 Stack (bottom-->top): 27 6 \n2 Stack (bottom-->top): 27 6 1 \n+ Stack (bottom-->top): 27 6 1 2 \n/ Stack (bottom-->top): 27 6 3 \n- Stack (bottom-->top): 27 2 \nEvaluates to 25\nEnter postfix: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": "\n" + } + ], + "prompt_number": 9 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch5.ipynb b/Data_Structures_and_Algorithms_in_Java/ch5.ipynb new file mode 100644 index 00000000..6ac7b766 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch5.ipynb @@ -0,0 +1,338 @@ +{ + "metadata": { + "name": "ch5" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 5 : Linked Lists" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.1 Page No : 190" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 5.1\nLink List\n'''\n\nclass Link:\n def __init__(self,i,dd):\n self.iData = i\n self.dData = dd\n self.next = None\n\n def displayLink(self): # display ourself\n print '{' , self.iData , ', ' , self.dData , '} ' ,\n\nclass LinkList:\n def __init__(self):\n self.first = None\n\n def isEmpty(self): # true if list is empty\n return (self.first==None)\n\n # insert at start of list\n def insertFirst(self,i, dd):\n # make new link\n newLink = Link(i, dd)\n newLink.next = self.first\n # newLink --> old first\n self.first = newLink\n\n def deleteFirst(self):\n temp = self.first\n self.first = self.first.next\n return temp\n \n def displayList(self):\n print 'List (first-->last): ' ,\n current = self.first\n while(current != None):\n current.displayLink()\n current = current.next\n print ''\n\ntheList = LinkList() # make new list\ntheList.insertFirst(22,2.99)\ntheList.insertFirst(44,4.99)\ntheList.insertFirst(66,6.99)\ntheList.insertFirst(88,8.99)\ntheList.displayList()\n\nwhile( not theList.isEmpty() ): # until it's empty,\n aLink = theList.deleteFirst() # delete link\n print 'Deleted ' , # display it\n aLink.displayLink()\n print ''\n \ntheList.displayList()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "List (first-->last): { 88 , 8.99 } { 66 , 6.99 } { 44 , 4.99 } { 22 , 2.99 } \nDeleted { 88 , 8.99 } \nDeleted { 66 , 6.99 } \nDeleted { 44 , 4.99 } \nDeleted { 22 , 2.99 } \nList (first-->last): \n" + } + ], + "prompt_number": 1 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.2 Page No : 193" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 5.2\ndemonstrates linked list\n'''\nclass Link:\n def __init__(self,i,dd):\n self.iData = i\n self.dData = dd\n self.next = None\n\n def displayLink(self): # display ourself\n print '{' , self.iData , ', ' , self.dData , '} ' ,\n\nclass LinkList:\n def __init__(self):\n self.first = None\n\n def isEmpty(self): # true if list is empty\n return (self.first==None)\n\n # insert at start of list\n def insertFirst(self,i, dd):\n # make new link\n newLink = Link(i, dd)\n newLink.next = self.first\n # newLink --> old first\n self.first = newLink\n\n def deleteFirst(self):\n temp = self.first\n self.first = self.first.next\n return temp\n \n def displayList(self):\n print 'List (first-->last): ' ,\n current = self.first\n while(current != None):\n current.displayLink()\n current = current.next\n print ''\n\n def find(self,key): # find link with given key\n current = self.first #start at first\n while(current.iData != key): # while no match,\n if(current.next == None): # if end of list,\n return None # didnt find it\n else:\n current = current.next # go to next link\n return current\n \n def delete(self,key): # delete link with given key\n current = self.first \n previous = self.first\n while(current.iData != key):\n if(current.next == None):\n return None # didnt find it\n else:\n previous = current\n current = current.next\n if(current == self.first): # if first link,\n self.first = self.first.next\n else:\n previous.next = current.next\n return current\n\n\ntheList = LinkList() # make list\ntheList.insertFirst(22,2.99)\ntheList.insertFirst(44,4.99)\ntheList.insertFirst(66,6.99)\ntheList.insertFirst(88,8.99)\ntheList.displayList() # display list\nf = theList.find(44) # find item\nif( f != None):\n print 'Found link with key ' , f.iData\nelse:\n print \"Can't find link\"\nd = theList.delete(66) # delete item\nif( d != None ):\n print \"Deleted link with key \" , d.iData\nelse:\n print \"Can't delete link\"\n\ntheList.displayList()", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "List (first-->last): { 88 , 8.99 } { 66 , 6.99 } { 44 , 4.99 } { 22 , 2.99 } \nFound link with key 44\nDeleted link with key 66\nList (first-->last): { 88 , 8.99 } { 44 , 4.99 } { 22 , 2.99 } \n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.3 Page NO :198" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 5.3\ndemonstrates list with first and last references\n'''\nclass Link:\n def __init__(self,d):\n self.dData = d\n self.next = None\n\n def displayLink(self): # display ourself\n print self.dData , \n\nclass FirstLastList:\n def __init__(self):\n self.first = None\n self.last = None\n\n def isEmpty(self): # true if list is empty\n return (self.first==None)\n\n # insert at start of list\n def insertFirst(self, dd):\n # make new link\n newLink = Link(dd)\n if (self.isEmpty()):\n self.last = newLink\n newLink.next = self.first\n # newLink --> old first\n self.first = newLink\n\n def deleteFirst(self):\n temp = self.first\n if self.first.next ==None:\n self.last = None\n self.first = self.first.next\n return temp\n\n def insertLast(self,dd): # insert at end of list\n newLink = Link(dd) # make new link\n if( self.isEmpty() ): # if empty list,\n self.first = newLink # first --> newLink\n else:\n self.last.next = newLink # old last --> newLink\n self.last = newLink # newLink <-- last\n\n def displayList(self):\n print 'List (first-->last): ' ,\n current = self.first\n while(current != None):\n current.displayLink()\n current = current.next\n print ''\n\n\ntheList = FirstLastList()\ntheList.insertFirst(22) \ntheList.insertLast(11)\ntheList.insertFirst(44) \ntheList.insertLast(33) \ntheList.insertFirst(66) \ntheList.insertLast(55) \ntheList.displayList() # display the list\ntheList.deleteFirst() \ntheList.deleteFirst() \ntheList.displayList() # display again", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "List (first-->last): 66 44 22 11 33 55 \nList (first-->last): 22 11 33 55 \n" + } + ], + "prompt_number": 3 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.4 Page No : 204" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 5.4\ndemonstrates a stack implemented as a list\n'''\nclass Link:\n def __init__(self,dd):\n self.dData = dd\n self.next = None\n\n def displayLink(self): # display ourself\n print self.dData , \n\nclass LinkList:\n def __init__(self):\n self.first = None\n\n def isEmpty(self): # true if list is empty\n return (self.first==None)\n\n # insert at start of list\n def insertFirst(self, dd):\n # make new link\n newLink = Link( dd)\n newLink.next = self.first\n # newLink --> old first\n self.first = newLink\n\n def deleteFirst(self):\n temp = self.first\n self.first = self.first.next\n return temp\n \n def displayList(self):\n current = self.first\n while(current != None):\n current.displayLink()\n current = current.next\n print ''\n\nclass LinkStack:\n def __init__(self):\n self.theList = LinkList()\n\n def push(self,j): # put item on top of stack\n self.theList.insertFirst(j)\n\n def pop(self): # take item from top of stack\n return self.theList.deleteFirst()\n\n def isEmpty(self):\n return ( self.theList.isEmpty() )\n\n def displayStack(self):\n print 'Stack (top-->bottom): ' ,\n self.theList.displayList()\n\ntheStack = LinkStack() # make stack\ntheStack.push(20)\ntheStack.push(40) \ntheStack.displayStack() # display stack\n\ntheStack.push(60) # push items\ntheStack.push(80) \ntheStack.displayStack() # display stack\ntheStack.pop() \ntheStack.pop() \ntheStack.displayStack() # display stack", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Stack (top-->bottom): 40 20 \nStack (top-->bottom): 80 60 40 20 \nStack (top-->bottom): 40 20 \n" + } + ], + "prompt_number": 4 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.5 Page No : 207" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 5.5\ndemonstrates queue implemented as double-ended list\n'''\n\nclass Link:\n def __init__(self,d): # constructor\n self.dData = d\n self.next = None\n\n def displayLink(self): # display this link\n print self.dData ,\n\nclass FirstLastList:\n def __init__(self):\n self.first = None\n self.last = None\n\n def isEmpty(self): # true if list is empty\n return (self.first==None)\n\n # insert at start of list\n def insertFirst(self, dd):\n # make new link\n newLink = Link(dd)\n if (self.isEmpty()):\n self.last = newLink\n newLink.next = self.first\n # newLink --> old first\n self.first = newLink\n\n def deleteFirst(self):\n temp = self.first\n if self.first.next ==None:\n self.last = None\n self.first = self.first.next\n return temp\n\n def insertLast(self,dd): # insert at end of list\n newLink = Link(dd) # make new link\n if( self.isEmpty() ): # if empty list,\n self.first = newLink # first --> newLink\n else:\n self.last.next = newLink # old last --> newLink\n self.last = newLink # newLink <-- last\n \n def displayList(self):\n print 'List (first-->last): ' ,\n current = self.first\n while(current != None):\n current.displayLink()\n current = current.next\n print ''\n\n\nclass LinkQueue:\n def __init__(self):\n self.theList = FirstLastList() # make a 2-ended list\n\n def isEmpty(self): # true if queue is empty\n return self.theList.isEmpty()\n \n def insert(self,j): # insert, rear of queue\n self.theList.insertLast(j)\n \n def remove(self): # remove, front of queue\n return self.theList.deleteFirst()\n \n def displayQueue(self):\n print 'Queue (front-->rear): ' , \n self.theList.displayList()\n\ntheQueue = LinkQueue()\ntheQueue.insert(20) # insert items\ntheQueue.insert(40) \ntheQueue.displayQueue() # display queue\ntheQueue.insert(60) # insert items\ntheQueue.insert(80) \ntheQueue.displayQueue() # display queue\ntheQueue.remove() # remove items\ntheQueue.remove() \ntheQueue.displayQueue() # display queue", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Queue (front-->rear): List (first-->last): 20 40 \nQueue (front-->rear): List (first-->last): 20 40 60 80 \nQueue (front-->rear): List (first-->last): 60 80 \n" + } + ], + "prompt_number": 5 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.6 Page No : 215" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 5.6\ndemonstrates sorted list\n'''\n\nclass Link:\n def __init__(self,d): # constructor\n self.dData = d\n self.next = None\n\n def displayLink(self): # display this link\n print self.dData ,\n\nclass SortedList:\n def __init__(self):\n self.first = None\n\n def isEmpty(self): # true if no links\n return (self.first==None)\n\n def insert(self,key): # insert, in order\n newLink = Link(key) # make new link\n previous = None\n current = self.first # until end of list,\n while(current != None and key > current.dData):\n previous = current\n current = current.next\n if(previous==None): # at beginning of list\n self.first = newLink\n else: # not at beginning\n previous.next = newLink\n newLink.next = current\n\n def remove(self): # return & delete first link\n temp = self.first # save first\n self.first = self.first.next # delete first\n return temp\n\n def displayList(self):\n print \"List (first-->last): \" ,\n current = self.first # start at beginning of listSorted Lists\n while(current != None): # until end of list,\n current.displayLink()\n current = current.next # move to next link\n print ''\n\n# create new list\ntheSortedList = SortedList()\ntheSortedList.insert(20) # insert 2 items\ntheSortedList.insert(40)\ntheSortedList.displayList() # display list\ntheSortedList.insert(10)\ntheSortedList.insert(30)\ntheSortedList.insert(50) # insert 3 more items\ntheSortedList.displayList() # display list\ntheSortedList.remove() # remove an item\ntheSortedList.displayList() # display list", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "List (first-->last): 20 40 \nList (first-->last): 10 20 30 40 50 \nList (first-->last): 20 30 40 50 \n" + } + ], + "prompt_number": 6 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.7 Page No : 218" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 5.7\ndemonstrates sorted list used for sorting\n'''\nclass Link:\n def __init__(self,d): # constructor\n self.dData = d\n self.next = None\n\n def displayLink(self): # display this link\n print self.dData ,\n\nclass SortedList:\n def __init__(self,linkArr = None):\n if linkArr == None:\n self.first = None\n else:\n self.first = None # initialize list\n for j in range(len(linkArr)):\n self.insert( linkArr[j] )\n\n def isEmpty(self): # true if no links\n return (self.first==None)\n\n def insert(self,k): # insert, in order\n previous = None\n current = self.first # until end of list,\n while(current != None and k.dData > current.dData):\n previous = current\n current = current.next\n if(previous==None): # at beginning of list\n self.first = k\n else: # not at beginning\n previous.next = k\n k.next = current\n\n def remove(self): # return & delete first link\n temp = self.first # save first\n self.first = self.first.next # delete first\n return temp\n\n def displayList(self):\n print \"List (first-->last): \" ,\n current = self.first # start at beginning of listSorted Lists\n while(current != None): # until end of list,\n current.displayLink()\n current = current.next # move to next link\n print ''\n\n\nsize = 10 # create array of links\nlinkArray = []\nimport random\nfor j in range(size): # fill array with links\n # random number\n n = int(random.random()*99)\n newLink = Link(n) # make link\n linkArray.append(newLink) # put in array\n\n# display array contents\nprint 'Unsorted array: ',\nfor j in range(size):\n print linkArray[j].dData , \nprint ''\n\n# create new list\n# initialized with array\ntheSortedList = SortedList(linkArray)\nlinkArray = []\nfor j in range(size): # links from list to array\n linkArray.append( theSortedList.remove())\n# display array contents\nprint 'Sorted Array: ',\nfor j in range(size):\n print linkArray[j].dData ,", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Unsorted array: 28 87 63 12 73 91 30 91 85 65 \nSorted Array: 12 28 30 63 65 73 85 87 91 91\n" + } + ], + "prompt_number": 7 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.8 Page no : 226" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 5.8\ndemonstrates doubly-linked list\n'''\nclass Link:\n def __init__(self,d): # constructor\n self.dData = d\n self.next = None\n self.previous = None\n\n def displayLink(self): # display this link\n print self.dData ,\n\nclass DoublyLinkedList:\n def __init__(self):\n self.first = None # no items on list yet\n self.last = None\n\n def isEmpty(self): # true if no links\n return self.first==None\n\n def insertFirst(self,dd): # insert at front of list\n newLink = Link(dd) # make new link\n if( self.isEmpty() ): # if empty list, \n self.last = newLink # newLink <-- last\n else:\n self.first.previous = newLink # newLink <-- old first\n newLink.next = self.first # newLink --> old first\n self.first = newLink # first --> newLink\n\n def insertLast(self,dd): # insert at end of list\n newLink = Link(dd) # make new link\n if( self.isEmpty() ) : # if empty list,\n self.first = newLink # first --> newLink\n else:\n self.last.next = newLink # old last --> newLink\n newLink.previous = self.last # old last <-- newLink\n self.last = newLink # newLink <-- last\n\n def deleteFirst(self): # delete first link\n # (assumes non-empty list)\n temp = self.first\n if(self.first.next == None): # if only one item\n self.last = None # None <-- last\n else:\n self.first.next.previous = None # None <-- old next\n self.first = self.first.next # first --> old next\n return temp\n\n def deleteLast(self): # delete last link\n # (assumes non-empty list)\n temp = self.last\n if(self.first.next == None): # if only one item\n self.first = None # first --> None\n else:\n self.last.previous.next = None # old previous --> None\n self.last = self.last.previous # old previous <-- last\n return temp\n\n # insert dd just after key\n def insertAfter(self,key,dd):\n # (assumes non-empty list)\n current = self.first # start at beginning\n while(current.dData != key): # until match is found,\n current = current.next # move to next link\n if(current == None):\n return False # didnt find it\n newLink = Link(dd) # make new link\n if(current==self.last): # if last link,\n newLink.next = None # newLink --> None\n self.last = newLink# newLink <-- last\n else: # not last link,\n newLink.next = current.next # newLink --> old next # newLink <-- old next\n current.next.previous = newLink\n newLink.previous = current # old current <-- newLink\n current.next = newLink # old current --> newLink\n return True # found it, did insertion\n\n def deleteKey(self,key): # delete item w/ given key\n # (assumes non-empty list)\n current = self.first # start at beginningDoubly Linked Lists\n while(current.dData != key):\n current = current.next\n if(current == None):\n return None\n if(current==self.first):\n self.first = current.next\n else: \n # until match is found, move to next link didnt find it found it first item? first --> old next\n # not first old previous --> old next\n current.previous.next = current.next\n if(current==self.last):\n self.last = current.previous\n else:\n # last item? old previous <-- last not last old previous <-- old next \n current.next.previous = current.previous\n return current # return value\n\n def displayForward(self):\n print 'List (first-->last): ',\n current = self.first # start at beginning\n while(current != None): # until end of list,\n current.displayLink()# display data\n current = current.next # move to next link\n print ''\n\n def displayBackward(self):\n print 'List (last-->first): ' ,\n current = self.last # start at end\n while(current != None): # until start of list,\n current.displayLink() # display data\n current = current.previous # move to previous link\n print ''\n\n# make a new list\ntheList = DoublyLinkedList()\ntheList.insertFirst(22) # insert at front\ntheList.insertFirst(44) \ntheList.insertFirst(66) \ntheList.insertLast(11) # insert at rear\ntheList.insertLast(33) \ntheList.insertLast(55) \ntheList.displayForward() # display list forward\ntheList.displayBackward() # display list backward\ntheList.deleteFirst() # delete first item\ntheList.deleteLast() # delete last item\ntheList.deleteKey(11) # delete item with key 11\ntheList.displayForward() # display list forward\ntheList.insertAfter(22, 77) # insert 77 after 22\ntheList.insertAfter(33, 88) # insert 88 after 33\ntheList.displayForward() # display list forward", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "List (first-->last): 66 44 22 11 33 55 \nList (last-->first): 55 33 11 22 44 66 \nList (first-->last): 44 22 33 \nList (first-->last): 44 22 77 33 88 \n" + } + ], + "prompt_number": 8 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 5.9 Page No : 235" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 5.9\ndemonstrates iterators on a linked listListIterator\n'''\nclass Link:\n def __init__(self,d): # constructor\n self.dData = d\n self.next = None\n\n def displayLink(self): # display this link\n print self.dData ,\n\nclass LinkList:\n def __init__(self):\n self.first = None\n\n def isEmpty(self): # true if list is empty\n return (self.first==None)\n\n # insert at start of list\n def insertFirst(self,i, dd):\n # make new link\n newLink = Link(i, dd)\n newLink.next = self.first\n # newLink --> old first\n self.first = newLink\n\n def deleteFirst(self):\n temp = self.first\n self.first = self.first.next\n return temp\n \n def displayList(self):\n print 'List (first-->last): ' ,\n current = self.first\n while(current != None):\n current.displayLink()\n current = current.next\n print ''\n\n def find(self,key): # find link with given key\n current = self.first #start at first\n while(current.iData != key): # while no match,\n if(current.next == None): # if end of list,\n return None # didnt find it\n else:\n current = current.next # go to next link\n return current\n \n def delete(self,key): # delete link with given key\n current = self.first \n previous = self.first\n while(current.iData != key):\n if(current.next == None):\n return None # didnt find it\n else:\n previous = current\n current = current.next\n if(current == self.first): # if first link,\n self.first = self.first.next\n else:\n previous.next = current.next\n return current\n\n def getFirst(self): # get value of first\n return self.first\n\n def setFirst(self,f): # set first to new link\n self.first = f\n\n def getIterator(self): # return iterator\n return ListIterator(self) # initialized with\n\nclass ListIterator:\n def __init__(self,l): # constructor\n self.ourList = l\n self.reset()\n self.current = None\n self.previous = None\n\n def reset(self): # start at first\n self.current = self.ourList.getFirst()\n self.previous = None\n\n def atEnd(self): # true if last link\n return (self.current.next==None) \n \n def nextLink(self): # go to next link\n self.previous = self.current\n self.current = self.current.next\n\n def getCurrent(self): # get current link\n return self.current \n\n def insertAfter(self,dd): # insert after\n # current link\n newLink = Link(dd)\n if( self.ourList.isEmpty() ):# empty list\n self.ourList.setFirst(newLink)\n self.current = newLink\n else: # not empty\n newLink.next = self.current.next\n self.current.next = newLink\n self.nextLink() # point to new link\n\n def insertBefore(self,dd): # insert before\n # current link\n newLink = Link(dd)\n if(self.previous == None): # beginning of list (or empty list)\n newLink.next = self.ourList.getFirst()\n self.ourList.setFirst(newLink)\n self.reset()\n else: # not beginning\n newLink.next = self.previous.next\n self.previous.next = newLink\n self.current = newLink\n\n def deleteCurrent(self): # delete item at current\n value = self.current.dData\n if(self.previous == None): # beginning of list\n self.ourList.setFirst(self.current.next)\n self.reset()\n else: # not beginning\n self.previous.next = self.current.next\n if( self.atEnd() ):\n self.reset()\n else:\n current = current.next\n return value\n\ntheList = LinkList() # new list\niter1 = theList.getIterator() # new iter\niter1.insertAfter(20)\niter1.insertAfter(40)\niter1.insertAfter(80)\niter1.insertBefore(60) # insert items\nwhile(True):\n print 'Enter first letter of show, reset, ' , \n print 'next, get, before, after, delete: ' ,\n choice = raw_input() # get users option\n if choice == 's': # show list\n if( not theList.isEmpty() ):\n theList.displayList()\n else:\n print 'List is empty'\n elif choice == 'r': # reset (to first)\n iter1.reset()\n elif choice == 'n': # advance to next item\n if( not theList.isEmpty() and not iter1.atEnd() ):\n iter1.nextLink()\n else:\n print \"Cant go to next link\"\n elif choice=='g': # get current item\n if( not theList.isEmpty() ):\n value = iter1.getCurrent().dData\n print \"Returned \" , value\n else:\n print \"List is empty\"\n elif choice == 'b': # insert before current\n print \"Enter value to insert: \",\n value = raw_input()\n iter1.insertBefore(value)\n elif choice=='a': # insert after current\n print \"Enter value to insert: \",\n value = raw_input()\n iter1.insertAfter(value)\n elif choice == 'd': # delete current item\n if( not theList.isEmpty() ):\n value = iter1.deleteCurrent()\n print \"Deleted \" , value\n else:\n print \"Cant delete\"\n else:\n print \"Invalid entry\"\n break", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "s\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " List (first-->last): 20 40 60 80 \nEnter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "r\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "n\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "n\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "g\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Returned 60\nEnter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "b\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter value to insert: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "100\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "a\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter value to insert: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "7\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "s\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " List (first-->last): 20 40 100 7 60 80 \nEnter first letter of show, reset, next, get, before, after, delete: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Invalid entry\n" + } + ], + "prompt_number": 10 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch6.ipynb b/Data_Structures_and_Algorithms_in_Java/ch6.ipynb new file mode 100644 index 00000000..483043b8 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch6.ipynb @@ -0,0 +1,240 @@ +{ + "metadata": { + "name": "ch6" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 6 : Recursion" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.1 Page No : 255" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 6.1\nevaluates triangular numbers\n'''\n\ndef triangle(n):\n if(n==1):\n return 1\n else:\n return( n + triangle(n-1) )\n\nprint 'Enter a number: ' ,\ntheNumber = int(raw_input())\ntheAnswer = triangle(theNumber)\nprint 'Triangle = ' , theAnswer\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": " Enter a number: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "50\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Triangle = 1275\n" + } + ], + "prompt_number": 11 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.2 Page No : 265" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 6.2\ncreates anagrams\n'''\narrChar = []\nsize = 0\ncount = 0\ndef doAnagram(newSize):\n if(newSize == 1): # if too small,\n return\n for j in range(newSize): # for each position,\n doAnagram(newSize-1) # anagram remaining\n if(newSize==2): # if innermost,\n displayWord()\n rotate(newSize);\n\ndef rotate(newSize):\n global size\n global arrChar\n position = size - newSize\n temp = arrChar[position]\n for j in range(position+1,size):\n # shift others left\n arrChar[j-1] = arrChar[j]\n arrChar[size-1] = temp;\n\ndef displayWord():\n global count\n global size\n global arrChar\n if(count < 99):\n print ' ' ,\n if(count < 9):\n print ' ' ,\n count += 1\n print count ,\n for j in range(size):\n print arrChar[j] ,\n print '' ,\n if(count%6 == 0):\n print ''\n\nprint 'Enter a word: '\ni = raw_input()\n#global size\nsize = len(i)\nfor j in range(size):\n arrChar.append(i[j])\ndoAnagram(size)\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter a word: \n" + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "cats\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " 1 c a t s 2 c a s t 3 c t s a 4 c t a s 5 c s a t 6 c s t a \n 7 a t s c 8 a t c s 9 a s c t 10 a s t c 11 a c t s 12 a c s t \n 13 t s c a 14 t s a c 15 t c a s 16 t c s a 17 t a s c 18 t a c s \n 19 s c a t 20 s c t a 21 s a t c 22 s a c t 23 s t c a 24 s t a c \n" + } + ], + "prompt_number": 19 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.3 Page No : 269" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nLISTING 6.3\ndemonstrates recursive binary search\n'''\nclass ordArray:\n def __init__(self,m): # constructor\n self.a = []\n self.nElems = 0\n def size(self):\n return self.nElems\n\n def find(self,searchKey):\n return self.recFind(searchKey, 0, self.nElems-1)\n\n def recFind(self,searchKey,lowerBound,upperBound):\n curIn = (lowerBound + upperBound ) / 2\n if(self.a[curIn]==searchKey):\n return curIn # found it\n elif(lowerBound > upperBound):\n return self.nElems # cant find it\n else: # divide range\n if(self.a[curIn] < searchKey): # its in upper half\n return self.recFind(searchKey, curIn+1, upperBound)\n else: # its in lower half\n return self.recFind(searchKey, lowerBound, curIn-1)\n\n def insert(self,value): # put element into array\n self.a.append(value)\n self.a.sort()\n self.nElems += 1\n\n def display(self): # displays array contents\n for j in range(self.nElems): # for each element,\n print self.a[j] , \n print ''\n\nmaxSize = 100 # array size\narr = ordArray(maxSize) # create the array\narr.insert(72)\narr.insert(90)\narr.insert(45)\narr.insert(126)\narr.insert(54)\narr.insert(99)\narr.insert(144)\narr.insert(27)\narr.insert(135)\narr.insert(81)\narr.insert(18)\narr.insert(108)\narr.insert(9)\narr.insert(117)\narr.insert(63)\narr.insert(36)\narr.display() # display array\nsearchKey = 27 # search for item\nif( arr.find(searchKey) != arr.size()):\n print 'Found ' , searchKey\nelse:\n print \"Can't find \" , searchKey", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144 \nFound 27\n" + } + ], + "prompt_number": 13 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.4 Page No : 278" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 6.4\nsolves the towers of Hanoi puzzle\n'''\ndef doTowers(topN,frm,inter,to):\n if(topN==1):\n print \"Disk 1 from \" , frm , \"to \" , to\n else:\n doTowers(topN-1, frm, to, inter) # from-->inter\n print \"Disk \" , topN ,\" from \" , frm , \" to \" , to\n doTowers(topN-1, inter, frm, to) # inter-->to\n\n\nnDisks = 3\ndoTowers(nDisks, 'A', 'B', 'C')\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Disk 1 from A to C\nDisk 2 from A to B\nDisk 1 from C to B\nDisk 3 from A to C\nDisk 1 from B to A\nDisk 2 from B to C\nDisk 1 from A to C\n" + } + ], + "prompt_number": 14 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.5 Page no : 281" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 6.5\ndemonstrates merging two arrays into a third\n'''\n# merge A and B into C\ndef merge(arrayA,sizeA,arrayB,sizeB,arrayC ):\n aDex=0\n bDex=0\n cDex=0\n while(aDex < sizeA and bDex < sizeB): # neither array empty\n if( arrayA[aDex] < arrayB[bDex] ):\n arrayC.append(arrayA[aDex])\n cDex += 1\n aDex += 1\n else:\n arrayC.append(arrayB[bDex])\n cDex += 1\n bDex += 1\n while(aDex < sizeA):\n arrayC.append(arrayA[aDex])\n cDex += 1\n aDex += 1\n while(bDex < sizeB):\n arrayC.append(arrayB[bDex]) # but arrayB isnt\n cDex +=1\n bDex += 1\n\ndef display(theArray,size):\n for j in range(size):\n print theArray[j],\n\n\n\narrayA = [23, 47, 81, 95]\narrayB = [7, 14, 39, 55, 62, 74]\narrayC = []\nmerge(arrayA, 4, arrayB, 6, arrayC)\ndisplay(arrayC, 10)\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "7 14 23 39 47 55 62 74 81 95\n" + } + ], + "prompt_number": 15 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.6 Page no : 288" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 6.6\ndemonstrates recursive merge sort\n'''\n\nclass DArray:\n def __init__(self,m):\n self.theArray = []\n self.nElems = 0\n \n def insert(self,value):\n self.theArray.append(value)\n self.nElems += 1\n\n def display(self): # displays array contents\n for j in range(self.nElems):\n print self.theArray[j] ,\n print ''\n\n def mergeSort(self):\n workSpace = []\n for i in range(self.nElems):\n workSpace.append(0)\n self.recMergeSort(workSpace, 0, self.nElems-1)\n\n def recMergeSort(self,workSpace, lowerBound,upperBound):\n if(lowerBound == upperBound): # if range is 1,\n return\n else:\n mid = (lowerBound+upperBound) / 2\n self.recMergeSort(workSpace, lowerBound, mid)\n self.recMergeSort(workSpace, mid+1, upperBound)\n self.merge(workSpace, lowerBound, mid+1, upperBound)\n\n def merge(self,workSpace,lowPtr,highPtr,upperBound):\n j = 0\n lowerBound = lowPtr\n mid = highPtr-1\n n = upperBound-lowerBound+1\n while(lowPtr <= mid and highPtr <= upperBound):\n if( self.theArray[lowPtr] < self.theArray[highPtr] ):\n workSpace[j] = self.theArray[lowPtr]\n j += 1\n lowPtr += 1\n else:\n workSpace[j] = self.theArray[highPtr]\n j += 1\n highPtr += 1\n while(lowPtr <= mid):\n workSpace[j] = self.theArray[lowPtr]\n j += 1\n lowPtr += 1\n while(highPtr <= upperBound):\n workSpace[j] = self.theArray[highPtr]\n j += 1\n highPtr += 1\n for j in range(n):\n self.theArray[lowerBound+j] = workSpace[j]\n\nmaxSize = 100 # array size\narr = DArray(maxSize) # create the array\narr.insert(64) # insert items\narr.insert(21) \narr.insert(33) \narr.insert(70) \narr.insert(12) \narr.insert(85) \narr.insert(44) \narr.insert(3) \narr.insert(99) \narr.insert(0) \narr.insert(108) \narr.insert(36) \narr.display() # display items\narr.mergeSort() # merge sort the array\narr.display() # display items again", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "64 21 33 70 12 85 44 3 99 0 108 36 \n0 3 12 21 33 36 44 64 70 85 99 108 \n" + } + ], + "prompt_number": 16 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.7 Page No :295" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 6.7\nevaluates triangular numbers, stack replaces recursion\n'''\nclass Params: #parameters to save on stack\n def __init__(self,nn, ra):\n self.n=nn\n self.returnAddress=ra\n\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\n\ntheNumber = 0\ntheAnswer = 0\ntheStack = None\ncodePart = 0\ntheseParams = None\ndef recTriangle():\n global theStack,codePart\n theStack = StackX(10000)\n codePart = 1\n while( step() == False): # call step() until it's true\n pass\n\ndef step():\n global theStack,codePart,theseParams,theAnswer,theNumber\n if codePart==1:\n # initial call\n theseParams = Params(theNumber, 6)\n theStack.push(theseParams);\n codePart = 2\n elif codePart==2:\n # method entry\n theseParams = theStack.peek()\n if(theseParams.n == 1):\n theAnswer = 1\n codePart = 5\n else:\n codePart = 3\n elif codePart==3:\n newParams = Params(theseParams.n - 1, 4)\n theStack.push(newParams)\n codePart = 2 # go enter method\n elif codePart==4:\n theseParams = theStack.peek()\n theAnswer = theAnswer + theseParams.n\n codePart = 5\n elif codePart==5: # method exit\n theseParams = theStack.peek()\n codePart = theseParams.returnAddress # (4 or 6)\n theStack.pop()\n elif codePart==6: # return point\n return True\n else:\n pass\n return False\n\nprint 'Enter a number: ' ,\ntheNumber = int(raw_input())\nrecTriangle()\nprint 'Triangle = ' ,theAnswer\n\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter a number: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "100\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Triangle = 5050\n" + } + ], + "prompt_number": 17 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 6.8 Page no : 301" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 6.8\nevaluates triangular numbers, stack replaces recursion\n'''\n\n\nclass StackX:\n def __init__(self,s):\n self.maxSize = s\n self.stackArray = []\n self.top = -1\n\n def push(self,j):\n self.top += 1\n self.stackArray.append(j)\n \n def pop(self):\n p = self.stackArray[self.top]\n self.top -= 1\n self.stackArray.remove(p)\n return p\n \n def peek(self):\n return self.stackArray[self.top]\n\n def isEmpty(self):\n return (self.top == -1)\n\n def isFull(self):\n return (self.top == self.maxSize-1);\ntheNumber = 0\ntheAnswer = 0\ntheStack = None\ntheseParams = None\n\ndef stackTriangle():\n global theNumber,theAnswer,theStack,theNumber\n theStack = StackX(10000)\n theAnswer = 0\n while(theNumber > 0): # until n is 1,\n theStack.push(theNumber) # push value\n theNumber -= 1 # decrement value\n\n while( not theStack.isEmpty() ): # until stack empty,\n newN = theStack.pop() # pop value,\n theAnswer += newN\n\nprint 'Enter a number: ' ,\ntheNumber = int(raw_input())\nstackTriangle()\nprint 'Triangle = ' ,theAnswer\n\n\n", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "Enter a number: " + }, + { + "name": "stdout", + "output_type": "stream", + "stream": "stdout", + "text": "50\n" + }, + { + "output_type": "stream", + "stream": "stdout", + "text": " Triangle = 1275\n" + } + ], + "prompt_number": 18 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch7.ipynb b/Data_Structures_and_Algorithms_in_Java/ch7.ipynb new file mode 100644 index 00000000..52523fdc --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch7.ipynb @@ -0,0 +1,133 @@ +{ + "metadata": { + "name": "ch7" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 7 : Advanced Sorting " + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 7.1 Page no : 321" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nExample 7.1\ndemonstrates shell sort\n'''\n\nclass ArraySh:\n def __init__(self,m): # constructor\n self.theArray = [] # create the array\n self.nElems = 0 # no items yet\n\n def insert(self,value): # put element into array\n self.theArray.append(value) # insert it\n self.nElems+=1 # increment size\n\n def display(self): # displays array contents\n print 'A=' , \n for j in range(self.nElems): # for each element,\n print self.theArray[j] , # display it\n print ''\n\n def shellSort(self):\n inner = 0\n outer = 0\n temp = 0\n h = 1\n while(h <= self.nElems/3):\n h = h*3 + 1\n while(h>0):\n # find initial value of h\n # (1, 4, 13, 40, 121, ...)\n # decreasing h, until h=1\n # h-sort the file\n for outer in range(h,self.nElems):\n temp = self.theArray[outer]\n inner = outer\n # one subpass (eg 0, 4, 8)\n while(inner > h-1 and self.theArray[inner-h] >= temp):\n self.theArray[inner] = self.theArray[inner-h]\n inner -= h\n self.theArray[inner] = temp\n h = (h-1) / 3\n\nmaxSize = 10 # array size\narr = ArraySh(maxSize) # create the array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\n\narr.display() # display unsorted array\narr.shellSort() # shell sort the array\narr.display() # display sorted array", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "A= 35 47 88 24 10 98 14 75 97 38 \nA= 10 14 24 35 38 47 75 88 97 98 \n" + } + ], + "prompt_number": 1 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 7.2 Page No 327" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 7.2\ndemonstrates partitioning an array\n'''\nclass ArrayPar:\n def __init__(self,m): # constructor\n self.theArray = [] # create the array\n self.nElems = 0 # no items yet\n\n def insert(self,value): # put element into array\n self.theArray.append(value) # insert it\n self.nElems += 1 # increment size\n\n def size(self): # return number of items\n return self.nElems \n\n def display(self): # displays array contents\n print 'A=' ,\n for j in range(self.nElems): # for each element,\n print self.theArray[j] , # display it\n print ''\n\n def partitionIt(self,left,right,pivot):\n leftPtr = left - 1 # right of first elem\n rightPtr = right + 1 # left of pivot\n while(True):\n leftPtr += 1\n while(leftPtr < right ):\n leftPtr += 1\n if self.theArray[leftPtr] < pivot:\n break\n while(rightPtr > left ):# find smaller item\n rightPtr -= 1\n if self.theArray[rightPtr] > pivot:\n break;\n if(leftPtr >= rightPtr): # if pointers cross,\n break\n else: # not crossed, so\n self.swap(leftPtr, rightPtr)\n return leftPtr\n\n def swap(self,dex1,dex2): # swap two elements\n temp = self.theArray[dex1] # A into temp\n self.theArray[dex1] = self.theArray[dex2] # B into A\n self.theArray[dex2] = temp # temp into BPartitioning\n\nmaxSize = 16 # array size\narr = ArrayPar(maxSize) # create the array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*199)\n arr.insert(n)\narr.display() # display unsorted array\npivot = 99 # pivot value\nprint \"Pivot is \", pivot ,\nsize = arr.size() # partition array\npartDex = arr.partitionIt(0, size-1, pivot)\nprint \", Partition is at index \" , partDex \narr.display() # display partitioned array", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "A= 114 43 4 72 43 6 41 78 25 107 19 18 191 116 108 10 \nPivot is 99 , Partition is at index 9\nA= 114 108 4 116 43 191 41 107 25 78 19 18 6 72 43 10 \n" + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 7.3 Page no : 337" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 7.3\ndemonstrates simple version of quick sort\n'''\nclass ArrayIns:\n def __init__(self,m):\n self.theArray = [] # create the array\n self.nElems = 0 # no items yet\n\n def insert(self,value): # put element into array\n self.theArray.append( value) # insert it\n self.nElems += 1 # increment size\n\n def display(self): # displays array contents\n print 'A=' ,\n for j in range(self.nElems): # for each element,\n print self.theArray[j] , # display it\n print ''\n def quickSort(self):\n self.recQuickSort(0, self.nElems-1)\n\n def recQuickSort(self,left,right):\n if(right-left <= 0): # if size <= 1,\n return # already sorted\n else: # size is 2 or larger\n pivot = self.theArray[right] # rightmost item\n # partition range\n partition = self.partitionIt(left, right, pivot)\n self.recQuickSort(left, partition-1) # sort left side\n self.recQuickSort(partition+1, right) # sort right side\n\n def partitionIt(self,start, end,pivot):\n bottom = start-1 # Start outside the area to be partitioned\n top = end # Ditto\n done = 0\n while not done: # Until all elements are partitioned...\n while not done: # Until we find an out of place element...\n bottom = bottom+1 # ... move the bottom up.\n if bottom == top: # If we hit the top...\n done = 1 # ... we are done.\n break\n if self.theArray[bottom] > pivot: # Is the bottom out of place?\n self.theArray[top] = self.theArray[bottom] # Then put it at the top...\n break # ... and start searching from the top.\n while not done: # Until we find an out of place element...\n top = top-1 # ... move the top down.\n \n if top == bottom: # If we hit the bottom...\n done = 1 # ... we are done.\n break\n \n if self.theArray[top] < pivot: # Is the top out of place?\n self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...\n break # ...and start searching from the bottom.\n\n self.theArray[top] = pivot # Put the pivot in its place.\n return top # Return the split point\n\nmaxSize = 16 # array size\narr = ArrayIns(maxSize) # create array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\narr.display() # display items\narr.quickSort() # quicksort them\narr.display() # display them again", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "A= 63 42 31 37 74 79 6 76 0 5 7 6 82 48 26 70 \nA= 0 5 6 6 7 26 31 37 42 48 63 70 74 76 79 82 \n" + } + ], + "prompt_number": 3 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 7.4 Page No : 347" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 7.4\ndemonstrates quick sort with median-of-three partitioning\n'''\nclass ArrayIns:\n def __init__(self,m):\n self.theArray = [] # create the array\n self.nElems = 0 # no items yet\n\n def insert(self,value): # put element into array\n self.theArray.append(value) # insert it\n self.nElems+=1 # increment size\n\n def display(self): # displays array contents\n print 'A=' ,\n for j in self.theArray:\n print j , \n print ''\n \n def quickSort(self):\n self.recQuickSort(0, self.nElems-1)\n\n def recQuickSort(self,left,right):\n size = right-left+1\n if(size <= 3): # manual sort if small\n self.manualSort(left, right)\n else:\n median = self.medianOf3(left, right)\n partition = self.partitionIt(left, right, median)\n self.recQuickSort(left, partition-1)\n self.recQuickSort(partition+1, right)\n\n def partitionIt(self,start, end,pivot):\n bottom = start-1 # Start outside the area to be partitioned\n top = end # Ditto\n done = 0\n while not done: # Until all elements are partitioned...\n while not done: # Until we find an out of place element...\n bottom = bottom+1 # ... move the bottom up.\n if bottom == top: # If we hit the top...\n done = 1 # ... we are done.\n break\n if self.theArray[bottom] > pivot: # Is the bottom out of place?\n self.theArray[top] = self.theArray[bottom] # Then put it at the top...\n break # ... and start searching from the top.\n while not done: # Until we find an out of place element...\n top = top-1 # ... move the top down.\n \n if top == bottom: # If we hit the bottom...\n done = 1 # ... we are done.\n break\n \n if self.theArray[top] < pivot: # Is the top out of place?\n self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...\n break # ...and start searching from the bottom.\n\n self.theArray[top] = pivot # Put the pivot in its place.\n return top # Return the split point \n \n \n \n def medianOf3(self,left, right):\n center = (left+right)/2 # order left & center\n if( self.theArray[left] > self.theArray[center] ):\n self.theArray[left],self.theArray[center] = self.theArray[center],self.theArray[left]\n if( self.theArray[left] > self.theArray[right] ):\n self.theArray[left],self.theArray[right] = self.theArray[right],self.theArray[left]\n if( self.theArray[center] > self.theArray[right] ):\n self.theArray[right],self.theArray[center] = self.theArray[center],self.theArray[right]\n self.theArray[right-1],self.theArray[center] = self.theArray[center],self.theArray[right-1] # put pivot on right\n return self.theArray[right-1] # return median value\n\n def manualSort(self,left,right):\n size = right-left+1\n if(size <= 1):\n return # no sort necessary\n if(size == 2): # 2-sort left and right\n if( self.theArray[left] > self.theArray[right] ):\n self.theArray[right],self.theArray[left] = self.theArray[left],self.theArray[right]\n return\n else: # size is 3\n # 3-sort left, center, & right\n if( self.theArray[left] > self.theArray[right-1] ):\n self.theArray[right-1],self.theArray[left] = self.theArray[left],self.theArray[right-1] # left, center\n if( self.theArray[left] > self.theArray[right] ):\n self.theArray[right],self.theArray[left] = self.theArray[left],self.theArray[right] # left, right\n if( self.theArray[right-1] > self.theArray[right] ):\n self.theArray[right-1],self.theArray[right] = self.theArray[right],self.theArray[right-1] # center, right\n\n\nmaxSize = 16 # array size\narr = ArrayIns(maxSize) # create array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\narr.display() # display items\narr.quickSort() # quicksort them\narr.display() # display them again", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "A= 93 28 45 24 83 16 56 62 26 13 62 49 29 89 63 18 \nA= 13 16 18 18 24 26 28 28 29 45 45 62 62 63 83 83 \n" + } + ], + "prompt_number": 4 + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Example 7.5 Page No : 351" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 7.5\ndemonstrates quick sort uses insertion sort for cleanup\n'''\nclass ArrayIns:\n def __init__(self,m):\n self.theArray = [] # create the array\n self.nElems = 0 # no items yet\n\n def insert(self,value): # put element into array\n self.theArray.append(value) # insert it\n self.nElems+=1 # increment size\n\n def display(self): # displays array contents\n print 'A=' ,\n for j in self.theArray:\n print j , \n print ''\n \n def quickSort(self):\n self.recQuickSort(0, self.nElems-1)\n\n def recQuickSort(self,left,right):\n size = right-left+1\n if(size <= 10): \n self.insertionSort(left, right)\n else:\n median = self.medianOf3(left, right)\n partition = self.partitionIt(left, right, median)\n self.recQuickSort(left, partition-1)\n self.recQuickSort(partition+1, right)\n\n def partitionIt(self,start, end,pivot):\n bottom = start-1 # Start outside the area to be partitioned\n top = end # Ditto\n done = 0\n while not done: # Until all elements are partitioned...\n while not done: # Until we find an out of place element...\n bottom = bottom+1 # ... move the bottom up.\n if bottom == top: # If we hit the top...\n done = 1 # ... we are done.\n break\n if self.theArray[bottom] > pivot: # Is the bottom out of place?\n self.theArray[top] = self.theArray[bottom] # Then put it at the top...\n break # ... and start searching from the top.\n while not done: # Until we find an out of place element...\n top = top-1 # ... move the top down.\n \n if top == bottom: # If we hit the bottom...\n done = 1 # ... we are done.\n break\n \n if self.theArray[top] < pivot: # Is the top out of place?\n self.theArray[bottom] = self.theArray[top] # Then put it at the bottom...\n break # ...and start searching from the bottom.\n\n self.theArray[top] = pivot # Put the pivot in its place.\n return top # Return the split point \n \n \n \n def medianOf3(self,left, right):\n center = (left+right)/2 # order left & center\n if( self.theArray[left] > self.theArray[center] ):\n self.theArray[left],self.theArray[center] = self.theArray[center],self.theArray[left]\n if( self.theArray[left] > self.theArray[right] ):\n self.theArray[left],self.theArray[right] = self.theArray[right],self.theArray[left]\n if( self.theArray[center] > self.theArray[right] ):\n self.theArray[right],self.theArray[center] = self.theArray[center],self.theArray[right]\n self.theArray[right-1],self.theArray[center] = self.theArray[center],self.theArray[right-1] # put pivot on right\n return self.theArray[right-1] # return median value\n\n def insertionSort(self,left,right):\n i = 0\n out = 0 # sorted on left of out\n for out in range(left+1,right+1):\n temp = self.theArray[out] # remove marked item\n i = out # start shifts at out\n # until one is smaller,\n while(i >left and self.theArray[i-1] >= temp):\n self.theArray[i] = self.theArray[i-1] # shift item to right\n i -= 1 # go left one position\n self.theArray[i] = temp # insert marked item\n\nmaxSize = 16 # array size\narr = ArrayIns(maxSize) # create array\nimport random\nfor j in range(maxSize): # fill array with\n # random numbers\n n = int(random.random()*99)\n arr.insert(n)\narr.display() # display items\narr.quickSort() # quicksort them\narr.display() # display them again", + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": "A= 32 49 43 84 84 76 63 70 37 50 13 46 46 19 60 72 \nA= 13 19 32 32 37 43 46 49 50 60 63 70 70 76 84 84 \n" + } + ], + "prompt_number": 5 + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/ch8.ipynb b/Data_Structures_and_Algorithms_in_Java/ch8.ipynb new file mode 100644 index 00000000..6e978756 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch8.ipynb @@ -0,0 +1,42 @@ +{ + "metadata": { + "name": "ch8" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": "Chapter 8 : Binary Trees" + }, + { + "cell_type": "heading", + "level": 3, + "metadata": {}, + "source": "Exmaple 8.1 Page No : 406" + }, + { + "cell_type": "code", + "collapsed": false, + "input": "'''\nexample 8.1\ndemonstrates binary tree\n'''\n\n# for Stack class\nclass Node:\n def __init__(self):\n self.iData = None # data item (key)\n self.dData = None # data item\n self.leftChild = None # this nodes left child\n self.rightChild = None # this nodes right child\n\n def displayNode(self):\n # display ourself\n print '{' , self.iData , ',' ,self.dData , '}',\n\nclass Tree:\n def __init__(self):\n # constructor\n self.root = None # no nodes in tree \n\n def find(self,key): # find node with given key\n # (assumes non-empty tree)\n current = self.root # start at self.root\n while(current.iData != key): # while no match,\n if(key < current.iData): # go left?\n current = current.leftChild\n else: # or go right?\n current = current.rightChild\n if(current == None): # if no child,\n return None # didnt find it\n return current\n\n def insert(self,i,dd):\n newNode = Node() # make new node\n newNode.iData = i # insert data\n newNode.dData = dd\n if(self.root==None):# no node in self.root\n self.root = newNode\n else: # self.root occupied\n current = self.root # start at self.root\n while(True): # (exits internally)\n parent = current\n if(i < current.iData): # go left?\n current = current.leftChild\n if(current == None): # if end of the line,\n # insert on left\n parent.leftChild = newNode\n return\n else:# or go right?\n current = current.rightChild\n if(current == None): # if end of the line \n # insert on right\n parent.rightChild = newNode\n return\n\n def delete(self,key): # delete node with given key\n # (assumes non-empty list)\n current = self.root\n parent = self.root\n isLeftChild = True\n while(current.iData != key):\n parent = current\n if(key < current.iData):\n isLeftChild = True\n current = current.leftChild\n else:\n isLeftChild = False\n current = current.rightChild\n if(current == None):\n return False\n # if no children, simply delete it\n if(current.leftChild==None and current.rightChild==None):\n if(current == self.root): # if self.root,\n self.root = None # tree is empty\n elif(isLeftChild):\n parent.leftChild = None\n else:\n parent.rightChild = None\n\n elif(current.rightChild==None):\n if(current == self.root):\n self.root = current.leftChild\n elif(isLeftChild):\n parent.leftChild = current.leftChild\n else:\n parent.rightChild = current.leftChild # if no left child, replace with right subtree\n elif(current.leftChild==None):\n if(current == self.root):\n self.root = current.rightChild\n elif(isLeftChild):\n parent.leftChild = current.rightChild\n else:\n parent.rightChild = current.rightChild\n else: # two children, so replace with inorder successor\n # get successor of node to delete (current)\n successor = self.getSuccessor(current)\n # connect parent of current to successor instead\n if(current == self.root):\n self.root = successor\n elif(isLeftChild):\n parent.leftChild = successor\n else:\n parent.rightChild = successor\n # connect successor to currents left child\n successor.leftChild = current.leftChild\n return True\n\n def getSuccessor(self,delNode):\n successorParent = delNode\n successor = delNode\n current = delNode.rightChild # go to right child\n while(current != None): # until no more\n # left children,\n successorParent = successor\n successor = current\n current = current.leftChild # go to left child\n # if successor not\n if(successor != delNode.rightChild): # right child,\n # make connections\n successorParent.leftChild = successor.rightChild\n successor.rightChild = delNode.rightChild\n return successor\n\n def traverse(self,traverseType):\n if traverseType == 1:\n print '\\nPreorder traversal: ',\n self.preOrder(self.root)\n elif traverseType == 2:\n print '\\nInorder traversal: ',\n self.inOrder(self.root)\n else:\n print '\\nPostorder traversal: ',\n self.postOrder(self.root)\n print ''\n\n def preOrder(self, localroot):\n if(localroot != None):\n print localroot.iData ,\n self.preOrder(localroot.leftChild)\n self.preOrder(localroot.rightChild)\n\n def inOrder(self, localroot):\n if(localroot != None):\n self.inOrder(localroot.leftChild)\n print localroot.iData ,\n self.inOrder(localroot.rightChild)\n \n def postOrder(self, localroot):\n if(localroot != None):\n self.postOrder(localroot.leftChild)\n self.postOrder(localroot.rightChild)\n print localroot.iData ,\n\n def displayTree(self):\n globalStack = list()\n globalStack.append(self.root)\n nBlanks = 32\n isRowEmpty = False\n print '\\n......................................................'\n while(isRowEmpty==False):\n localStack = list()\n isRowEmpty = True\n for j in range(nBlanks):\n print ' ',\n while(globalStack is not None):\n temp = globalStack.pop()\n if(temp != None):\n print temp.iData,\n localStack.append(temp.leftChild)\n localStack.append(temp.rightChild)\n if(temp.leftChild != None or temp.rightChild != None):\n isRowEmpty = False\n else:\n print '--' ,\n localStack.push(None)\n localStack.push(None)\n for j in range(nBlanks*2-2):\n print ' ', # end while globalStack not empty\n \n print ''\n nBlanks /= 2\n while(localStack is not None):\n globalStack.append( localStack.pop() ) # end while isRowEmpty is false\n \n print '\\n......................................................'\n\ntheTree = Tree()\ntheTree.insert(50,1.5)\ntheTree.insert(25,1.2)\ntheTree.insert(75,1.7)\ntheTree.insert(12,1.5)\ntheTree.insert(37,1.2)\ntheTree.insert(43,1.7)\ntheTree.insert(30,1.5)\ntheTree.insert(33,1.2)\ntheTree.insert(87,1.7)\ntheTree.insert(93,1.5)\ntheTree.insert(97,1.5)\nwhile(True):\n print 'Enter first letter of show, '\n print 'insert, find, delete, or traverse: ',\n choice = raw_input()\n if choice == 's':\n theTree.displayTree()\n elif choice == 'i':\n print 'Enter value to insert: '\n value = int(raw_input())\n theTree.insert(value, value + 0.9)\n elif choice == 'f':\n print 'Enter value to find: ',\n value = int(raw_input())\n found = theTree.find(value)\n if(found != None):\n print 'Found: ', \n found.displayNode()\n print ''\n else:\n print 'Could not find', value \n elif choice=='d':\n print 'Enter value to delete: ',\n value = int(raw_input())\n didDelete = theTree.delete(value)\n if(didDelete):\n print 'Deleted ' , value \n else:\n print 'Could not delete ',value\n elif choice=='t':\n print 'Enter type 1, 2 or 3: '\n value = int(raw_input())\n theTree.traverse(value)\n else:\n print 'Invalid entry'\n", + "language": "python", + "metadata": {}, + "outputs": [] + }, + { + "cell_type": "code", + "collapsed": false, + "input": "", + "language": "python", + "metadata": {}, + "outputs": [] + } + ], + "metadata": {} + } + ] +}
\ No newline at end of file diff --git a/Data_Structures_and_Algorithms_in_Java/screenshots/hashtableslinear.png b/Data_Structures_and_Algorithms_in_Java/screenshots/hashtableslinear.png Binary files differnew file mode 100644 index 00000000..a8a3ab96 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/screenshots/hashtableslinear.png diff --git a/Data_Structures_and_Algorithms_in_Java/screenshots/shellsorting.png b/Data_Structures_and_Algorithms_in_Java/screenshots/shellsorting.png Binary files differnew file mode 100644 index 00000000..4cf4d4ca --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/screenshots/shellsorting.png diff --git a/Data_Structures_and_Algorithms_in_Java/screenshots/shortestpath.png b/Data_Structures_and_Algorithms_in_Java/screenshots/shortestpath.png Binary files differnew file mode 100644 index 00000000..876ddd19 --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/screenshots/shortestpath.png |
