Administration

Submission is done electronically via Tabula, and two files are expectedfor submission:

1. A PDF of your solutions named Answers.pdf.

2. A file named Practical.py of your python solution for the parts of Question 9.

The solutions submitted must be your own work. You are expected to work individually, not in groups.  Please show full working where appropriate, detailing how you have arrived at your answer.

Questions

Question 1 (10 points)

For each function f(n) and time t in the following table, determine the largest size n (an integer) of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds. You are free to use Python as a tool to work out answers.

Remember to explain your work progress, not just write down the answers.

Note: you can assume there are 30 days in a month and 365 days in a year.

Question 2 (10 points)

Determine whether the following complexity statements are true or false. For each answer, explain your reasoning according to the formal definition of O, Ω and Θ .

(a) 9n2 + 9 in O(n2 )

(b) 6n4 − 3n2 + 3 in Ω(n4 )

(c) 9n3 − 7n in O(n4 )

(d) n4 + 2n2 + 1 in Θ(n2 )

(e) n2 + 6n + 143 in Ω(n)

Question 3 (10 points)

Where possible, apply the master theorem for the following. If not possible, state the reason why.

(a) T() + 5

(b)  7T() + 47n

(c)  2nT() + n

(d)  16T() + 16n2

(e) 4T() + 50n3

Question 4 (10 points)

For each of the following input lists, state what you believe to be the most effective sorting algorithm.  Justify your reasoning, taking into account complexity, number of operations, memory usage and any other properties of sorted lists. If there are features or attributes of the algorithm that are implementation dependent, state these in your answer.

(a)  [1, 2, 3, 4, 6, 5, 7, 10]

(b)  [13, 12, 9, 6, 5, 4, 3, 2, 1]

(c)  [1, 10, 5, 8, 3, 9, 6, 4, 2]

(d)  [6, 5, 6, 5, 9, 11, 1, 23, 7].  Two objects with the same values need to preserve their order after sorting.

(e)  [(3, 9), (4, 5), (4, 4), (9, 5), (8, 7), (10, 6)] where each tuple (key, value) is sorted by

the key. The ordering of the values must be preserved where the keys are equivalent.

Question 5 (5 points)

Apply Dijkstra’s Algorithm to the following graph,  computing the shortest path for all vertices from vertex A.

11

17

47

Present the results in the format of the following table and write a paragraph to briefly explain your work process.

Each row states (a) the current stage, (b) the vertex just added to the search graph, and (c) the current updated predecessor node label and distance from A for each vertex in the graph. The vertices should be processed in the order dictated by Dijkstra’s Algorithm.

Question 6 (5 points)

Apply Dijkstra’s Algorithm to the following directed graph, and compute the shortest path for all vertices from vertex A. As in Question 5, present your results in the same table format, and write a paragraph to explain your work process.

Question 7 (10 points)

For the following graph:

7

17

25

C

5

(a) Apply Prim’s Algorithm, beginning at vertex A. Show the results of each stage of the

algorithm.  In this case, we define a stage as the addition of a new vertex and a new edge to the MST S={V,E}.

Present the results in the format of the following table (note that values provided are only examples and do not correspond to the solution), and write a paragraph to explain your work process.

(b) Apply Kruskal’s Algorithm.  Show the results of each stage of the algorithm.  In this

case, we define a stage as the processing of an edge from the graph, whether or not it

is added to the MST S={V,E}.

Present the results in the format of the following table (values provided are only examples and do not correspond to the solution), and write a paragraph to explain your work process.

Note the division of the MST Vertices Set into Connected Components.

Question 8 (10 points)

Figure 1 shows left and right rotations in a red-black tree to resolve violations.  T denotes the tree, while x and y are two nodes on the tree.  The operation LEFT-ROTATE(T, x) transforms the configuration of the two nodes on the left into the configuration on the right by changing a constant number of pointers. The inverse operation RIGHT-ROTATE(T, y) transforms the configuration on the right into the configuration on the left.  The letters α , β, and γ represent arbitrary sub-trees.

Figure 1: The rotation operations on a red-black tree

The pseudo-code for LEFT-ROTATE is shown in Algorithm 1. A node’s left child, right child and parent are represented as  .left,  .right and  .p respectively.   T.nil represents an empty node. This algorithm assumes that x.right T.nil and that the root’s parent is T.nil. Complete the pseudo-code for RIGHT-ROTATE in Algorithm 2.