MTH5001: Introduction to Computer Programming 2022/23

Late Summer Project: "Pattern Containment"

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 August 7, 23:55. 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%202

Your lecturers will respond to project-related emails until 5:00pm on August 4, 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 advice

(https://qmplus.qmul.ac.uk/pluginfile.php/3467941/mod_resource/content/1/School%20of%20Mathematical%20Sciences%20UG%20Student%20Handbook%202

in the student handbook,

Introduction to the Project

This project will deal with algorithms for testing pattern containment in 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 − 1) is a subsequence of the permutation π if 0 ≤ i0  < i1 < … < ik < n.

A permutation σ is said to be contained in another permutation π, if π has a subsequence whose terms have the same relative ordering as σ. We say the pattern σ is contained in π .

For example, (2, 0, 3, 4, 8, 1, 5, 6, 7) contains the pattern (0, 3, 1, 2) because the subsequence (3, 8, 5, 7) is ordered in the same way as (0, 3, 1, 2) .

A permutation π is said to avoid the pattern σ if σ is not contained in π .

For example, (2, 0, 3, 4, 8, 1, 5, 6, 7) avoids the pattern (2, 1, 0) as there are no decreasing subsequences of length three.

Some code to get you started

It is tempting to try to find code online to solve this problem. For example, asking ChatGPT to "write python code to check if a permutation contains a given permutation pattern" gives

def contains_permutation_pattern_ChatGPT(p, pattern):

n = len(p)

m = len(pattern)

if m > n:

return False

for i in range (n-m+1):

if all(p [i+j] < p [i+j+1] if pattern[j] < pattern[j+1] else p [i+j] > p [i+j+1] for j in range (m-1)):

return True

return False

(The code is verbatim from ChatGPT, we have only amended the function name.) The same code in a codebox:

In  [1]:

But how do we know that this is indeed correct? Let's test the examples above:

In  [2]:

print(contains_permutation_pattern_ChatGPT([2,0,3,4,8,1,5,6,7],[0,3,1,2]))

print(contains_permutation_pattern_ChatGPT([2,0,3,4,8,1,5,6,7],[2,1,0]))

True

False

So far so good. Below you will work on understanding this function in more detail and test if it really does what it it claims.

Plotting Permutations

An easy way to visualise permutations is to consider them as n points (i, πi ) on the [n]2 -grid. It is quite easy to spot patterns graphically: π contains σ if the plot of σ results from erasing zero or more points from the plot of π and then rescaling the axes appropriately.

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 the pattern (0, 1, 2, 3) shown in blue (there are three other occurrences of this pattern, can you find them?).

The structure of the Project

This project consists of 3 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.

The first part (worth 40 marks) asks you to explain given Python code, improve it, and analyse its complexity.

The second part (worth 30 marks) asks you to write code to properly test pattern-avoidance.

The third part (worth 30 marks) asks you to analyse large pattern-avoiding permutations.

The following code box is used to load any necessary modules.

You may not import any other modules.

In  [3]:

Part 1: Analysis and improvement of given code [40 marks total]