\n",
"\n",
"**IMPORTANT**: \n",
"Start by filling in your 9 digit *student ID number* below. **DO IT NOW**. \n",
" \n",
"Save this Jupyter Notebook with the name **MTH5001_ID.ipynb**, where instead of **ID** you write your *student ID number*.\n",
"\n",
"Please check very carefully that your *student ID number* is accurately typed everywhere. Otherwise your marks might go to the wrong person.\n",
"\n",
"Use the available cells to introduce the code. You can add additional cells if needed. explain your code as much as possible with `# comments`

"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"### ID: please replace the text after the colon by your 9 digit student ID number\n",
"\n",
"

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "### Instructions:\n", "\n", "You must write your answers in this Jupyter Notebook, using either Markdown or Python code as appropriate. \n", "\n", "Your code must be **well documented**. As a rough guide, you should aim to include one line of comments for each line of code (but you may include more or fewer comments depending on the situation).\n", "\n", "The total number of marks available is 100. Attempt all parts of all questions.\n", "\n", "For this project, you are expected to write your code almost entirely 'from scratch', although you are allowed to use some specific packages like `numpy`, `matplotlib.pyplot`, etc.\n", "\n", "### Submission deadline:\n", "\n", "You must submit your work via QMPlus, to the \"Final Report Project\" assignment in the \"Final Report Project\" section under the \"Assessment\" tab.\n", "\n", "The submission deadline is **11:55pm on Thursday 4th of May, 2023**. *(May the 4th be with you!)* Late submissions will be penalised according to the School's [guidelines](https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202022_23.pdf).\n", "\n", "Your lecturers will respond to project-related emails until 5:00pm on Tuesday 2 May, 2022, only. You should aim to have your project finished by this time.\n", "\n", "### Marking of projects:\n", "\n", "When writing up projects, good writing style is even more important than in written exams. According to the [advice](https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202022_23.pdf) in the student handbook,\n", "\n", "> To get full marks in any assessed work (tests or exams) you must normally not only give the right answers but also explain your working clearly and give reasons for your answers by writing legible and grammatically correct English sentences. Mathematics is about logic and reasoned arguments and the only way to present a reasoned and logical argument is by writing about it clearly. Your writing may include numbers and other mathematical symbols, but they are not enough on their own. You should copy the writing style used in good mathematical textbooks, such as those recommended for your modules. **You can expect to lose marks for poor writing (incorrect grammar and spelling) as well as for poor mathematics (incorrect or unclear logic).**\n", "\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "### Instructions:\n", "\n", "You must write your answers in this Jupyter Notebook, using either Markdown or Python code as appropriate. \n", "\n", "Your code must be **well documented**. As a rough guide, you should aim to include one line of comments for each line of code (but you may include more or fewer comments depending on the situation).\n", "\n", "The total number of marks available is 100. Attempt all parts of all questions.\n", "\n", "For this project, you are expected to write your code almost entirely 'from scratch', although you are allowed to use some specific packages like `numpy`, `matplotlib.pyplot`, etc.\n", "\n", "### Submission deadline:\n", "\n", "You must submit your work via QMPlus, to the \"Final Report Project\" assignment in the \"Final Report Project\" section under the \"Assessment\" tab.\n", "\n", "The submission deadline is **11:55pm on Thursday 4th of May, 2023**. *(May the 4th be with you!)* Late submissions will be penalised according to the School's [guidelines](https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202022_23.pdf).\n", "\n", "Your lecturers will respond to project-related emails until 5:00pm on Tuesday 2 May, 2022, only. You should aim to have your project finished by this time.\n", "\n", "### Marking of projects:\n", "\n", "When writing up projects, good writing style is even more important than in written exams. According to the [advice](https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202022_23.pdf) in the student handbook,\n", "\n", "> To get full marks in any assessed work (tests or exams) you must normally not only give the right answers but also explain your working clearly and give reasons for your answers by writing legible and grammatically correct English sentences. Mathematics is about logic and reasoned arguments and the only way to present a reasoned and logical argument is by writing about it clearly. Your writing may include numbers and other mathematical symbols, but they are not enough on their own. You should copy the writing style used in good mathematical textbooks, such as those recommended for your modules. **You can expect to lose marks for poor writing (incorrect grammar and spelling) as well as for poor mathematics (incorrect or unclear logic).**\n", "\n", "

\n",
" \n",
"### Plagiarism warning:\n",
"\n",
"Your work will be tested for plagiarism, which is an assessment offence, according to the [School's policy on Plagiarism](https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202022_23.pdf). In particular, while only academic staff will make a judgement on whether plagiarism has occurred in a piece of work, we will use the plagiarism detection software \"Turnitin\" to help us assess how much of work matches other sources. You will have the opportunity to upload your work, see the Turnitin result, and edit your work once accordingly before finalising your submission.\n",
"\n",
"\n",
"However, you must use your own words as far as possible (within reason, e.g. you would not be expected to change the wording of a well-known theorem), and you **must** [reference](https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202022_23.pdf) any sources that you use. You cannot communicate with other students on any part of the project. You should also note that some of the questions are personalised in the sense that you will need to import and manipulate data that will be unique to you (i.e. no other student will have the same data).\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"### Introduction to the Project\n",
"\n",
"Longest increasing subsequences appear in many areas across mathematics, computer science, and physics.\n",
"This project will deal with algorithms for creating longest increasing subsequences of permutations of a set of $n$ numbers, their graphical representation, and some analysis of their structure with computational and graphical means.\n",
"\n",
"As Python indexing starts with zero, we will also start counting at zero and hence give the mathematical description in terms of the set of numbers $[n]=\\{0,1,\\ldots,n-1\\}$. \n",
"\n",
"For a given $n\\in\\mathbb N$, let $\\pi=(\\pi_0,\\pi_1,\\ldots,\\pi_{n-1})$ be a **permutation** of $[n]$, i.e., one of the $n!$ possible orderings of $[n]$.\n",
"\n",
"A sequence $(\\pi_{i_0},\\pi_{i_1},\\ldots,\\pi_{i_{k-1}})$ is a **subsequence** of the permutation $\\pi$ if $0\\leq i_0k$.\n",
"\n",
"For example, the increasing subsequences of the permutation $(0,2,1)$ are $()$, $(0)$, $(2)$, $(1)$, $(0,2)$, and $(0,1)$. Clearly $(0,2)$ and $(0,1)$ are longest, so the length of the longest increasing subsequence of $(0,2,1)$ is $2$. This example shows also that the longest increasing subsequence is not necessarily unique. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"### Some code to get you started\n",
"\n",
"It is very easy to find code online to solve this problem. For example, the following function finds a longest increasing subsequence in a sequence of numbers:\n",
"```python\n",
"def find_length_of_longest_increasing_subsequence(pi):\n",
" n=len(pi) \n",
" l=n*[0]\n",
" for i in range(n):\n",
" for j in range(i):\n",
" if pi[j]l[i]:\n",
" l[i]=l[j]\n",
" l[i]=l[i]+1\n",
" return max(l+[0])\n",
"```\n",
"The same code in a codebox:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"def find_length_of_longest_increasing_subsequence(pi):\n",
" n=len(pi) \n",
" l=n*[0]\n",
" for i in range(n):\n",
" for j in range(i):\n",
" if pi[j]l[i]:\n",
" l[i]=l[j]\n",
" l[i]=l[i]+1\n",
" return max(l+[0])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Applied to the example $(0,2,1)$ above we indeed get the right result."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 2, 1] 2\n"
]
}
],
"source": [
"pi=[0,2,1]\n",
"print(pi,find_length_of_longest_increasing_subsequence(pi))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Three obvious cases to check are:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[] 0\n",
"[0, 1, 2, 3, 4, 5] 6\n",
"[5, 4, 3, 2, 1, 0] 1\n"
]
}
],
"source": [
"pi=[]\n",
"print(pi,find_length_of_longest_increasing_subsequence(pi))\n",
"pi=list(range(6))\n",
"print(pi,find_length_of_longest_increasing_subsequence(pi))\n",
"pi=pi[::-1]\n",
"print(pi,find_length_of_longest_increasing_subsequence(pi))"
]
},
{
"attachments": {
"image-3.png": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAOcAAADnCAYAAADl9EEgAAAHU0lEQVR4nO3cO29Udx7G8WeMkeIMW6Eo7tbvwMWuXUduAbuARBFI8B7gdcB7AIncE8lcyqC0MVD4JaRLtFv6goQvW2QVYWLGM8dz+c2Zz0eiGR8mfxR9OZ745EkAAAAAAJi8Tq8vXr58+XhpaWlcZ5k929vJwcHw3m9+PlleHt77MRavX7/+b5JP3n99vtdvWlpayqtXr0Z2qJnX6fl34+AODhL/vqZOp9P57bTX58Z9EKA/4oSixAlFiROKEicUJU4oSpxQlDihKHFCUeKEosQJRYkTihInFCVOKEqcUJQ4oShxQlHihKLEOUmfflr7/ZionhtCjNjvv0/6BBTmzkn/Fhf/HCUb1q/FxUn/iUoTJ/3744/a79cy4oSixAlFiZNzO07ya1bzeb5NNzuZy2G62ckX+SZbWcnxpA84pcTJubzNfG7mcdbyc37K9eylm+PMZS/d/JgbWcuL3MzjvPWDgYGJk8aOk9zOwzzJRvZyKUe5cOLrR7mQ3VzKZjZyOw/dQQckThrbymqeZj176fa8bj/dPM16XmZlTCdrB3HS2P3czX4W+rp2Pwu5n7sjPlG7iJPGnufq376V/ZCjXMjzXB3xidpFnDTW712z6fWzTpw0tpD9kV4/68RJY1fyLHM57OvauRzmSp6N+ETtIk4au5cHfd8NP8qb3MuDEZ+oXcRJY6vZyrU8yUJ2e163kN2sZzMreTmmk7WDOGmsk+RR7mQjm389tveuuRzm4+xmI5t5lDvpTOaYU0ucnMvFHOSr3MqLrOV6fjjxbO2NfJ9f8lm+zq1czMGkjzp1PPDIuXWSrOZlvsuXkz5Kq7hzQlHihKLESf+sBY6Vz5z0z1rgWLlztpGVvFYQZxtZyWsFcUJR4oSixDlDrORNF3HOCCt500ecM8BK3nQS5wywkjedxDkDrORNJ3HOACt500mcM8BK3nQS5wywkjedxDkDrORNJ3HOACt500mcM8BK3nQS5wywkjedxDkjrORNHw9SzhAredPFnROKEicUJc42spLXCj5ztpGVvFZo153T6hwt0q44rc7RIu2KE1pEnFCUOKEocUJR4oSixAlFiROKEicUJU4oSpxQlDihKHFCUeKEosQJRYkTihInFCVOKEqcUFS74rQ6R4u0a33P6hwt0q47J4zDkFcel5Pl0/4x4oRBDXmVcf4D38GKE4oSJxQlTihKnFCUOKEocUJR4oSixAlFiROKEicUJU4oSpxQlDihKHFCUeKEosQJRYkTihInFCVOGNSQVxkPkoPTXm/X+h6Mw5BXHrc7ne3TXnfn7MeQ19ayuDjpPxFTQJz9GPLa2tDfj1YSJxQlTihKnOdwnOTXrObzfJtudjKXw3Szky/yTbaykuNJH5CpJs6G3mY+N/M4a/k5P+V69tLNceayl25+zI2s5UVu5nHe+g/iNCTOBo6T3M7DPMlG9nIpR7lw4utHuZDdXMpmNnI7D91BaUScDWxlNU+znr10e163n26eZj0vszKmk9Em4mzgfu5mPwt9XbufhdzP3RGfiDYSZwPPc/Vv38p+yFEu5HmujvhEtJE4G+j3rtn0ekjE2chC9kd6PSTibORKnmUuh31dO5fDXMmzEZ+INhJnA/fyoO+74Ud5k3t5MOIT0UbibGA1W7mWJ1nIbs/rFrKb9WxmJS/HdDLaRJwNdJI8yp1sZPOvx/beNZfDfJzdbGQzj3InnckckyknzoYu5iBf5VZeZC3X88OJZ2tv5Pv8ks/ydW7l4un/kzucyYOf59BJspqX+S5fTvootJA7JxQlTihKnP0Y8tra0N+PVvKZsx9DXluDfvS+c25vW52DCekd58GQfwxgdQ765jMnFCVOKKpRnFbnYPR6Pvb5r+T41Xuvvc38/8et1vMmCycWAeZymIXs51qe5FHunP7o2rF04V2dTud1kn+///pAd06rczA+A8VpdQ7GZ6A4rc7B+Az0mbObnTPvmu/qZic7+cfJF33mhBOG8pnT6hyMz0BxWp2D8RkoTqtzMD4DxWl1DsZnoDitzsH4DBSn1TkYn4GfrbU6B+Mx8LO15+bnnHDCUH7OCYyPOKGo3nHOD3n/y+oc9K13nMvLf35GHNYvK3bQN9/WMnmLi1YeTyFOJm/Yq4wtWXkUJxQlTihKnFCUOKEocUJR4oSixAlFiROKEicUJU4oSpxQlDihKHFCUeKEosQJRYkTihInFCVOKEqcTN6wVxlbsvI45O1LaMAq46kmc+e0tgZnmkyc1tbgTD5zQlHihKLECUWJE4oSJxQlTihKnFCUOKEocUJR4oSixAlFiROKEicUJU4oSpxQlDihKHFCUeKEoiYTp7U1ONNk1vesrcGZfFtLe035yqM4aa8pX3kUJxQlTihKnFCUOKEocUJR4oSixAlFiROKEicUJU4oSpxQlDihKHFCUeKEosQJRYkTihInFCVOKKpzxtf/k+S3cRwEhm05WZ4f4ojdQXKwnWwP6/3e8c8kn4zgfQEAAAAAOLf/AUmm0nXyrtprAAAAAElFTkSuQmCC"
}
},
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"### Plotting Permutations\n",
"\n",
"An easy way to visualise permutations is to consider them as $n$ points $(i,\\pi_i)$ on the $[n]^2$-grid. For example, the permutation $(3,1,6,4,9,7,8,2,0,5)$ is represented by the following picture, with the permutation shown in red and a longest increasing subsequence shown in blue (there are three others, can you find them?).\n",
"![image-3.png](attachment:image-3.png)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"### The structure of the Project\n",
"\n",
"This project consists of **4 parts**. In each of the parts you will need to code up some specific functions, run some code, and respond to some questions. Recall that all code needs to be properly documented with `# comments`, and the explanations in these comments will indeed be assessed and you will receive lots of marks for adequate documentation. \n",
"\n",
"\n",
"\n",
"* The **first part** (worth 35 marks) asks you to explain given Python code to compute longest increasing subsequences and analyse its complexity.\n",
"\n",
"* The **second part** (worth 30 marks) asks you to write code to find all longest increasing subsequences.\n",
"\n",
"* The **third part** (worth 20 marks) asks you to analyse longest increasing subsequences for one specifically given permutation.\n",
"\n",
"* The **fourth part** (worth 15 marks) asks you to modify your code for a slight variation on the problem.\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following code box is used to load any necessary modules. \n",
"\n",
"**You may not import any other modules, except for the `project` module, which we introduce in Part 3.**"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"#DO NOT CHANGE THE CONTENT OF THIS CODE BOX\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"from timeit import timeit\n",
"from itertools import permutations"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"# Part 1: Analysis of given code [35 marks total]\n",
"\n",
"***\n",
"\n",
"

\n",
" \n",
"Please remember to write plenty of `# comments` in the code cells. Mark scheme is depicted in each question. 50% of the marks will go to assess the actual code, and 50% of the marks will go to assess the `# comments`. Remember also to **reference** any sources you used. If you used any code or coding ideas you found elsewhere, you are encouraged to do that in the `# comments`.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[1.1] [10 marks]** Explain in detail how the function `find_length_of_longest_increasing_subsequence` works. More specifically:\n",
"- Which data types would be accepted by the function for the argument `pi`?\n",
"- What does the function return? What data type is it?\n",
"- Explain the purpose of the variable `l`.\n",
"- Explain what precisely is being computed in the nested loop involving the parameters `i` and `j`. What is the meaning of `pi[j]\n",
" \n",
"Please remember to write plenty of `# comments` in the code cells. Mark scheme is depicted in each question. 50% of the marks will go to assess the actual code, and 50% of the marks will go to assess the `# comments`. Remember also to **reference** any sources you used. If you used any code or coding ideas you found elsewhere, you are encouraged to do that in the `# comments`.\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[2.1] [15 marks]** The code in Part 1 only gives the length of the longest increasing subsequence for a given permutation. Moreover, we have seen above that the largest increasing subsequence need not be unique.\n",
"\n",
"By using the existing code for `find_length_of_longest_increasing_subsequence(pi)`, **and not otherwise**, write a function `find_all_longest_increasing_subsequences(pi)` that gives out all of them for a given `pi`.\n",
"\n",
"The output should be in the form of a list of lists, i.e. `[sequence1, sequence2, ...]`, where each entry is a longest increasing subsequence.\n",
"\n",
"Test this function on `[]`, `[0,2,1]`, `[0,1,2,3,4,5]`, `[5,4,3,2,1]`, and `\"computer\"`.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**Note:** if you could not complete Q2.1 and write a working function `find_all_longest_increasing_subsequences`, you are allowed to use other code you found to work on subsequent questions, provided you provide a complete reference."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[2.2] [10 marks]** Among permutations of fixed size, there are many with several longest increasing subsequences. Find all permutations $\\pi$ of length $10$ with the largest number of different longest increasing subsequences. How many permutations $\\pi$ have you found, and how many different longest increasing subsequences do they each have? Print each of these permutations along with their longest increasing subsequences.\n",
"\n",
"You are allowed to use generate permutations using `itertools.permutation` (imported above) as follows.\n",
"```python\n",
"perms=permutations(range(10))\n",
"for p in perms:\n",
" ...\n",
" ...\n",
"```\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[2.3] [5 marks]** As you should now have seen, there are many different questions one could ask about the properties of longest increasing subsequences. We shall finish this part by looking at \"typical\" lengths for large random permutations.\n",
"\n",
"Generate $10000$ random permutations of size $100$, compute the lengths of their longest increasing subsequences and display them in a suitable histogram, making sure that each bin corresponds precisely to one single length.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"# Part 3: Visualising longest increasing subsequences [20 marks total]\n",
"*** ***\n",
"\n",
"

\n",
" \n",
"Please remember to write plenty of `# comments` in the code cells. Mark scheme is depicted in each question. 50% of the marks will go to assess the actual code, and 50% of the marks will go to assess the `# comments`. Remember also to **reference** any sources you used. If you used any code or coding ideas you found elsewhere, you are encouraged to do that in the `# comments`.\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You have been provided with a Python file called **\"project.py\"** on QMPlus, which you should **save in the same directory as this Jupyter notebook**.\n",
"This file contains a function `create_permutation()` which creates a permutation for you, based on your student id. (This will look random, but will be unique to you, i.e. no two students will have the same permutation to work with.) In this section, you will analyse this permutation."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**[3.1] [5 marks]** Execute the following code cell to create your permutation. You **must** replace the number \"123456789\" with your 9-digit student number. \n",
"\n",
"*Important note.* This question essentially gives you 5 free marks for typing your student ID correctly. If you do not do this correctly, you will score zero for this part, and if you instead use another student's ID, then your submission will be reviewed for plagiarism."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"from project import create_permutation\n",
"\n",
"# Replace \"123456789\" below with your 9-digit student number\n",
"\n",
"my_permutation=create_permutation(123456789)\n",
"\n",
"# Replace \"123456789\" above with your 9-digit student number"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[3.2] [5 marks]** As described in the introduction above, a permutation $\\pi$ can be visualised using the points $(i,\\pi_i)$. Plot your permutation (choosing an appropriate marker size!), and describe what you see. How large is your permutation?\n",
"\n",
"---\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[3.3] [5 marks]** How long is the longest increasing subsequence? How many are there?\n",
"\n",
"You will notice that it might take a minute or two to compute all those subsequences. Be patient...\n",
"\n",
"---\n",
"**Note:** if you could not complete Q2.1 and write a working function `find_all_longest_increasing_subsequences`, you are allowed to use other code you found, provided you provide a complete reference.\n",
"\n",
"---\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[3.4] [5 marks]** Now that you have found all longest increasing subsequences, display these together with the permutation in a figure. What do you notice?\n",
"\n",
"---\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"# Part 4: Longest Increasing Shifted Subsequences [15 marks total]\n",
"*** ***\n",
"\n",
"

\n",
" \n",
"Please remember to write plenty of `# comments` in the code cells. Mark scheme is depicted in each question. 50% of the marks will go to assess the actual code, and 50% of the marks will go to assess the `# comments`. Remember also to **reference** any sources you used. If you used any code or coding ideas you found elsewhere, you are encouraged to do that in the `# comments`.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We conclude with a modification of our original problem. For any $n\\in\\mathbb{N}$, let $\\tau_n$ be the permutation of $[n]$ given by\n",
"\n",
"$$\\tau_n=(1,\\,2,\\,\\ldots,\\,n-1,\\,0) \\;. $$\n",
"\n",
"Right-multiplying a permutation by $\\tau_n$ has the effect of shifting the elements left by one place (with the first element being cycled back around to the end). For example, if we have $n=5$, then\n",
"\n",
"$$(2,\\,4,\\,3,\\,1,\\,0)\\cdot\\tau_5=(4,\\,3,\\,1,\\,0,\\,2)\\;.$$\n",
"\n",
"Let $\\pi$ be a permutation of length $n$. We call a sequence a **longest increasing shifted subsequence (LISS)** of $\\pi$ if it is a longest increasing subsequence of all permutations of the form $\\pi\\cdot\\tau_n^m$, where $m\\in\\mathbb{N}$. Clearly after shifting $n$ times we have come full circle, so $\\pi\\cdot\\tau_n^n=\\pi$.\n",
"\n",
"Returning to the example above, we see that $(0,\\,2,\\,4)$ is a LISS of the permutation $(2,\\,4,\\,3,\\,1,\\,0)$, since it is a longest increasing subsequence of $(2,\\,4,\\,3,\\,1,\\,0)\\cdot\\tau_5^2$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[4.1] [5 marks]** Let `pi` be a permutation of $[n]$, for some $n\\in\\mathbb{N}$, written in the form of a Python list. Write a function `find_all_LISSes` that accepts such an input `pi`, and returns a list of every LISS of this permutation.\n",
"\n",
"Once this is done, use this function to compute the LISSes of the permutation `[2,4,3,1,0]`, and compare these with its longest increasing subsequences.\n",
"\n",
"**Hint:** Your function may use the function `find_all_longest_increasing_subsequences` that has already been defined above. There is no need to re-write this code."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**Note:** if you could not complete Q2.1 and write a working function `find_all_longest_increasing_subsequences`, you are allowed to use other code you found, provided you provide a complete reference.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You should find that the length of the LISSes of `[2,4,3,1,0]` is three, while the length of the longest increasing subsequences of `[2,4,3,1,0]` is only two. It should be clear from the definition that the length of the LISSes of a permutation will always be longer than the length of its longest increasing subsequences.\n",
"\n",
"Note however, that we if we were to evaluate the LISSes of `[4,3,1,0,2]`, we would get identical results. This is because the LISSes of a permutation are invariant under shifts. The same is not true for longest increasing subsequences, which vary each time the permutation is shifted. Indeed, if we left-shift twice, the set of LISSes and longest increasing subsequences would now coincide.\n",
"\n",
"This means that if we were to consider the ratio of the length of the LISSes with the length of the longest increasing subsequences, we would have reduced it from $1.5$ to $1$. This brings us to our next question."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"**[4.2] [5 marks]** Take the permutation `my_permutation` that you constructed in Q3.1, and determine how many places you must shift by in order to minimise the length of the longest increasing subsequence.\n",
"\n",
"Once this is done, perform this shift, and label the result `shifted_permutation`.\n",
"\n",
"Note that `shifted_permutation` will have a maximal ratio between the length of its LISSes to the length of its longest increasing subsequences.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"**[4.3] [5 marks]** Replot the figure from Q3.4 with this new shifted permutation. Your plot should now highlight the LISSes of your permutation, rather than the longest increasing subsequences. Explain how the behaviour of the LISSes differs from the behaviour of the longest increasing subsequences.\n",
"\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
}
],
"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.9.7"
}
},
"nbformat": 4,
"nbformat_minor": 2
}