MTH5001: Introduction to Computer Programming 2022/23
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MTH5001: Introduction to Computer Programming 2022/23
Final Report Project: "Longest Increasing Subsequences"
|
IMPORTANT: Start by filling in your 9 digit student ID number below. DO IT NOW. Save this Jupyter Notebook with the name MTH5001_ID.ipynb , where instead of ID you write your student ID number. Please check very carefully that your student ID number is accurately typed everywhere. Otherwise your marks might go to the wrong person. Use the available cells to introduce the code. You can add additional cells if needed. explain your code as much as possible with # comments |
|
ID: please replace the text after the colon by your 9 digit student ID number |
Instructions:
You must write your answers in this Jupyter Notebook, using either Markdown or Python code as appropriate.
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) .
The total number of marks available is 100. Attempt all parts of all questions.
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.
Submission deadline:
You must submit your work via QMPlus, to the "Final Report Project" assignment in the "Final Report Project" section under the "Assessment" tab.
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 (
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.
Marking of projects:
When writing up projects, good writing style is even more important than in written exams. According to the
in the student handbook,
|
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). |
Plagiarism warning:
Your work will be tested for plagiarism, which is an assessment offence, according to the School's policy on Plagiarism
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.
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
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) .
Introduction to the Project
Longest increasing subsequences appear in many areas across mathematics, computer science, and physics. 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.
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, … , n − 1}.
For a given n ∈ N , let 几 = (几0 , 几1 , … , 几n−1 ) be a permutation of [n], i.e., one of the n! possible orderings of [n].
A sequence (几i0, 几i 1, … , 几ik− 
is a subsequence of the permutation 几 if 0 ≤ i0 < i1 < … < ik < n .
A subsequence of the permutation 几 is increasing if 几i0 < 几i 1 < … < 几ik−1.
An increasing subsequence of the permutation 几 is longest if there is no other increasing subsequence with k′ > k.
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.
Some code to get you started
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:
def find_length_of_longest_increasing_subsequence(pi):
n= len(pi)
l=n*[0]
for i in range(n):
for j in range(i):
if pi[j]
l[i]= l[j]
l[i]= l[i]+1
return max(l+[0])
The same code in a codebox:
In [1]:
|
def find_length_of_longest_increasing_subsequence(pi): n= len(pi) l=n*[0] for i in range(n): for j in range(i): if pi[j]<pi[i] and l[j]>l[i]: l[i]= l[j] l[i]= l[i]+1 return max(l+[0]) |
Applied to the example (0, 2, 1) above we indeed get the right result.
In [2]:
[0, 2, 1] 2
Three obvious cases to check are:
In [3]:
|
pi= [] print(pi,find_length_of_longest_increasing_subsequence(pi)) pi= list(range(6)) print(pi,find_length_of_longest_increasing_subsequence(pi)) pi=pi[::- 1] print(pi,find_length_of_longest_increasing_subsequence(pi)) |
[] 0
[0, 1, 2, 3, 4, 5] 6
[5, 4, 3, 2, 1, 0] 1
|
Plotting Permutations An easy way to visualise permutations is to consider them as n points (i, 几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 |
2023-05-02
Longest Increasing Subsequences