{
 "metadata": {
  "name": "",
  "signature": "sha256:e3b54ab088a42a68b5666c432cb7bb7b24f6ac5896dfbd8ae6cf469e8bea26f9"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Chapter 11: Dynamic Memory Allocation\n"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 1, page no. 407"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "g = 50\n",
      "def func(p):\n",
      "    s = 200\n",
      "    i = 10\n",
      "    print i, s\n",
      "a = 1\n",
      "print a\n",
      "print g\n",
      "func(-16)\n",
      "print \"over!\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n",
        "50\n",
        "10 200\n",
        "over!\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 2, page no. 409"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#there is no concept of malloc & free in Python\n",
      "\n",
      "print \"How many elements?: \",\n",
      "n = int(raw_input())\n",
      "ary = []\n",
      "print \"Enter the elements: \"\n",
      "for i in range(n):\n",
      "    ary.append(int(raw_input()))\n",
      "print \"The entered array is: \"\n",
      "for ele in ary:\n",
      "    print ele,"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "How many elements?: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " Enter the elements: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The entered array is: \n",
        "1 2 3\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.1, page no. 412"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "marks = []\n",
      "size = 3\n",
      "n = 0\n",
      "print \"Enter marks (-1 to stop: )\"\n",
      "mark = int(raw_input())\n",
      "while mark != -1:\n",
      "    if n >= size:\n",
      "        print \"realloc 3 more integers...\"\n",
      "        size += 3\n",
      "    marks.append(mark)\n",
      "    mark = int(raw_input())\n",
      "    n += 1\n",
      "\n",
      "for mark in marks:\n",
      "    print mark,"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter marks (-1 to stop: )\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "12\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "50\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "60\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "70\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "realloc 3 more integers...\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "80\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "90\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "realloc 3 more integers...\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "-1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "12 50 60 70 80 90 100\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.2, page no. 413"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy\n",
      "n = int(raw_input(\"Rows: \"))\n",
      "m = int(raw_input(\"Columns: \"))\n",
      "mat = numpy.zeros((n, m))\n",
      "print \"Input the elements: \"\n",
      "for i in range(n):\n",
      "    for j in range(m):\n",
      "        mat[i][j] = int(raw_input())\n",
      "print \"Input two rows to swap: \"\n",
      "i = int(raw_input())\n",
      "j = int(raw_input())\n",
      "mat[i], mat[j] = mat[j], mat[i]\n",
      "for i in range(n):\n",
      "    for j in range(m):\n",
      "        print mat[i][j],\n",
      "    print \"\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Rows: 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Columns: 5\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Input the elements: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "5\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "7\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Input two rows to swap: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2.0 4.0 6.0 8.0 10.0 \n",
        "6.0 7.0 8.0 9.0 0.0 \n",
        "2.0 4.0 6.0 8.0 10.0 \n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.3, page no. 415"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get(x, r, c):\n",
      "    for i in range(r):\n",
      "        for j in range(c):\n",
      "            x[i][j] = int(raw_input())\n",
      "    return x\n",
      "def display(x, r, c):\n",
      "    for i in range(r):\n",
      "        for j in range(c):\n",
      "            print x[i][j],\n",
      "        print \"\"\n",
      "def mul(a, b, c, row, m, col):\n",
      "    for i in range(row):\n",
      "        for j in range(col):\n",
      "            c[i][j] = 0\n",
      "            for k in range(m):\n",
      "               c[i][j] = c[i][j] + a[i][k] * b[k][j]\n",
      "    return c\n",
      "a = numpy.zeros((30, 30))            \n",
      "b = numpy.zeros((30, 30))            \n",
      "c = numpy.zeros((30, 30))            \n",
      "print \"Size of matrix A: \"\n",
      "r1 = int(raw_input(\"row: \"))\n",
      "c1 = int(raw_input(\"col: \"))\n",
      "print \"Size of matrix B: \"\n",
      "r2 = int(raw_input(\"row: \"))\n",
      "c2 = int(raw_input(\"col: \"))\n",
      "if c1 != r2:\n",
      "    print \"Multiplication not possible.\"\n",
      "    print \"columns of matrix A are not equal\"\n",
      "    print \"to rows of Matrix B\"\n",
      "else:\n",
      "    print \"Multiplication possible\"\n",
      "    print \"Matrix A(%d X %d) elements?\" %(r1, c1)\n",
      "    a = get(a, r1, c1)\n",
      "    print \"Matrix B(%d X %d) elements?\" %(r2, c2)\n",
      "    b = get(a, r1, c1)\n",
      "    c = mul(a, b, c, r1, c1, c2)\n",
      "    print \"Product matrix C(%d X %d): \" %(r1, c2)\n",
      "    display (c, r1, c2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Size of matrix A: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "row: 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "col: 4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Size of matrix B: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "row: 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "col: 3\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Multiplication possible\n",
        "Matrix A(3 X 4) elements?\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "5\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "7\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "11\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "12\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Matrix B(4 X 3) elements?\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "5\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "7\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "11\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "12\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Product matrix C(3 X 3): \n",
        "38.0 44.0 50.0 \n",
        "98.0 116.0 134.0 \n",
        "158.0 188.0 218.0 \n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Exmaple 11.4, page no. 419"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import sys\n",
      "\n",
      "class node:\n",
      "    def __init__(self, data=0, link=None):\n",
      "        self.data = data\n",
      "        self.link = link\n",
      "\n",
      "start = None\n",
      "    \n",
      "def add_front(data):\n",
      "    global start\n",
      "    tmp = node(data)\n",
      "    if(start == None):\n",
      "        start = tmp\n",
      "    else:\n",
      "        tmp.link = start\n",
      "        start = tmp\n",
      "\n",
      "def del_pos(pos):\n",
      "    global start\n",
      "    if (pos == 0):\n",
      "        tmp = start\n",
      "        start = start.link\n",
      "        return\n",
      "    q = start\n",
      "    count = 1\n",
      "    while(q.link != None):\n",
      "        if(count == pos):\n",
      "            tmp = q.link\n",
      "            q.link = tmp.link\n",
      "            return\n",
      "        count += 1\n",
      "        q = q.link\n",
      "    print \"\\n\\nThere is no element at %d position\" %pos\n",
      "        \n",
      "def del_elem(data):\n",
      "    global start\n",
      "    if (start.data == data):\n",
      "        tmp = start\n",
      "        start = start.link\n",
      "        return\n",
      "    q = start\n",
      "    while(q.link.link != None):\n",
      "        if(q.link.data == data):\n",
      "            tmp = q.link\n",
      "            q.link = tmp.link\n",
      "            return\n",
      "        q = q.link\n",
      "    if(q.link.data == data):\n",
      "        tmp = q.link;\n",
      "        q.link = None\n",
      "        return\n",
      "    print \"\\n\\nThere is no element whose value is %d\" %data\n",
      "\n",
      "def display_list():\n",
      "    global start\n",
      "    if(start == None):\n",
      "        print \"\\n\\nList empty\"\n",
      "        return\n",
      "    q=start\n",
      "    print \"\\nThe List is...\"\n",
      "    while(q != None):\n",
      "        print q.data,\n",
      "        q = q.link\n",
      "    print \"\\n\"\n",
      "\n",
      "def get_data():\n",
      "    data = int(raw_input(\"Enter the data: \"))\n",
      "    return data\n",
      "\n",
      "while(1):\n",
      "    print \"\\n1.Insert at the beginning of the list\"\n",
      "    print \"2.Delete an element at a give position\"\n",
      "    print \"3.Delete an element with a give value\"\n",
      "    print \"4.Quit\"\n",
      "    print \"Choice: \",\n",
      "    choice =int(raw_input())\n",
      "    if choice == 1:\n",
      "        data = get_data()\n",
      "        add_front(data)\n",
      "    elif choice == 2:\n",
      "        if (start == None):\n",
      "            print \"\\nList empty\"\n",
      "            continue\n",
      "        print \"\\n\\nEnter the position:\"\n",
      "        pos = int(raw_input())\n",
      "        del_pos(pos)\n",
      "    elif choice == 3:\n",
      "        if (start == None):\n",
      "            print \"\\nList empty\"\n",
      "            continue\n",
      "        data = get_data()\n",
      "        del_elem(data)\n",
      "    elif choice == 4:\n",
      "        break\n",
      "    display_list()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "2 1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 3\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "3 2 1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "\n",
        "Enter the position:\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "The List is...\n",
        "3 1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "2 3 1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "1 2 3 1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 5\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "5 1 2 3 1 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "\n",
        "Enter the position:\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "The List is...\n",
        "5 1 2 3 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Quit\n",
        "Choice: "
       ]
      }
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.5, page no. 424"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def bubble(x, upbound):\n",
      "    pas = upbound\n",
      "    while pas >= 0:\n",
      "        for i in range(pas):\n",
      "            if x[i] > x[i+1]:\n",
      "                x[i], x[i+1] = x[i+1], x[i]\n",
      "        pas -= 1\n",
      "    return x\n",
      "vector = []\n",
      "n = int(raw_input(\"Size of array? \"))\n",
      "for i in range(n):\n",
      "    vector.append(int(raw_input()))\n",
      "vector = bubble(vector, n-1)\n",
      "print \"Sorted array \"\n",
      "for ele in vector:\n",
      "    print ele,"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Size of array? 8\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "98\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "5\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "34\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "62\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "12\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "88\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Sorted array \n",
        "0 1 5 12 34 62 88 98\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.6, page no. 425"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "s1 = raw_input(\"Enter string one \")\n",
      "s2 = raw_input(\"Enter string two \")\n",
      "print \"Concatenated string is: \", s1+s2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter string one Tejaswi\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter string two .V.\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Concatenated string is:  Tejaswi.V.\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.7, page no. 425"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def sort_strings(strarr):\n",
      "    return sorted(strarr)\n",
      "\n",
      "n = int(raw_input(\"Number of strings: \"))\n",
      "str_array = []\n",
      "print \"Enter the strings: \"\n",
      "for i in range(n):\n",
      "    str_array.append(raw_input())\n",
      "\n",
      "strarr = sort_strings(str_array)\n",
      "print \"The sorted array is\"\n",
      "for string in strarr:\n",
      "    print string"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Number of strings: 5\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the strings: \n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Tejaswi\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Anand\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Rajkumar\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Maya\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Sudeep\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The sorted array is\n",
        "Anand\n",
        "Maya\n",
        "Rajkumar\n",
        "Sudeep\n",
        "Tejaswi\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 11.8, page no. 427"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import sys\n",
      "\n",
      "class node:\n",
      "    def __init__(self, data=0, link=None):\n",
      "        self.data = data\n",
      "        self.link = link\n",
      "\n",
      "start = None\n",
      "    \n",
      "def add_front(data):\n",
      "    global start\n",
      "    tmp = node(data)\n",
      "    if(start == None):\n",
      "        start = tmp\n",
      "    else:\n",
      "        tmp.link = start\n",
      "        start = tmp\n",
      "\n",
      "def del_pos(pos):\n",
      "    global start\n",
      "    if (pos == 0):\n",
      "        tmp = start\n",
      "        start = start.link\n",
      "        return\n",
      "    q = start\n",
      "    count = 1\n",
      "    while(q.link != None):\n",
      "        if(count == pos):\n",
      "            tmp = q.link\n",
      "            q.link = tmp.link\n",
      "            return\n",
      "        count += 1\n",
      "        q = q.link\n",
      "    print \"\\n\\nThere is no element at %d position\" %pos\n",
      "        \n",
      "def del_elem(data):\n",
      "    global start\n",
      "    if (start.data == data):\n",
      "        tmp = start\n",
      "        start = start.link\n",
      "        return\n",
      "    q = start\n",
      "    while(q.link.link != None):\n",
      "        if(q.link.data == data):\n",
      "            tmp = q.link\n",
      "            q.link = tmp.link\n",
      "            return\n",
      "        q = q.link\n",
      "    if(q.link.data == data):\n",
      "        tmp = q.link;\n",
      "        q.link = None\n",
      "        return\n",
      "    print \"\\n\\nThere is no element whose value is %d\" %data\n",
      "\n",
      "def display_list():\n",
      "    global start\n",
      "    if(start == None):\n",
      "        print \"\\n\\nList empty\"\n",
      "        return\n",
      "    q=start\n",
      "    print \"\\nThe List is...\"\n",
      "    while(q != None):\n",
      "        print q.data,\n",
      "        q = q.link\n",
      "    print \"\\n\"\n",
      "\n",
      "def smallest():\n",
      "    global start\n",
      "    q = start\n",
      "    min = q.data\n",
      "    pos = 0\n",
      "    min_pos = 0\n",
      "    while(q != None):\n",
      "        if q.data < min:\n",
      "            min = q.data\n",
      "            mis_pos = pos\n",
      "        pos += 1\n",
      "        q = q.link\n",
      "    return min, min_pos+1\n",
      "\n",
      "def largest():\n",
      "    global start\n",
      "    q = start\n",
      "    max = q.data\n",
      "    pos = 0\n",
      "    max_pos = 0\n",
      "    while(q != None):\n",
      "        if q.data > max:\n",
      "            max = q.data\n",
      "            max_pos = pos\n",
      "        pos += 1\n",
      "        q = q.link\n",
      "    return max, max_pos+1\n",
      "\n",
      "def get_data():\n",
      "    data = int(raw_input(\"Enter the data: \"))\n",
      "    return data\n",
      "\n",
      "while(1):\n",
      "    print \"\\n1.Insert at the beginning of the list\"\n",
      "    print \"2.Delete an element at a give position\"\n",
      "    print \"3.Delete an element with a give value\"\n",
      "    print \"4.Find smallest in the list\"\n",
      "    print \"5.Find largest in the list\"\n",
      "    print \"6.Quit\"\n",
      "    print \"Choice: \",\n",
      "    choice =int(raw_input())\n",
      "    if choice == 1:\n",
      "        data = get_data()\n",
      "        add_front(data)\n",
      "    elif choice == 2:\n",
      "        if (start == None):\n",
      "            print \"\\nList empty\"\n",
      "            continue\n",
      "        print \"\\n\\nEnter the position:\"\n",
      "        pos = int(raw_input())\n",
      "        del_pos(pos)\n",
      "    elif choice == 3:\n",
      "        if (start == None):\n",
      "            print \"\\nList empty\"\n",
      "            continue\n",
      "        data = get_data()\n",
      "        del_elem(data)\n",
      "    elif choice == 4:\n",
      "        min, pos = smallest()\n",
      "        print \"The smallest element has value \", min\n",
      "        print \"Its position is \", pos\n",
      "    elif choice == 5:\n",
      "        max, pos = largest()\n",
      "        print \"The largest element has value \", max\n",
      "        print \"Its position is \", pos\n",
      "    elif choice == 6:\n",
      "        break\n",
      "    display_list()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 56\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 34\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 45\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "45 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " The smallest element has value  34\n",
        "Its position is  1\n",
        "\n",
        "The List is...\n",
        "45 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "5\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " The largest element has value  56\n",
        "Its position is  3\n",
        "\n",
        "The List is...\n",
        "45 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 3\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "3 45 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 80\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "80 3 45 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "\n",
        "Enter the position:\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "\n",
        "There is no element at 9 position\n",
        "\n",
        "The List is...\n",
        "80 3 45 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "\n",
        "Enter the position:\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "The List is...\n",
        "80 3 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the data: 80\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " \n",
        "The List is...\n",
        "3 34 56 \n",
        "\n",
        "\n",
        "1.Insert at the beginning of the list\n",
        "2.Delete an element at a give position\n",
        "3.Delete an element with a give value\n",
        "4.Find smallest in the list\n",
        "5.Find largest in the list\n",
        "6.Quit\n",
        "Choice: "
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 16
    }
   ],
   "metadata": {}
  }
 ]
}