Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

SEMESTER 1, 2020 SUPPLEMENTARY AND DEFERRED EXAMINATIONS

CITS2200

Data Structures and Algorithms

Q1.

(a) This is the insertion sort algorithm with two missing lines. Explain how you can complete this algorithm to sort the array A in ascending and descending orders by supplying the missing lines    (write two separate short answers).

procedure INSERTION-SORT(A)

for j from 2 to length[A]

do key = A[j]

i = j-1

(missing line 1)

do A[i+ 1] = A[i]

i = i-1

(missing line 2)

(5 marks)

(b) Explain clearly in your own words why the worst case complexity of the MERGESORT algorithm is O(nlog n), when the length of the array to be sorted is n.

(5 marks)

Q2.

(a) Write the Link class in Java (including variables and the constructor). We have used this class extensively in lectures and labs for constructing linked lists, stacks and queues.

(5 marks)

(b) Now modify your Link class to create a new class NewLink. The objects of this class store two references, one to the successor, and another to the successor of successor (if it exists, otherwise this reference is null).

You are given a linked list consisting of two objects from the NewLink class, called first and second in that order. Your task is to create an object called third of the NewLink class and connect it                   appropriately after the object 'second'.

(5 marks)

Q3.

(a) Explain why O(n^3log n) is not O(n^2)

(5 marks)

(b) Explain why O(nlog^2 n) is  O(n^2).

(5 marks)

Q4.

(a) Write a Java class for a node in a binary tree. Call it TreeNode. Write Java code for creating a binary tree with three nodes, the root node should be called 'root', the children of the root node

should be called 'first' and 'second'.

(5 marks)

(b) You are given a complete binary tree of height 3, with a root node and two levels of nodes below it. Here are the labels on the nodes (left to right).

root - a

first level - b,c

second level - d,e,f,g

b and c are children of a, d and e are children of b, and f and g are children of c.

Write these labels according to depth-first and breadth-first traversals of this binary tree. (5 marks)

Q5.

(a) Explain clearly in your own words Prim's minimum spanning tree algorithm.

(5 marks)

(b) Explain clearly how Prim's minimum spanning tree algorithm can be implemented efficiently using a priority queue data structure.

(5 marks)

Q6.

(a) Explain clearly in your own words Dijkstra's shortest-path algorithm for graphs. (5 marks)

(b) Explain in your own words the dynamic programming framework for the Floyd-Warshall                algorithm for computing all-pairs shortest paths in a graph. What is the complexity of this algorithm?

(5 marks)