{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Solutions to the end sem exam"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Problem 1a"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Problem 1a\n",
      "def compute_f(m, n) :\n",
      "    if m >= n and n >= 0 :\n",
      "        if n == m or n == 0 :\n",
      "            print \"f(%d, %d) = 1\" % (m, n)\n",
      "            rval = 1\n",
      "        else :\n",
      "            rval = compute_f(m-1, n-1) + compute_f(m-1, n)\n",
      "            print \"f(%d, %d) = f(%d, %d) + f(%d, %d) = %d\" % (m, n, m-1,\\\n",
      "                                                         n-1, m-1, n, rval)\n",
      "\n",
      "    else :\n",
      "        print \"f(%d, %d) = None\" % (m, n)\n",
      "        rval = None\n",
      "    return rval"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(4+1) :\n",
      "    print compute_f(4, i)\n",
      "    print \"-\"*30"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "f(4, 0) = 1\n",
        "1\n",
        "------------------------------\n",
        "f(3, 0) = 1\n",
        "f(2, 0) = 1\n",
        "f(1, 0) = 1\n",
        "f(1, 1) = 1\n",
        "f(2, 1) = f(1, 0) + f(1, 1) = 2\n",
        "f(3, 1) = f(2, 0) + f(2, 1) = 3\n",
        "f(4, 1) = f(3, 0) + f(3, 1) = 4\n",
        "4\n",
        "------------------------------\n",
        "f(2, 0) = 1\n",
        "f(1, 0) = 1\n",
        "f(1, 1) = 1\n",
        "f(2, 1) = f(1, 0) + f(1, 1) = 2\n",
        "f(3, 1) = f(2, 0) + f(2, 1) = 3\n",
        "f(1, 0) = 1\n",
        "f(1, 1) = 1\n",
        "f(2, 1) = f(1, 0) + f(1, 1) = 2\n",
        "f(2, 2) = 1\n",
        "f(3, 2) = f(2, 1) + f(2, 2) = 3\n",
        "f(4, 2) = f(3, 1) + f(3, 2) = 6\n",
        "6\n",
        "------------------------------\n",
        "f(1, 0) = 1\n",
        "f(1, 1) = 1\n",
        "f(2, 1) = f(1, 0) + f(1, 1) = 2\n",
        "f(2, 2) = 1\n",
        "f(3, 2) = f(2, 1) + f(2, 2) = 3\n",
        "f(3, 3) = 1\n",
        "f(4, 3) = f(3, 2) + f(3, 3) = 4\n",
        "4\n",
        "------------------------------\n",
        "f(4, 4) = 1\n",
        "1\n",
        "------------------------------\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Problem 1b\n",
      "$f(m, n) = \\binom{m}{n}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Problem 2"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def fold(f, l) :\n",
      "    lenl = len(l)\n",
      "    if lenl == 0 :\n",
      "        rval = 0\n",
      "    elif lenl == 1 :\n",
      "        rval = l[0]\n",
      "    else :\n",
      "        rval = f(l[0], fold(f, l[1:]))\n",
      "    return rval"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print fold(lambda a, b : a + b, [1, 2, 3, 4])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Problem 3a"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Poly :\n",
      "    def __init__(self, l) :\n",
      "        self.l = l\n",
      "    def __call__(self, x) :\n",
      "        l = self.l\n",
      "        val = 0\n",
      "        for i in range(len(l)) :\n",
      "            val += l[i] * x**i\n",
      "        return val\n",
      "    def __str__(self) :\n",
      "        showstr = \"\"\n",
      "        for i in range(len(self.l)) :\n",
      "            if i == 0 :\n",
      "                showstr += str(self.l[i])\n",
      "            elif i == 1 :\n",
      "                showstr += ' + ' + str(self.l[i]) + ' x'\n",
      "            else :\n",
      "                showstr += \" + %g x^%d\" % (self.l[i], i)\n",
      "        showstr += '\\n'\n",
      "        return showstr\n",
      "    def __add__(self, other) :\n",
      "        sumpol = []\n",
      "        for i in range(max(len(self.l), len(other.l))) :\n",
      "            if i < len(self.l) and i < len(other.l) :\n",
      "                sumpol.append(self.l[i] + other.l[i])\n",
      "            elif i < len(self.l) :\n",
      "                sumpol.append(self.l[i])\n",
      "            elif i < len(other.l) :\n",
      "                sumpol.append(other.l[i])\n",
      "        return Poly(sumpol)\n",
      "    def __mul__(self, other) :\n",
      "        prodpol = []\n",
      "        sl = len(self.l)\n",
      "        ol = len(other.l)\n",
      "        for i in range((sl - 1) + (ol - 1) + 1) :\n",
      "            prodterm = 0\n",
      "            for j in range(i+1) :\n",
      "                if j < sl and i - j < ol :\n",
      "                    prodterm += self.l[j] * other.l[i - j]\n",
      "            prodpol.append(prodterm)\n",
      "        return Poly(prodpol)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def l(lot, i) :\n",
      "    no_of_tup = len(lot)\n",
      "    if i < 0 or i >= no_of_tup :\n",
      "        print \"i = %d is out of range.\" % i\n",
      "    else :\n",
      "        lipol = Poly([1])\n",
      "        for k in range(no_of_tup) :\n",
      "            if k != i :\n",
      "                xk = lot[k][0]\n",
      "                xi = lot[i][0]\n",
      "                lipol *= Poly([float(-xk)/(xi - xk), 1.0/(xi - xk)])\n",
      "    return lipol"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def compute_lagrange(lot) :\n",
      "    p = Poly([0])\n",
      "    for i in range(len(lot)) :\n",
      "        print \"l_%d(x) = %s\"% (i, l(lot, i))\n",
      "        p += l(lot, i) * Poly([lot[i][1]])\n",
      "    print \"p(x) = \", p\n",
      "    return p"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "lot = [(-2, 0), (0, 0), (2, 4)]\n",
      "compute_lagrange(lot)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "l_0(x) = 0.0 + -0.25 x + 0.125 x^2\n",
        "\n",
        "l_1(x) = 1.0 + 0.0 x + -0.25 x^2\n",
        "\n",
        "l_2(x) = 0.0 + 0.25 x + 0.125 x^2\n",
        "\n",
        "p(x) =  0.0 + 1.0 x + 0.5 x^2\n",
        "\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "<__main__.Poly instance at 0x7fd93c49f950>"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Problem 3b"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def find_num_der(f, x, h) :\n",
      "    num = float(f(x + h) - f(x - h))\n",
      "    den = float(2 * h)\n",
      "    return num/den"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = compute_lagrange(lot)\n",
      "print \"-\" * 20\n",
      "print \"dp/dx =\", find_num_der(p, -1, .1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "l_0(x) = 0.0 + -0.25 x + 0.125 x^2\n",
        "\n",
        "l_1(x) = 1.0 + 0.0 x + -0.25 x^2\n",
        "\n",
        "l_2(x) = 0.0 + 0.25 x + 0.125 x^2\n",
        "\n",
        "p(x) =  0.0 + 1.0 x + 0.5 x^2\n",
        "\n",
        "--------------------\n",
        "dp/dx = 0.0\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Problem 3c"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "matrix = [[2, 8, 6, 0], [3, 12, 9, 10]]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def elem1(mat, r1, r2) :\n",
      "    nrow = len(mat)\n",
      "    if nrow <= 1 :\n",
      "        print \"elem1 : Not enough rows.\"\n",
      "        rmat = None\n",
      "    else :\n",
      "        ncol = len(mat[0])\n",
      "        if ncol <= 0 :\n",
      "            print \"elem1 : Not enough columns\"\n",
      "            rmat = None\n",
      "        else :\n",
      "            if r1 < 0 or r1 >= nrow :\n",
      "                print \"r1 out of range.\"\n",
      "                rmat = None\n",
      "            elif r2 < 0 or r2 >= nrow :\n",
      "                print \"r2 out of range.\"\n",
      "                rmat = None\n",
      "            elif r1 == r2 :\n",
      "                print \"r1 = r2\"\n",
      "                rmat = list(mat)\n",
      "            else :\n",
      "                rmat = []\n",
      "                for i in range(nrow) :\n",
      "                    present_row = []\n",
      "                    for j in range(ncol) :\n",
      "                        if i == r1 :\n",
      "                            present_row.append(mat[r2][j])\n",
      "                        elif i == r2 :\n",
      "                            present_row.append(mat[r1][j])\n",
      "                        else :\n",
      "                            present_row.append(mat[i][j])\n",
      "                    rmat.append(present_row)\n",
      "    return rmat"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def elem2(mat, row, a) :\n",
      "    if len(mat) == 0 :\n",
      "        print \"Cannot process an empty matrix.\"\n",
      "        rmat = None\n",
      "    elif len(mat[0]) == 0 :\n",
      "        print \"Matrix should have non-empty rows\"\n",
      "        rmat = None\n",
      "    else :\n",
      "        ncol = len(mat[0])\n",
      "        nrow = len(mat)\n",
      "        if row < 0 or row >= nrow :\n",
      "            print \"row out of range\"\n",
      "            rmat = None\n",
      "        else :\n",
      "            rmat = []\n",
      "            for i in range(nrow) :\n",
      "                present_row = []\n",
      "                for j in range(ncol) :\n",
      "                    if i == row :\n",
      "                        present_row.append(mat[i][j] * a)\n",
      "                    else :\n",
      "                        present_row.append(mat[i][j])\n",
      "                rmat.append(present_row)\n",
      "    return rmat\n",
      "                "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def elem3(mat, r1, r2, a) :\n",
      "    nrows = len(mat)\n",
      "    if nrows < 2 :\n",
      "        print \"Not enough rows\"\n",
      "        rmat = None\n",
      "    else :\n",
      "        ncols = len(mat[0])\n",
      "        if ncols == 0 : \n",
      "            print \"Not enough cols\"\n",
      "            rmat = None\n",
      "        else :\n",
      "            if a == 0 :\n",
      "                print \"a cannot be zero.\"\n",
      "                rmat = None\n",
      "            else :\n",
      "                rmat = []\n",
      "                for i in range(nrows) :\n",
      "                    curr_row = []\n",
      "                    for j in range(ncols) :\n",
      "                        if i == r2 :\n",
      "                            curr_row.append(mat[r2][j] + mat[r1][j] * a)\n",
      "                        else :\n",
      "                            curr_row.append(mat[i][j])\n",
      "                    rmat.append(curr_row)\n",
      "    return rmat\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def print_matrix(mat, fmt='%3d') :\n",
      "    for i in range(len(mat)) :\n",
      "        for j in range(len(mat[0])) :\n",
      "            print fmt % mat[i][j],\n",
      "        print\n",
      "    return None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print_matrix(matrix, '%10.6f')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "  2.000000   8.000000   6.000000   0.000000\n",
        "  3.000000  12.000000   9.000000  10.000000\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def show_sweep(mat, pivot, fmt='%3d') :\n",
      "    r = pivot[0]\n",
      "    c = pivot[1]\n",
      "    nrow = len(mat)\n",
      "    if r < 0 or r >= nrow :\n",
      "        print \"r out of range.\"\n",
      "    else :\n",
      "        ncol = len(mat[0])\n",
      "        if c < 0 or c >= ncol :\n",
      "            print \"c out of range.\"\n",
      "        else :\n",
      "            print_matrix(mat, fmt)\n",
      "            a = 1.0 / mat[r][c]\n",
      "            print \"Multiplying row %d with %g\" % (r, a)\n",
      "            mat = elem2(mat, r, a)\n",
      "            print_matrix(mat, fmt)\n",
      "            for i in range(nrow) :\n",
      "                if i != r :\n",
      "                    a = mat[i][c]\n",
      "                    print \"Subtracting %g times row %d from row %d.\" % (a, r, i)\n",
      "                    mat = elem3(mat, r, i, -a)\n",
      "                    print_matrix(mat, fmt)\n",
      "            print \"The sweeping is done.\"\n",
      "    return None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "show_sweep(matrix, (0, 0), '%5.2f')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 2.00  8.00  6.00  0.00\n",
        " 3.00 12.00  9.00 10.00\n",
        "Multiplying row 0 with 0.5\n",
        " 1.00  4.00  3.00  0.00\n",
        " 3.00 12.00  9.00 10.00\n",
        "Subtracting 3 times row 0 from row 1.\n",
        " 1.00  4.00  3.00  0.00\n",
        " 0.00  0.00  0.00 10.00\n",
        "The sweeping is done.\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Problem 4"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def show_trapezoidal(f, a, b, steps=3) :\n",
      "    h = b-a\n",
      "    for i in range(steps) :\n",
      "        nparts = int(round((b-a)/h))\n",
      "        integral = 0\n",
      "        for k in range(nparts) :\n",
      "            area_trap = 0.5 * (f(a + k*h) + f(a + (k+1) * h)) * h\n",
      "            print \"Step %d : Area of %d-th trapezium = %g\" % (i+1, k, area_trap)\n",
      "            integral += area_trap\n",
      "        print \"Step %d : Total integral = %g\" % (i+1, integral)\n",
      "        h /= 2.0\n",
      "    return None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "show_trapezoidal(lambda x : x * (x - 1) * (x - 2) * (x - 3) * (x - 4), 0, 4)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Step 1 : Area of 0-th trapezium = 0\n",
        "Step 1 : Total integral = 0\n",
        "Step 2 : Area of 0-th trapezium = 0\n",
        "Step 2 : Area of 1-th trapezium = 0\n",
        "Step 2 : Total integral = 0\n",
        "Step 3 : Area of 0-th trapezium = 0\n",
        "Step 3 : Area of 1-th trapezium = 0\n",
        "Step 3 : Area of 2-th trapezium = 0\n",
        "Step 3 : Area of 3-th trapezium = 0\n",
        "Step 3 : Total integral = 0\n"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class PolySymbInt(Poly) :\n",
      "    def integrate(self) :\n",
      "        l = self.l\n",
      "        m = [0]\n",
      "        lenl = len(l)\n",
      "        for d in range(lenl) :\n",
      "            m.append(float(l[d])/float(d+1))\n",
      "        return Poly(m)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = PolySymbInt([0, 1])\n",
      "xm1 = PolySymbInt([-1, 1])\n",
      "xm2 = PolySymbInt([-2, 1])\n",
      "xm3 = PolySymbInt([-3, 1])\n",
      "xm4 = PolySymbInt([-4, 1])\n",
      "p = x * xm1 * xm2 * xm3 * xm4\n",
      "pp = PolySymbInt(p.l)\n",
      "print pp\n",
      "q = pp.integrate()\n",
      "print q\n",
      "print \"Symbolic integral =\", q(4) - q(0)\n",
      "print \"It should be zero.\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0 + 24 x + -50 x^2 + 35 x^3 + -10 x^4 + 1 x^5\n",
        "\n",
        "0 + 0.0 x + 12 x^2 + -16.6667 x^3 + 8.75 x^4 + -2 x^5 + 0.166667 x^6\n",
        "\n",
        "Symbolic integral = -1.13686837722e-13\n",
        "It should be zero.\n"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Problem 5a)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def clear_extra_space(s) :\n",
      "    s = s.strip()\n",
      "    news = \"\"\n",
      "    is_blank = False\n",
      "    for i in range(len(s)) :\n",
      "        if s[i] == ' ' and not is_blank :\n",
      "            is_blank = True\n",
      "            news += s[i]\n",
      "        elif s[i] != ' ' :\n",
      "            is_blank = False\n",
      "            news += s[i]\n",
      "    return news"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "clear_extra_space('        This          should be    Ok.     ')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "'This should be Ok.'"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Problem 5b)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def midno(n) :\n",
      "    if n != int(n) or n <= 0 :\n",
      "        print \"Need a positive integer.\"\n",
      "    else :\n",
      "        sn = str(n)\n",
      "        ln = len(sn)\n",
      "        if ln % 4 == 3 :\n",
      "            sn = ' ' + sn\n",
      "        elif ln % 4 == 2 :\n",
      "            sn = ' ' + sn + ' '\n",
      "        elif ln %4 == 1 :\n",
      "            sn = '  ' + sn + ' '\n",
      "        \n",
      "        newln = len(sn)\n",
      "        print newln, '\"' + sn + '\"'\n",
      "        blocklen = newln/4\n",
      "        midblock = sn[blocklen:3*blocklen]\n",
      "        midn = int(midblock)\n",
      "        return midn"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print midno(234332)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8 \" 234332 \"\n",
        "3433\n"
       ]
      }
     ],
     "prompt_number": 26
    }
   ],
   "metadata": {}
  }
 ]
}