week-8-class.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ignore\n",
    "from IPython.display import Image"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1. Write pseudocode for a parallel version of merge sort using a serial merge step. Compute the span and parallelism of your code. How useful is this code?\n",
    "\n",
    "You may assume that the work is unchanged, $O(n\\log n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2. Write pseudocode for a parallel merge step, using the hints below. Compute its span.\n",
    "\n",
    "If you're merging L and R, find the midpoint value x of L, and divide L and R into halves which are less than or greater than x. Use an efficient (serial) algorithm to find the midpoint of R. Find an upper bound of the span of the two spawned merge steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"parallel-merge-hint.png\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Image(url=\"parallel-merge-hint.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "You may want to use the following variant of the master method:\n",
    "\n",
    "If $T(n)=aT(n/b)+f(n)$ and $f(n)=\\Theta(n^{\\log_b a}(\\log n)^k)$ then $T(n)=\\Theta(n^{\\log_b a}(\\log n)^{k+1})$.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q3. Write pseudocode for a fully parallel merge sort, and compute its span and parallelism. How useful is this code?\n",
    "\n",
    "You may again assume the work is $O(n\\log n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q4 (optional). Write code to implement this and verify that it works.\n",
    "\n",
    "You don't need to actually use multiple processors, just verify that the code works."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.11.0 ('dmclass')",
   "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"
  },
  "vscode": {
   "interpreter": {
    "hash": "6a49734ee071ffa0c8c241132785defaa79e59e5d82f90ac60edfabf8372010d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}