adding book

1 files changed, 240 insertions, 0 deletions

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