STOR-601 Introductory Python - Assessment
Contents
16. STOR-601 Introductory Python - Assessment#
16.1. Overview#
This is the assessment for the STOR-601 Introductory Python Module.
The submission date for this assessment is 05/02/2024. Your submission should be in the form of a jupyter notebook made available for download via your github account. Please send details of your github repository to daniel grose by 09:00 on the submission date. Alternatively, send me an invite via github - my github name is grosed.
The assessment is marked out of 100 and the scores assigned to each task are indicated in the task descriptions.
A number of discretionary marks (10) have been reserved for rewarding the quality of your work. You can gain these marks by, for example, providing additional markup in your notebook to support your solutions to the tasks, using appropriate charts and tables to summarise your data, providing links to external references, providing simple tests for your functions, and so on. You may also choose to use additional material in support of your notebook, for example, files containing python source code. If this is the case, these materials must also be available from your github repository. Some of the discretionary marks might also be awarded for examples of particularly “pythonesque” code. To get an idea of what this means try executing
import this
in a code cell.
Please feel free to you use and extend any of the examples from the course notes and use resources available online where appropriate. However, it is important that your solution to Task 7 is your own work and reflects your own judgements as how to best implement the “fundamental algorithm” in python.
Before your results and feedback are returned you might be asked to have a short (approximately 5 minutes) individual online “interview” to discuss some aspects of your work. The outcome of this interview might impact on your overall individual score.
16.2. Task 1#
Read Lecture 1 of Stable Marriage and Its Relation to Other Combinatorial Problems up to and including the fifth paragraph on page 4.
For n men and n women, provide an upperbound for the maximum number of stable matchings ?
Marks [2]
16.3. Task 2#
Given the definitions on page 1 of Stable Marriage and Its Relation to Other Combinatorial Problems consider the computatinal problem -
IS_STABLE - Given a pair of preference tables and a matching determine if the matching is stable.
16.3.1. Part a)#
Write a python program that solves the computational problem IS_STABLE.
16.3.2. Part b)#
Describe any data structures that you chose to use in part b) and justify your choice.
16.3.3. Part c)#
Given n women (men) what is the computational complexity of your solution to part b) ?
Note - If you are unsure about how to determine the computational complexity of an algorithm/program using asymptotic analysis read Cormen et al sections 3.1 and 3.2.
Marks [10]
16.4. Task 3#
Given the definitions on page 1 of Stable Marriage and Its Relation to Other Combinatorial Problems consider the computational problem -
STABLE_MATCHINGS - Given a pair of preference tables find all stable matchings
16.4.1. Part a)#
Write a python program that solves the computational problem STABLE__MATCHINGS.
16.4.2. Part b)#
Describe any data structures that you chose to use in part b) and justify your choice.
16.4.3. Part c)#
Given n women (men) what is the computational complexity of your solution to part b) ?
Marks [15]
16.5. Task 4#
Write a python function which takes two lists of distinct and mutually disjoint symbols (of the same length) and which produces a pair of random preference tables as output.
You may find the following code example useful.
import random
random.sample(range(1,10),6)
Marks [5]
16.6. Task 5#
Provide some supporting material that might improve the Replicability your solutions to Task 2 and Task 3. You might want to look at this short presentation , particular the section on the 5Rs.
Marks [10]
16.7. Task 6#
Use your solutions to Task 4 to determine how the execution time of your implementations of IS_STABLE and STABLE_MATCHINGS varies with the size of the preference table. Is this relationship consistent with your expectations ? Justify your reasoning with reference to your implementation of the algorithm and your experimental observations.
You may find the following code example useful.
import time
start = time.perf_counter()
for i in range(1000000) :
x = 2
end = time.perf_counter()
print(end-start)
Marks [5]
16.8. Task 7#
Read lecture 2 of Stable Marriage and Its Relation to Other Combinatorial Problems up to and including the fourth paragraph on page 12.
16.8.1. Part a)#
Explain how you could include the “very undesirable” imaginary man introduced on page 9 into your representation of the preference tables.
16.8.2. Part b)#
Implement the fundamental algorithm described on page 9 as a Python function. Your function should take a (compatible) pair of preference tables as input and produce a (stable) matching as an output.
16.8.3. Part c)#
Analyse your implementation of the fundamental algorithm with respect to computational complexity making reference to how you employ your chosen python data structures.
Marks [23]
16.9. Task 8#
Some colleagues wish to use your python code to study a problem that involves solving the Stable Marriage Problem. They represent their preference tables using pandas data frames. Here is how they represent the male preference table from page 1 of Stable Marriage and Its Relation to Other Combinatorial Problems
import pandas as pd
H_preference_table = pd.DataFrame({"Anatole" : ["cunegonde","brigitte","donatienne","antoinette"],
"Barnabe" : ["brigitte","antoinette","cunegonde","donatienne"],
"Camille" : ["brigitte","donatienne","antoinette","cunegonde"],
"Dominique" : ["cunegonde","antoinette","donatienne","brigitte"]
})
They also represent matchings using pandas data frames. Here is the way the represent the stable solution given on page 2 of Stable Marriage and Its Relation to Other Combinatorial Problems
matching = pd.DataFrame({"Men" : ["Anatole","Barnabe","Camille","Dominique"],
"Women" : ["donatienne","antoinette","brigitte","cunegonde"]
})
Implement a function which accepts a pair of compatible preference tables and returns a matching using pandas data frames such as those shown above.
Marks [10]
16.10. Task 9#
Describe how you might use your solution to Task 4 to create some tests for your python code. Provide some further functions that could be used for testing your code and indicate how they should be used. Which of the 5Rs are improved by adding these tests ?
Marks [10]
16.11. Task 10#
Discretionary marks awarded for the overall quality of your code, solutions, reporting and insights, along with any techniques, methods and materials which support the concept of the 5 Rs and particularly “pythonesque” code.
Marks [10]