{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MA934 - Week 7 (assessed!) Problem Sheet\n",
    "\n",
    "## Deadline: 17:00 (UK time) on Friday 24 November \n",
    "\n",
    "For this assignment, you must create a new Jupyter notebook called MA934_Week7_UniID.ipynb to contain the implementations that you write. This should also be exported as a .pdf file such that all execution output (from data to plots) is visible as produced on your own machine. You can separate out individual tasks if you prefer, but the full submission should be made as a single .zip via [our website](/fac/sci/mathsys/courses/msc/ma934/resources/assessedwork/ma934declaration). The platform will not allow you to upload more than one file.\n",
    "\n",
    "A few tips:\n",
    "- please make sure to debug intermediate outputs as you code along. You are welcome to design smaller test cases and toy problems to verify your work (even if they are not part of the final submission).\n",
    "- consider possible forms of input or arguments and make sure your solution can cope with *interesting* cases.\n",
    "- do not forget to comment your code and use Markdown cells to explain what you are doing. A perfectly functional solution with no information about the thought process will not receive more than a subset of the points (~$70\\%$ depending on the difficulty of the problem and how transparent the algorithm flow is). \n",
    "- generally getting used to writing tidy solutions is good practice. Feel free to use [online resources](https://www.ibm.com/docs/en/watson-studio-local/1.2.3?topic=notebooks-markdown-jupyter-cheatsheet) for editing guidance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1 - insertion sort [20 marks]\n",
    "\n",
    "Add an implementation of the insertion sort algorithm to your solution. Check that it works by sorting some manageably small lists of random integers. The command ```random.sample(range(1, 200), 10)``` (after having imported the random module) creates a list of 10 random intergers in the range $1 - 200$ which you can use for more elaborate testing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2 - mergesort [20 marks]\n",
    "\n",
    "Consider two lists of integers, list1 and list2, having lengths $n$ and $m$, respectively. Assuming that the elements of list1 and list2 are already sorted in ascending order, the following recursive function merges them to return an array of length $n+m$ whose elements are sorted in ascending order:\n",
    "\n",
    "```Python\n",
    "    def interlace(list1, list2):\n",
    "    alist = []\n",
    "    if (len(list1) == 0):\n",
    "        return list2\n",
    "    elif (len(list2) == 0):\n",
    "        return list1\n",
    "    elif list1[0] < list2[0]:\n",
    "        alist.append(list1[0])\n",
    "        return alist + interlace(list1[1:], list2)\n",
    "    else:\n",
    "        alist.append(list2[0])\n",
    "        return alist + interlace(list1, list2[1:])\n",
    "```\n",
    "\n",
    "You have seen this function before (recall MA934_Week1_3_SortingAlgorithms.ipynb). Add it to your code, test it, and use it to implement the mergesort algorithm. Check that it works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 3 - fixing mergesort [25 marks]\n",
    "\n",
    "You will probably find that your mergesort algorithm fails for moderately large array lengths (on my laptop, I could not viably process lists of length $2^{16}$ for example, but this is just a guide). The reason for this is that there are too many recursions: the code quickly exceeds the maximum allowed recursion depth. \n",
    "\n",
    "To fix this, write a non-recursive implementation of the ```interlace()``` function. Test your ```mergesort()``` function using the non-recursive version. How does it compare to the previous solution in terms of achievable list length?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 4 - runtime [25 marks]\n",
    "\n",
    "Measure the runtime of your insertion sort and mergesort functions for random arrays of integers in the range $2$ to $2^{20}$. Save your results to a file.\n",
    "\n",
    "This is the potentially complicated part of this task. Here are some pointers:\n",
    "- recall we have touched upon the topic of runtime measurement and benchmarking when discussing matrix-matrix multiplication. \n",
    "- especially for small datasets, running your code multiple times and averaging the runtime may prove useful.\n",
    "- this part of the worksheet will involve handling file operations; finding the key read/write functionality and getting accustomed to working with the documentation is an intentional part of the process, one that you should become more and more comfortable with."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 5 - empirical analysis of computational complexity [10 marks]\n",
    "\n",
    "Load your runtime results back from the file and plot them on a log-log scale. Fit your data to determine how the computational cost scales with the length of the input array for large array sizes. How does this compare to theoretical expectations (which you should state and briefly justify)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}