wk9/MY470_wk9_class.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### MY470 Computer Programming\n",
    "# Order of Growth\n",
    "### Week 9 Lab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![Big-O Comparison](figs/big-o-table.png \"Big-O Comparison\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Runtime: Benchmarking\n",
    "\n",
    "Use `time` module:\n",
    "\n",
    "1. Save time immediately before code\n",
    "2. Save time immediately after code\n",
    "3. Estimate 2 – 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0008790493011474609\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "ls = list(range(100000))\n",
    "\n",
    "start = time.time()\n",
    "ls.count(99999)\n",
    "end = time.time()\n",
    "print(end - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Benchmarking: Repeat to Time More Accurately\n",
    "\n",
    "* Execution time can be affected by other processes running simultaneously\n",
    "* Execution time can depend on the order of execution (randomize execution order)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0008678531646728516\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.0008166161800181726"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Do it yourself\n",
    "ls = list(range(100000))\n",
    "\n",
    "res = 0\n",
    "for i in range(100):\n",
    "    start = time.time()\n",
    "    ls.count(99999)\n",
    "    end = time.time()\n",
    "    res += end - start\n",
    "print(res / 100)\n",
    "\n",
    "# Use a module\n",
    "from timeit import timeit \n",
    "timeit(stmt='ls.count(99999)', setup='ls = list(range(100000))', number=100) / 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "### R code ###\n",
    "\n",
    "require(microbenchmark)\n",
    "\n",
    "ls <- seq(0, 99999)\n",
    "microbenchmark(sum(ls == 99999))\n",
    "\n",
    "# Unit: microseconds\n",
    "#             expr     min      lq     mean  median       uq      max neval\n",
    "# sum(ls == 99999) 368.309 416.865 684.3047 559.569 706.2215 3955.864   100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Runtime: Order of Growth\n",
    "\n",
    "* Consider the worst-case scenario\n",
    "* Look at:\n",
    "    * Function and method calls \n",
    "    * Recursive calls\n",
    "    * Loops\n",
    "* Keep the term with the largest growth rate\n",
    "* Drop any constants from the remaining term"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Exercise 1**: The following functions show the average number of operations required to perform some algorithm on a list of length $n$. Give the Big-O notation for the time complexity of each algorithm:\n",
    "\n",
    "a) $4n^2 + 2n + 2$\n",
    "\n",
    "b) $n + \\log n$\n",
    "\n",
    "c) $n \\log n$\n",
    "\n",
    "d) 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Exercise 2: Give the order of growth for the function \n",
    "# and explain your reasoning in a couple of sentences.\n",
    "\n",
    "def sum_product(ls):\n",
    "    summ, product = 0, 1\n",
    "    for i in range(len(ls)):\n",
    "        summ += ls[i]\n",
    "    for j in range(len(ls)):\n",
    "        product *= ls[j]\n",
    "    return summ, product   \n",
    "\n",
    "# Your answer: \n",
    "#\n",
    "#\n",
    "#\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true,
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# Exercise 3: Give the order of growth for the function \n",
    "# and explain your reasoning in a couple of sentences.\n",
    "\n",
    "def combine(la, lb):\n",
    "    for i in la:\n",
    "        for j in lb:\n",
    "            if i < j:\n",
    "                print(i, '-', j)\n",
    "\n",
    "# Your answer: \n",
    "#\n",
    "#\n",
    "#\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# Exercise 4: Give the order of growth for the function \n",
    "# and explain your reasoning in a couple of sentences.\n",
    "\n",
    "def sum_digits(n):\n",
    "    \"\"\"Take positive integer n and sum its digits.\"\"\"\n",
    "    summ = 0\n",
    "    while n > 0:\n",
    "        summ += int(n % 10)\n",
    "        n = int(n / 10)\n",
    "    return summ\n",
    "\n",
    "# Your answer: \n",
    "#\n",
    "#\n",
    "#\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 5: Give the order of growth for the code \n",
    "# and explain your reasoning in a couple of sentences.\n",
    "\n",
    "a = 0;\n",
    "for i in range(x):\n",
    "    for j in reversed(range(i, x)):\n",
    "        a = a + i + j\n",
    "        \n",
    "# Your answer: \n",
    "#\n",
    "#\n",
    "#\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 6: Give the order of growth for the function \n",
    "# and explain your reasoning in a couple of sentences.\n",
    "\n",
    "def factorial(n):\n",
    "    \"\"\"Takes non-negative integer n and returns the factorial n!,\n",
    "    where n! = n * (n-1) * (n-2) ... * 2 * 1\n",
    "    \"\"\"\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial(n-1)\n",
    "        \n",
    "# Your answer: \n",
    "#\n",
    "#\n",
    "#\n",
    "#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Exercise 7: This is code submitted by a student for Problem 2 \n",
    "# in Problem Set 1. Given an edge list of coauthors in data, \n",
    "# the task was to create a sorted list of all unique authors. \n",
    "# What is the order of growth of this code? What is wrong here? \n",
    "# How would you rewrite the code to make it more efficient?\n",
    "\n",
    "lst = [] \n",
    "for i,j in data:\n",
    "    lst.append(int(i)) \n",
    "    unique_authors = list(set(lst))\n",
    "    unique_authors.sort()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Exercise 8: Compare the execution time for loops \n",
    "# between R and Python using Exercise 4.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# Exercise 9: Create a function to multiply each element of a \n",
    "# vector `v` by a scalar `m` in R with and without a for-loop\n",
    "# and compare their execution time.\n",
    "\n",
    "### R code ###\n",
    "multiply <- function (v, m) {\n",
    "  # Write with a for-loop\n",
    "}\n",
    "\n",
    "multiply2 <- function(v, m) {\n",
    "  # Write without a for-loop\n",
    "}\n",
    " "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}