labs/quiz-complexity.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice quiz: complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. What is the T(n) for the following loop as a recurrence relation (i.e., no Sigma)? (Write answer as \"T(n)=...\")\n",
    "\n",
    "```\n",
    "a = 100\n",
    "for i in range(n):\n",
    "    a -= i\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "T(n)=1+T(n-1)\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. What is the T(n) for the following loop as a recurrence relation (i.e., no Sigma)? (Write answer as \"T(n)=...\")\n",
    "\n",
    "```\n",
    "a = 100\n",
    "for i in range(0,n,10):\n",
    "    a -= i\n",
    "```   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "T(n)=1+T(n-10) \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. Give a closed form for time recurrence equation T(n) = k + T(n-2) with T(1)=0, T(0)=0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "T(n) = k + T(n-2)\n",
    "T(n) = k + k + T(n-4)\n",
    "T(n) = k + k + k + T(n-6)  # we can turn crank n/2 times\n",
    "T(n) = kn/2\n",
    "</pre>\n",
    "\n",
    "Remember we don't drop constants until asymptotic behavior\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. Give a closed form for time recurrence equation T(n) = 1 + T(n/2) + T(n/2) with T(1)=1, T(0)=1\n",
    "\n",
    "Hint: I had to turn crank a few times and simplify the equation. Note: $2^0+2^1+..+2^k = 2^{k+1}-1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "T(n) = 1 + T(n/2) + T(n/2)\n",
    "T(n) = 1 + 2T(n/2)\n",
    "T(n) = 1 + 2(1 + 2T(n/4))\n",
    "T(n) = 1 + 2(1 + 2(1 + 2T(n/8))\n",
    "T(n) = 1 + 2(1 + 2(1 + 2(1 + 2T(n/16))) # can do this log2(n) times\n",
    "T(n) = 1 + 2 + 4(1 + 2(1 + 2T(n/16)))\n",
    "T(n) = 1 + 2 + 4 + 8(1 + 2T(n/16))\n",
    "T(n) = 1 + 2 + 4 + 8 + 16T(n/16)\n",
    "T(n) = sum 2^i from i=0 to log2(n)\n",
    "T(n) = 2^(log2(n+1)) - 1\n",
    "T(n) = 2*2^log2(n) - 1\n",
    "T(n) = 2*n - 1\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. What is the T(n) for the following loop in main program (not the function)?\n",
    "\n",
    "```python\n",
    "def f(m):\n",
    "    for i in range(m):\n",
    "        print(\"hi\") # assume constant time, k, for this operation\n",
    "\n",
    "for i in range(n):\n",
    "    f(i)\n",
    "```\n",
    "\n",
    "Recall $\\sum_{i=1}^n i = n(n+1) / 2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "T(n)=$\\sum_{i=1}^n \\sum_{j=1}^i k$<br>\n",
    "T(n)=$\\sum_{i=1}^n ki$<br>\n",
    "T(n)=$\\frac{k n(n+1)}{2}$<br>\n",
    "T(n)=$\\frac{k(n^2+n)}{2}$<br>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. What is the O(...) derived from $T(n)=k(n^2-n)/4$ for constant $k$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "$n^2$   \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. Given a list of first names of size $n$ and a list of last names of size $m$, what's the maximum amount of work required to find all possible combinations of first and last names. Order matters so: first names go first, last name next. You are counting the number of string concatenations such as \"Xue\"+\"Smith\".  Given the \"T(n,m) = ...\" formula in closed form not the O(...)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "$T(n,m)=nm$. There's a couple ways to look at this but the simplest is to look at the work product: the list of first-last name combinations. There are at most $nm$ of these combinations and so we get $T(n,m) = nm$. A brute force approach using a nested loop over the first names and the inner loop over the last names would also give you a complexity of $nm$ because we would get a nested sigma for $T(n,m)$ and solving for closed form would give you just $nm$.    \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q**. Given a directed, cyclic graph with $n$ nodes but without edge labels, you would like to execute function f() on each node.  Function f() takes time $n/2$.  Imagine an algorithm that (avoiding cycles) walks the graph and is not deliberately performing redundant f() calls.  We are counting just cost of applying f(), not edge traversals. What's the maximum amount of work required to execute f() for each node in closed form T(n) notation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "$T(n)=n*n/2$. Given that we want the program to halt eventually, we have to avoid cycles, which we can do by simply marking each node has visited after we execute f() on each node. This implies we can only execute f() once for each node and there are $n$ nodes.  The cost of executing each f() is $n/2$ so the overall cost is $T(n) = n*n/2$.</details>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}