Assessed Standard Task 2/5: Find method for Binary Tree class Standard

Data Structures 1, Slides 115 to 119, create 2 binary search methods, one iterative and one recursive, and implement these into the python Binary Tree class given on Aula in the zip folder, ‘BST-class’.

Call the iterative method find_i, and the recursive method find_r. Notice that find_r needs a sub-method. Call this _find_r.

Each method should return True, False, or None (note that the solution for ‘None’ is not given in the iterative pseudocode).

Check your code works by calling it and returning the correct result.

You may decide, if you wish, to implement the entire class and solutions in C++, instead of, or in addition to, the python solution, but this is not mandatory for this task.

Using the given code on Aula, in the zip folder ADJACENCY-MATRIX, use python to implement an unweighted and undirected graph data structure as an adjacency matrix, where the vertices consist of positive integers (note that 0 is not a positive integer). The program should have methods for the following:

1. Adding a vertex to the graph.
2. Adding an edge to the graph.

This should check whether the edge already exists

1. Removing an edge from the graph.

Checking that there is an edge to remove

1. Printing the graph as a matrix.

Which should look something like this:

1   2   3   4   5   6

———————

1 |   0   1   1   0   0   0

2 |   1   0   1   0   0   0

3 |   1   1   0   1   0   0

4 |   0   0   1   0   0   0

5 |   0   0   0   0   0   0

6 |   0   0   0   0   0   0

(continues over)

IMPORTANT:

• The code as given may need altering to allow the new methods to be introduced.
• Edges can be removed with no need to worry about vertices.

NOTE: If you wish, you could implement the entire code as C++ instead of, or in addition to, python. This is not mandatory for this task.

• Assessed Standard Task 4:Implement Prim’s Algorithm Standard

Using the code given on Aula in the folder PRIMS-STD-TASK-4, complete the code to produce the following output for the given graph:

Edge  Weight

0 – 1  2

1 – 2  3

0 – 3  6

1 – 4  5

Note that this is an advanced algorithm, so to simplify the task for standard level, we have provided full comments throughout to aid understanding. This means that if you select this task as one of the 3 standard tasks to write up, you need provide no further comments (altho’ you might provide docstrings). You will of course need to give an explanation as well as critical comment.

Assessed Standard Task 5: Implement an Insert Method for a Linked List Standard

• You will need to have studied the lecture Data Structures 2, on Aula, Slides 52 to 83.

Use the code in the folder on Aula called LINKED-LIST-STD-TASK-5.The code currently outputs the following:

Mon

Tue

Thur

Fri

Sat

Sun

So we need to add ‘Weds’.

To do this, create an insert method. Here is some code to get you started. You’ll need to add code after the else:

def Insert(self,val_before,newdata):

if val_before is None:

print(“No node to insert after”)

return

else: