{
"cells": [
{
"cell_type": "markdown",
"id": "47669dce",
"metadata": {},
"source": [
"## PDSP Assignment 5\n",
"### 8 November 2022, due 14 November 2022\n",
"\n",
"Run the following experiments and report your results. \n",
"\n",
"1. Run selection sort on `K` random lists of size `N` and compute\n",
" the mean and standard deviation. Repeat this `M` times, so\n",
" you should report `M` pairs of the form `(mean_run_time, std_deviation)`.\n",
"\n",
"1. Run (iterative) insertion sort on `K` random lists of size `N`\n",
" and compute the mean and standard deviation. Repeat this `M`\n",
" times, so you should report `M` pairs of the form\n",
" `(mean_run_time, std_deviation)`.\n",
" \n",
"1. Implement a variant of mergesort that switches to (iterative)\n",
" insertion sort when the list length is less than than `cutoff`.\n",
" Run this hybrid merge-iteration sort on `K` random lists of size `N`\n",
" and compute the mean and standard deviation. Repeat this `M`\n",
" times, so you should report `M` pairs of the form\n",
" `(mean_run_time, std_deviation)`. Try this for different values of\n",
" `cutoff` below `100`, including `cutoff = 0`.\n",
"\t\n",
"1. Implement a variant of quicksort that switches to (iterative)\n",
" insertion sort when the list length is less than than `cutoff`.\n",
" Run this hybrid quick-iteration sort on `K` random lists of size `N`\n",
" and compute the mean and standard deviation. Repeat this `M`\n",
" times, so you should report `M` pairs of the form\n",
" `(mean_run_time, std_deviation)`. Try this for different values of\n",
" `cutoff` below `100`, including `cutoff = 0`.\n",
"\t\n",
"\n",
"### Instructions\n",
"\n",
"1. Submit your final code as a single Python notebook extending these instructions. However, you can run individual experiments separately before combining them into a single notebook.\n",
"\n",
"1. The assignment is open ended in terms of choosing `K`, `N` and\n",
"`M` for all questions and the number of different values of\n",
"`cutoff` in the last two questions. However:\n",
"\n",
"\t- `K` should be at least `100`\n",
" - `N` should be at least `5000` for the first two questions\n",
" and at least `50000` for the last two questions\n",
" - `M` should be at least `5`.\n",
"\t- For the last two questions, use at least `5` values of\n",
" `cutoff`, other than `cutoff = 0`. If the performance\n",
" improves for any value of `cutoff > 0`, try to find an\n",
" optimum value for `cutoff`.\n",
"\n",
"1. Use the same random lists for the first two questions.\n",
" Similarly use the same random lists for the last two questions.\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.7.13"
}
},
"nbformat": 4,
"nbformat_minor": 5
}