Objectives

The objectives of this assignment are:
- To gain experience in designing algorithms for a given problem description and implementing those algo- rithms 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.

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) - 1 marks (e)Code is appropriately decomposed

Task 2:

(a) File read in correctly - 2 marks (b)Maximum spanning tree found - 3 marks (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 - 3 marks (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:

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 for a given n ≥ 0 and k ∈ [0, n] is denoted (ⁿ_k). The value of (ⁿ_k) can be calculated using (1) below where n! is the factorial of n.

(ⁿ_k) = n!/((n - k)!k!)

The following identity involving a sum of a number of combinations allows for it to be calculated more simply:

Σⁿ_k=0(ⁿ_k)x^k/k=1 = ((x +1)ⁿ⁺¹ -1)/x(n +1)

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 (ⁿ_k).

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.