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