Objectives
The objectives of this assignment are:
- To gain experience in designing algorithms for a given problem description and implementing those algorithms in Python 3.
- To demonstrate the ability to:
- Implement algorithms for sorting in Python.
- Decompose code into functions in Python.
- Implement simple recursive algorithms in Python.
- Read from text files using Python.
- Manipulate lists using basic operations.
Submission Procedure
- Put you name and student ID in a comment at the start of each file in your solution.
- Save your files into a zip file called yourFirstName yourLastName.zip
- Submit your zip file containing your solution to Moodle.
- Your assignment will not be accepted unless it is a readable zip file.
Important Note
Please ensure that you have read and understood the college’s policies on plagiarism and collusion available. You will be required to agree to these policies when you submit your assignment.
Marks
This assignment has a total of 40 marks and contributes to 15% of your final mark. Late submission will have 5% off the total assignment marks per day (including weekends) deducted from your assignment mark.
In the case of this Assignment, this means that a late assignment will lose 2 marks for each day (including weekends). Assignments submitted 7 days after the due date will normally not be accepted.
Marking Criteria
Task 1
Part A
- (a) File read in correctly
- (b) Merge sort implemented correctly
- (c) Rankings printed correctly
- (d) Code is readable (including meaningful variable names and non-trivial comments on code)
- (e) Code is appropriately decomposed
Part B
- (a) File read in correctly
- (b) Merge sort implemented correctly
- (c) Rankings printed correctly
- (d) Code is readable (including meaningful variable names and non-trivial comments on code)
- (e) Code is appropriately decomposed
Task 2
- (a) File read in correctly
- (b) Maximum spanning tree found
- (c) Spanning tree printed correctly
- (d) Code is readable (including meaningful variable names and non-trivial comments on code)
- (e) Code is appropriately decomposed
Task 3
Part A
- (a) Recursive function(s) implemented correctly
- (b) Mathematical function(s) implemented correctly
- (c) Code is readable (including meaningful variable names and non-trivial comments on code)
- (d) Code is appropriately decomposed
Part B
- (a) Report conclusions and quality
Task 1
For this year’s Olympic games, as always, the ranking of the teams is given by the number of medals that they win in the various events. The number of medals that each team won is stored in a file with one team per line.
Each line contains a team’s name, followed by the number of gold, silver and bronze medals they won. The values on each line are separated by commas. An example of the format is shown below.
Canada (CAN),1,5,12
Indonesia (INA),0,1,1
Poland (POL),2,2,6
Part A
For this part, you are to write a Python program to sort the teams by the number of gold medals that they won. Perform this sort using Merge sort. The program should ask the user for a filename containing the medal tally and read the file in. It should then sort the teams by their number of gold medals and finally print the teams in their sorted order along with their rank. Note that multiple teams can have the same rank if they have the same number of medals. For example, given a file containing the above tally, the program could print:
Sorted according to the number of gold medals
1: Poland (POL)
2: Canada (CAN)
3: Indonesia (INA)
Part B
In this part, write a Python program similar to the one from Part A but sort by the total medal count instead. So instead of sorting by the number of gold medals that each team won, this time it should be sorted by the total number of medals (gold, silver and bronze) that the team won.
For this part, your program might print the following:
Sorted according to the total number of the medals
1: Canada (CAN)
1: Poland (POL)
2: Indonesia (INA)
Task 2
Previously in this unit, we have discussed finding minimum spanning trees using a variety of methods. In this task, we will be finding maximum spanning trees, that is spanning trees with the highest possible weight.
Create a Python program which finds a maximum spanning tree of a given graph. Your program will ask the user for a filename and read a graph, stored as an edge list, from that file. It will then compute a maximal spanning tree from that graph and print the edges in the tree along with its weight. For example: The file containing the following lines:
0 1 1
0 4 8
0 5 9
1 2 17
1 4 6
2 3 2
3 4 9
4 5 3
2 4 12
For example: If the file testGraph.txt contains the edges and weights of the graph (see figure 1), your program might do the following:
This is the edges of the spanning tree
[[0,5],[0,4],[4,2],[2,1],[4,3]]
The weight of the maximum spanning tree is: 55
Task 3
A combination is a way of selecting k elements from a set of n elements. The total number of ways of doing this.
Part A
For this task, you are to attempt to verify the correctness of this identity. Do this by implementing both the left-hand and right-hand sides of the equation as functions in Python.
Using these two functions, create a program which takes values for x and n and prints the result of both the left-hand and right-hand sides of the identity for those values.
Your program should include at least one non-trivial recursive function. You must not use the math package and must write your own function to compute.
Part B
Using your program from Part A, compare the results for both functions for a variety of values of both x and n. Choose at least 10 combinations of values and present your results in a table. Include this table in a short report (about 2 paragraphs) and discuss whether your results indicate that the identity is true.