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

COMP90038

Algorithms and Complexity

Sample Exam 2017*

Section A (13 marks): Answer all the questions

1. (1 mark) What is the fundamental difference between the stack ADT and a queue ADT?

2. (2 marks) Consider the following algorithm.

Algorithm MIN1(A[0..n-1])

If n = 1 then return A[0]

else temp ← MIN1(A[0..n-2])

if temp <= A[n-1] then return temp

else return A[n-1]

end if

end if

i. What does this algorithm compute?

ii. What is its basic operation?

iii. How many times is the basic operation executed?

iv. What is the efficiency class of this algorithm? Show your working.

3. (2 marks) Use the Master Theorem to find the order of growth for the recurrence

T(n) = 4T(n/2) + n2

4. (1mark) What is the worst case complexity of selection sort? Use big-Oh notation.

5. (1 mark) What is the best case complexity of merge sort? Use big-Oh notation.

6. (4 marks) For each of the following statements, indicate whether it is true or false:

a. “Heap sort is a stable sorting algorithm”.

b. “The worst case complexity of merge sort is O(n²).

c. “Insertion sort is a stable algorithm”.

d. “The height of a complete binary tree with N nodes is N”.

7. (2 marks) Explain briefly when a sorting algorithm is said to be in-place.

Section B (32 marks): Answer all the questions

8. (3 mark) Sequential search can be used with about the same efficiency whether a list is implemented as an array or a linked list. Is this statement true or false for binary search? Justify your answer.

9. (3 marks) You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking your advice about which algorithm to use:- 3 -

Algorithm A has an average – case run time of n, and a worst case run time of n4 , where n is the number of input parameters.

Algorithm B has an average case run time of n(log n)3 , and a worst case of n2 .

Which algorithm would you favour for inclusion in the software? Justify your answer.

10. (4 marks) This question is about graph algorithms

a. (2 marks) Sketch a graph that could be used to model the friendship network of a group of four people. Draw the corresponding adjacency matrix representation of your graph.

b. (2 marks) Traverse the graph by Breadth First Search (BFS). You may start the traversal at vertex 10 and construct the corresponding BFS forest:

11. (5 marks) This question is about heaps and heap sort.

a. (3 marks) Sort the following list (into increasing order) by heap sort, using array representation of heaps. Show your workings. 13, 21, 16, 40, 30, 2, 10

b. (2 marks) State whether the following statements are true or false:

i. A heap is a complete binary tree.

ii. The heap structure must satisfy either the structural constraint or the value relationship constraint.

12. (8 marks) This question is about search trees

a. (2 marks) What is the relationship between the value stored at a node and the values stored at its children in a Binary Search tree?

b. (2 marks) Suggest one limitation of using a Binary Search Tree in search applications?

c. (2 marks) Build an AVL tree for the list of items: 1 6 2 1 5 8 7 4 2

d. (2 marks) Show one possible binary search tree that can result from deleting 60 in the following binary search tree:

13. (9 marks) This question is about hashing.

a. Insert items with the following keys into a hash table of size 7

Use the hash function h(k) = k(k+3) mod 7.

i. (2 marks) Use separate chaining for collision resolution. Show the hash value you have calculated for each input key, and show the hash table after all items have been inserted.

ii. (4 marks) Use linear probing for collision resolution. Show the hash value you have calculated for each input key, and show the hash table after all items have been inserted.

iii. (1 mark) For the resulting hash table using linear probing, how many probes are needed in a search for the key 5.

b. (2 marks) Why is it not a good idea for a hash function to depend on just one letter (say the first one) of a natural language word?

Section C (25 marks) Answer all the questions

14. (6 marks) Write a correct and detailed algorithm that takes as input a Binary Search Tree (BST) T and finds the second largest value in the given BST. You may assume that the BST has at least two nodes, and that all of the node values are distinct. You must use clear, appropriately commented pseudo-code, Java or C to write your algorithm. Then, analyze the time and space complexity of your algorithm. Show your working for the complexity analysis.

15. (9 marks) Building the east-west road link created a budget blowout for the Victorian Government even before the project started. However, in the quest to provide better road infrastructure for suburbs in Melbourne, the Victorian Government in partisan with the road authorities, have now decided to lay bus routes connecting suburbs between the east and west of Melbourne. The road authorities have asked the project manager to start work on this project. The project manager has called on you – the software engineer – to design and implement an algorithm that manages a bus router problem between suburbs in Melbourne. The road authorities want to have bus routes in the suburb such that there is at least one bus route connecting every pair of suburbs. Furthermore, as laying roads is very expensive, the road authorities want to minimize the total amount of bus routes they wish to lay. Your algorithm must provide the project manager with a shorted bus route layout such that all suburbs between the eastern and western suburbs are connected, thus lowering costs.

a. What Abstract Data Type (ADT) should be used to help manage the bus-router problem?

b. Write a clear, correct and detailed algorithm to solve this problem. Make sure you design the algorithm to accept relevant input and; produces an appropriate output that the project manager can use to identify the shortest bus route layout connecting suburbs. You must use clear, appropriately commented pseudo-code, Java or C to write your algorithm.

16. (10 marks) Let A[0 ..n-1] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

a) List the inversions of the array (2, 3, 8, 6, 1).

b) What arrays of size n have the largest number of inversions and what is this number?

c) What arrays of size n have the smallest number of inversions and what is this number?

d) Write two different algorithms that you could use to count the number of inversions in a list of n elements, one based on each of the following design strategies:

(i) Brute force

(ii) Divide and conquer

You must use clear, appropriately commented pseudo-code, Java or C to write your algorithm.

e) Analyze the complexity of each algorithm and determine the efficiency class. You must show how you arrived at your answer.