diff options
| author | hardythe1 | 2015-05-05 14:21:39 +0530 |
|---|---|---|
| committer | hardythe1 | 2015-05-05 14:21:39 +0530 |
| commit | fba055ce5aa0955e22bac2413c33493b10ae6532 (patch) | |
| tree | be70ef4fccd07c9c88de778014219201b4ea971f /Elements_of_discrete_mathematics/Chapter9.ipynb | |
| parent | 67068710030ddd6b6c809518c34af2e04e0bf7ca (diff) | |
| download | Python-Textbook-Companions-fba055ce5aa0955e22bac2413c33493b10ae6532.tar.gz Python-Textbook-Companions-fba055ce5aa0955e22bac2413c33493b10ae6532.tar.bz2 Python-Textbook-Companions-fba055ce5aa0955e22bac2413c33493b10ae6532.zip | |
add books
Diffstat (limited to 'Elements_of_discrete_mathematics/Chapter9.ipynb')
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter9.ipynb | 285 |
1 files changed, 285 insertions, 0 deletions
diff --git a/Elements_of_discrete_mathematics/Chapter9.ipynb b/Elements_of_discrete_mathematics/Chapter9.ipynb new file mode 100755 index 00000000..2c4b742e --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter9.ipynb @@ -0,0 +1,285 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:fe52e80aefa7cef4c97d80a1d8ac06d5a056bd7deebddce40f058e873b9c3a02"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "9 Recurrence relations and recursive algorithms"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 15:Page 421"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"MERGE SORT\"\n",
+ "alist=[65,43,22,54,87,11,76,48,30,60,19,75,94,27,58,80]#List to be sorted\n",
+ "def mergesort(alist):\n",
+ " print \"Splitting\",alist\n",
+ " if len(alist)>1:\n",
+ " \n",
+ " mid=len(alist)/2\n",
+ " left_half=alist[:mid]\n",
+ " right_half=alist[mid:]#Spltting into halves\n",
+ " mergesort(left_half)\n",
+ " mergesort(right_half)#Recirsive split to obtain values\n",
+ " i=0\n",
+ " j=0\n",
+ " k=0#Varaibles for indexing\n",
+ " while i<len(left_half) and j<len(right_half):\n",
+ " if left_half[i]<right_half[j]:\n",
+ " alist[k]=left_half[i]#Puts the minimum value in the beginning\n",
+ " i=i+1\n",
+ " else:\n",
+ " alist[k]=right_half[j]\n",
+ " j=j+1\n",
+ " k=k+1\n",
+ " while i<len(left_half):\n",
+ " alist[k]=left_half[i]#Combine left sorted elements to the whole list\n",
+ " i=i+1\n",
+ " k=k+1\n",
+ " while j<len(right_half):\n",
+ " alist[k]=right_half[j]#Combine right sorted elements to the wholw list\n",
+ " j=j+1\n",
+ " k=k+1\n",
+ " print \"Merging\",alist\n",
+ " \n",
+ "mergesort(alist)\n",
+ "print(alist)\n",
+ "\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "MERGE SORT\n",
+ "Splitting [65, 43, 22, 54, 87, 11, 76, 48, 30, 60, 19, 75, 94, 27, 58, 80]\n",
+ "Splitting [65, 43, 22, 54, 87, 11, 76, 48]\n",
+ "Splitting [65, 43, 22, 54]\n",
+ "Splitting [65, 43]\n",
+ "Splitting [65]\n",
+ "Merging [65]\n",
+ "Splitting [43]\n",
+ "Merging [43]\n",
+ "Merging [43, 65]\n",
+ "Splitting [22, 54]\n",
+ "Splitting [22]\n",
+ "Merging [22]\n",
+ "Splitting [54]\n",
+ "Merging [54]\n",
+ "Merging [22, 54]\n",
+ "Merging [22, 43, 54, 65]\n",
+ "Splitting [87, 11, 76, 48]\n",
+ "Splitting [87, 11]\n",
+ "Splitting [87]\n",
+ "Merging [87]\n",
+ "Splitting [11]\n",
+ "Merging [11]\n",
+ "Merging [11, 87]\n",
+ "Splitting [76, 48]\n",
+ "Splitting [76]\n",
+ "Merging [76]\n",
+ "Splitting [48]\n",
+ "Merging [48]\n",
+ "Merging [48, 76]\n",
+ "Merging [11, 48, 76, 87]\n",
+ "Merging [11, 22, 43, 48, 54, 65, 76, 87]\n",
+ "Splitting [30, 60, 19, 75, 94, 27, 58, 80]\n",
+ "Splitting [30, 60, 19, 75]\n",
+ "Splitting [30, 60]\n",
+ "Splitting [30]\n",
+ "Merging [30]\n",
+ "Splitting [60]\n",
+ "Merging [60]\n",
+ "Merging [30, 60]\n",
+ "Splitting [19, 75]\n",
+ "Splitting [19]\n",
+ "Merging [19]\n",
+ "Splitting [75]\n",
+ "Merging [75]\n",
+ "Merging [19, 75]\n",
+ "Merging [19, 30, 60, 75]\n",
+ "Splitting [94, 27, 58, 80]\n",
+ "Splitting [94, 27]\n",
+ "Splitting [94]\n",
+ "Merging [94]\n",
+ "Splitting [27]\n",
+ "Merging [27]\n",
+ "Merging [27, 94]\n",
+ "Splitting [58, 80]\n",
+ "Splitting [58]\n",
+ "Merging [58]\n",
+ "Splitting [80]\n",
+ "Merging [80]\n",
+ "Merging [58, 80]\n",
+ "Merging [27, 58, 80, 94]\n",
+ "Merging [19, 27, 30, 58, 60, 75, 80, 94]\n",
+ "Merging [11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]\n",
+ "[11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 17:Page 424"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"BINARY SEARCH\"\n",
+ "array=[\"\" for i in range(100)]\n",
+ "temp=0#Variable checks if the element has been found. Initialised to zero, if it retains the same value till the end, then the element is not in the given list\n",
+ "n=input(\"Enter the number of elements\")\n",
+ "print \"Enter the elememts in sorted order\"\n",
+ "for i in range(0,n):\n",
+ " array[i]=input()#Input the numbers in ascending order\n",
+ "item=input(\"Enter the item to be searched\")\n",
+ "first=0#\n",
+ "last=n-1\n",
+ "while first<=last:\n",
+ " mid=(first+last)/2#Finds the middle element\n",
+ " if item==array[mid]:\n",
+ " print \"Search is successfully completed\"\n",
+ " temp=mid\n",
+ " print \"The item is in position\",temp+1\n",
+ " \n",
+ " if item<array[mid]:#Divides the array into half depending on the value to be searched\n",
+ " last=mid-1\n",
+ " else:\n",
+ " first=mid+1\n",
+ "if temp==0:\n",
+ " print \"Search is not successfully completed\"\n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "BINARY SEARCH\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of elements7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the elememts in sorted order\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "16\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "25\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "49\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "50\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "67\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "84\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the item to be searched67\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Search is successfully completed\n",
+ "The item is in position 6\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file |