{
 "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": {}
  }
 ]
}