midterm_review.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>.prompt{width: 0px; min-width: 0px; visibility: collapse}</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<style>\n",
       "div#notebook {\n",
       " font-family: \"Exo_2\", sans-serif;\n",
       "}\n",
       "\n",
       ".rendered_html h1,\n",
       ".text_cell_render h1 {\n",
       " color: #126dce;\n",
       " font-size: 220%;\n",
       " text-align: center;\n",
       " font-weight: lighter;\n",
       "}\n",
       ".rendered_html h2,\n",
       ".text_cell_render h2 {\n",
       " text-align: center;\n",
       " font-size: 170%;\n",
       " color: #126dce;\n",
       " font-style: normal;\n",
       " font-weight: lighter;\n",
       "}\n",
       ".rendered_html h3,\n",
       ".text_cell_render h3 {\n",
       " font-size: 150%;\n",
       " color: #126dce;\n",
       " font-weight: lighter;\n",
       " text-decoration: italic;\n",
       " font-style: normal;\n",
       "}\n",
       ".rendered_html h4,\n",
       ".text_cell_render h4 {\n",
       " font-size: 120%;\n",
       " color: #126dce;\n",
       " font-weight: underline;\n",
       " font-style: normal;\n",
       "}\n",
       ".rendered_html h5,\n",
       ".text_cell_render h5 {\n",
       " font-size: 100%;\n",
       " color: #2f2f2f;\n",
       " font-weight: lighter;\n",
       " text-decoration: underline;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# setup\n",
    "from IPython.core.display import display,HTML\n",
    "display(HTML('<style>.prompt{width: 0px; min-width: 0px; visibility: collapse}</style>'))\n",
    "display(HTML(open('rise.css').read()))\n",
    "\n",
    "# imports\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "%matplotlib inline\n",
    "sns.set(style=\"whitegrid\", font_scale=1.5, rc={'figure.figsize':(12, 6)})\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# CMPS 2200\n",
    "## Mid-term Review \n",
    "\n",
    "> Part I: 10:00AM-11:00AM - March 6.\n",
    "\n",
    "> Part II: 8:00AM-9:25AM - March 7\n",
    "\n",
    "\n",
    "> Office Hours: ST 402A\n",
    "<br>\n",
    "    - Me: 2PM-4PM - March 4\n",
    "<br>\n",
    "    - Zach: 3PM-5PM - March 5 not March 7\n",
    "\n",
    "\n",
    "You are allowed to use any relevant class materials (book, lectures, notes, etc.). You are not to use any other source of information, or to communicate with anyone about this exam (either portion) other than the instructors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Good Algorithm [efficient - runs quickly, requires little memory]\n",
    "> input size $n$<br>\n",
    "\n",
    "- Algorithm Comparison [**Worse Case**, Asymptotic Dominance] \n",
    "  - Upper Bound: $\\mathcal{O}(\\cdot)$, Lower Bound: $\\Omega(\\cdot)$, Tight Bound: $\\Theta(\\cdot)$, \n",
    "  - Limit Method, e.g., $\\lim_{n=∞}\\frac{n^c}{(n-1)^{c}}=1$\n",
    "\n",
    "- **Exampe**-[Assignment 1]\n",
    " \n",
    "  - 1a. Is $2^{n+1} \\in O(2^n)$? Why or why not? \n",
    " \n",
    "  - 1b. Is $2^{2^n} \\in O(2^n)$? Why or why not?     \n",
    "\n",
    "  - 1c. Is $n^{1.01} \\in O(\\mathrm{log}^2 n)$?    \n",
    "\n",
    "  - 1d. Is $n^{1.01} \\in \\Omega(\\mathrm{log}^2 n)$?  \n",
    " \n",
    "  - 1e. Is $\\sqrt{n} \\in O((\\mathrm{log} n)^3)$?  \n",
    "\n",
    "  - 1f. Is $\\sqrt{n} \\in \\Omega((\\mathrm{log} n)^3)$?  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "- **Parallelism:** ability to run multiple computations at the same time. Then what is the bottleneck?\n",
    "<br><br>\n",
    "- **Speedup**: To solve a same task, a parellel algorithm $P$ over a sequential algorithms $S$ is: \n",
    "$$\n",
    "\\mathrm{speedup}(P,S) = \\frac{T(S)}{T(P)}\n",
    "$$\n",
    "\n",
    "\n",
    "<br><br>\n",
    "- **Work $T_1$ \\& Span $T_\\infty$**\n",
    "  - **Work**: total energy consumed by a computation; \n",
    "  - **Span**: minimum possible time that the computation requires\n",
    "  - When only $p$ processors are available $T_p <\\mathcal{O}(\\frac{T_1}{p}+T_\\infty)$ [when applying the Greedy Scheduler]\n",
    "  \n",
    "\n",
    "<br><br>\n",
    "- **Amdahl's Law**: \n",
    "$$\\frac{T_1}{T_p} = \\frac{1}{S + \\frac{1 − S}{p}}$$\n",
    "where $S$ be the amount of time that cannot be parallelized.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "- Funtional Language [SPARC] \n",
    "  - Pure function -> no side effects [**benign effects**]\n",
    "  - High Order Function (function as variable) -> e.g., we pass mapping and reduce functions to a higher order one\n",
    "<br><br>\n",
    "- Language based Work-Span model \n",
    "  - $(e_1,~e_2)$ [**Add work and span**]\n",
    "  - $(e_1~||~e_2)$ [Add work but **take the maximum span**]\n",
    "> For a given expression $e$ [a series of statements], we will analyze the work $W(e)$ and span $S(e)$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### **Reccursive Algorithms**\n",
    "  - Recurrences are useful because they help us characterize the running time of recursive algorithms.\n",
    "  - **Tree Method \\& Brick Method**\n",
    "  - General Formulation: $$W(n) = \\alpha W(\\dfrac{n}{\\beta}) + f_w(n) \\Rightarrow S(n) = S(\\dfrac{n}{\\beta}) + f_s(n)$$ \n",
    "\n",
    "- **Take Work as an example**:\n",
    "\n",
    "> Step 1. What is the **input size** per node at level $i$? \n",
    "\n",
    "$$\\frac{n}{\\beta^i}$$\n",
    "\n",
    ">Step 2. What is the **cost** of each node at level $i$? \n",
    "\n",
    "$$f_w(\\frac{n}{\\beta^i})$$\n",
    "\n",
    ">Step 3. How many nodes are there at level $i$? \n",
    "\n",
    "$$\\alpha^i$$\n",
    "\n",
    "\n",
    ">Step 4. What is the total cost across the level $i$? <span style=\"color:blue\">$\\Rightarrow$ This step is used for Brick Method.</span>\n",
    "\n",
    "$$\\alpha^i\\big(f_w(\\frac{n}{\\beta^i})\\big)$$\n",
    "\n",
    ">Step 5. How many levels are there in the tree [**Tree Height/Depth**]? <span style=\"color:blue\">Note that Span is positively correlated with Tree Depth.</span>\n",
    "\n",
    "$$\\frac{n}{\\beta^i} = 1 \\Rightarrow {i = \\log_{\\beta}n}$$\n",
    "\n",
    " \n",
    "\n",
    ">Step 6. What is the total cost? \n",
    "\n",
    "$$\\sum_{i=0}^{\\log_{\\beta}n}\\alpha^i\\big(f_w(\\frac{n}{\\beta^i})\\big)$$\n",
    "\n",
    "\n",
    "<span style=\"color:green\"> Note that the leave level has $\\alpha^{\\log_\\beta n}$ nodes, or equivalently, $n^{\\log_\\beta \\alpha}$.</span>\n",
    "\n",
    "<br><br>\n",
    "<span style=\"color:red\">**Question**:</span> What is the geometric property? What is the base case?\n",
    "\n",
    "$ W(n) = 3 W(n/2) + n \\Rightarrow$ Leaf dominated, $O(n^{\\log_23})$, where base case $n=1$.\n",
    "\n",
    "> Root: n, Level 1: 3*(n/2) = 1.5n, it is leaf dominated. The depth is $\\log_2n$, the number of leaves is $3^{\\log_2n}$, which is $O(n^{\\log_23})$.\n",
    "\n",
    "$ W(n) = 2 W(n/3) + n \\Rightarrow$ Root dominated, $O(n)$, where base case $n=1$.\n",
    "\n",
    "$ W(n) = 3 W(n/3) + n \\Rightarrow$ Balanced , $O(n\\log_3n)$, where base case $n=1$.\n",
    "\n",
    "$ W(n)=2W(n/3)+1 \\Rightarrow$ Leaf dominated, $O(n^{\\log_32})$, where base case $n=1$.\n",
    "\n",
    "$ W(n)=W(\\sqrt{n})+1 \\Rightarrow$ Balanced, $O(\\log\\log{n})$, where base case $n=2$.\n",
    "\n",
    "> Root: n, Level 1: 1, it is balanced. The node size at level $i$ is $n^\\frac{1}{2^i}$ and the base case is 2 (must be larger than 1), so that the depth is $\\log_2\\log_2n$.\n",
    "\n",
    "\n",
    "\n",
    "$W(n)=W(n-1)+2 \\Rightarrow$ Balanced, $O(n)$, where base case $n=1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Assignment 2 \n",
    "Q2. Suppose that for a given task you are choosing between the following three algorithms:\n",
    "\n",
    "> Algorithm $\\mathcal{A}$ solves problems by dividing them into\n",
    "      five subproblems of half the size, recursively solving each\n",
    "      subproblem, and then combining the solutions in linear time.\n",
    "\t  \n",
    "      \n",
    "$W(n) = 5 W(n/2) + n$\n",
    "\n",
    "root is $n$\n",
    "\n",
    "level 1 is $5/2 n$\n",
    "\n",
    "geomtric growth\n",
    "\n",
    "number of leaves is $5^{\\log_2 n} \\in O(n^{\\log_2 5}) \\approx O(n^{2.32})$\n",
    "      \n",
    "> Algorithm $\\mathcal{B}$ solves problems of size $n$ by\n",
    "      recursively solving two subproblems of size $n-1$ and then\n",
    "      combining the solutions in constant time.\n",
    "      \n",
    "$W(n) = 2 W (n-1) + 1$\n",
    "\n",
    "root : 1\n",
    "\n",
    "level 1 : 2\n",
    "\n",
    "level 2 : 4\n",
    "\n",
    "geometric growth\n",
    "\n",
    "height is $n$. number of leaves is $2^n \\in O(2^n)$\n",
    "\n",
    "> Algorithm $\\mathcal{C}$ solves problems of size $n$ by dividing\n",
    "      them into nine subproblems of size $n/3$, recursively solving\n",
    "      each subproblem, and then combining the solutions in $O(n^2)$\n",
    "      time.\n",
    "      \n",
    "$W(n) = 9 W (n/3) + n^2$\n",
    "\n",
    "root : $n^2$\n",
    "\n",
    "level 1 : $n^2$\n",
    "\n",
    "balanced\n",
    "\n",
    "$\\Rightarrow O(n^2 log_3 n)$\n",
    "\n",
    "> What are the asymptotic running times of each of these algorithms?\n",
    "    Which algorithm would you choose?\n",
    "\n",
    "compare $O(n^2 \\lg n)$ vs $O(n^{\\log_2 5})$\n",
    "\n",
    "$ n^2 \\lg n =? \\: n^{\\lg 5}$\n",
    "\n",
    "$ n^{\\lg 4} \\lg n =? \\: n^{\\lg (4 \\cdot \\frac{5}{4})}$\n",
    "\n",
    "$ n^{\\lg 4} \\lg n =? \\: n^{\\lg 4 +  \\lg \\frac{5}{4}}$\n",
    "\n",
    "$ n^{\\lg 4} \\lg n =? \\: n^{\\lg 4} n^{\\lg \\frac{5}{4}}$\n",
    "\n",
    "$ \\lg n =? \\: n^{\\lg \\frac{5}{4}}$\n",
    "\n",
    "$ \\lg n <  \\: n^{0.322...}$\n",
    "\n",
    "Therefore choose $O(n^2 log_3 n)$ (Algorithm $\\mathcal{C}$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Sequence\n",
    "- iterate: $W(n) = O(n), S(n) = O(n)$\n",
    "- reduce: $W(n) = O(n), S(n) = O(\\log n)$\n",
    "- scan [fast version]: $W(n) = O(n), S(n) = O(\\log n)$\n",
    "\n",
    "\n",
    "Note that the three arguements of each function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<span style=\"color:red\">**Question**:</span> Compute the frequency per unique char\n",
    " - Lab 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\n",
    "### Reduction/Brute-Force Algorithms/Search Space\n",
    "\n",
    "<span style=\"color:red\">Reduction:</span> A problem $A$ is reducible to a problem $B$ if any instance of problem $A$ can be turned into some instance of $B$.\n",
    "\n",
    "If $A$ is reducible to $B$ then: (1) $A$ is not harder than $B$; (2) $B$ is at least as hard as $A$\n",
    "\n",
    "\n",
    "- <span style=\"color:blue\">Lower Bound and Upper Bound</span>\n",
    "  - $A$ is reducible to $B$, $B$ is reducible to $C$.\n",
    "\n",
    "<br><br>\n",
    "<span style=\"color:red\">Brute Force</span> paradigm just for a problem $A$ and an instance $\\mathcal{I}_A$, just looks at every possible solution and checks each one.\n",
    "\n",
    "\n",
    "<span style=\"color:green\">Question:</span> Consider the problem of finding the minimal element in a list $L$ of length $n$, what is the search space for this problem and what is the work/span of the brute-force algorithm?\n",
    "\n",
    "<span style=\"color:blue\">Solution:</span> \n",
    "- **Using `iterate`**: work $O(n)$; span $O(n)$\n",
    "- **Using `reduce`**: work $O(n)$; span $O(\\log n)$\n",
    "- **Brute-force**: work $O(n^2)$; span $O(\\log n)$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "### Divide-and-Conquer \\& Contraction\n",
    "- Prove the correctness: <span style=\"color:red\">Induction</span>\n",
    "- Deduct Work and Span\n",
    "\n",
    "The general form of the work is:\n",
    "\n",
    "$$ W(n) = W_{\\mathsf{\\small divide}}(n) + \\sum_{i=1}^{k}W(n_i) + W_{\\mathsf{\\small combine}}(n) + 1 $$\n",
    "\n",
    "The general form for the span is:\n",
    "\n",
    "$$ S(n) = S_{\\mathsf{\\small divide}}(n) + \\max_{i=1}^{k}S(n_i) + S_{\\mathsf{\\small combine}}(n) + 1 $$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#### Divide-and-Conquer\n",
    "\n",
    "For a problem $A$ and instance $\\mathcal{I}_A$:\n",
    "\n",
    "- **Base Case**: If $\\mathcal{I}_A$ is small, solve directly. \n",
    "\n",
    "- **Inductive Step**: \n",
    "    - **Divide** $\\mathcal{I}_A$ into smaller instances.\n",
    "    - **Recursively solve** smaller instances.\n",
    "    - **Combine** solutions\n",
    "\n",
    "#### Contraction\n",
    "A contraction algorithm for problem $A$ has the following structure.\n",
    "\n",
    "- **Base Case**: If the problem instance is sufficiently small, then compute and return the solution, possibly using another algorithm.\n",
    "\n",
    "- **Inductive Step(s)**: If the problem instance is sufficiently large, then \n",
    "  - Apply the following two steps, as many times as needed:\n",
    "\n",
    "    - ``Contract``: map the instance of the problem $A$ to a smaller instance of $A$.\n",
    "    - ``Solve``: solve the smaller instance recursively.\n",
    "\n",
    "  - Expand the solutions to smaller instance to solve the original instance."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.11.0"
  },
  "rise": {
   "autolaunch": true,
   "controls": false,
   "enable_chalkboard": true,
   "scroll": true,
   "theme": "simple",
   "transition": "fade"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}