# Network | 代做network | 代做Algorithm | 代写java | project – COMP90038 Algorithms and Complexity

### COMP90038 Algorithms and Complexity

Network | 代做network | 代做Algorithm | 代写java | project – 这个题目属于一个Algorithm的代写任务, 包括了Network/network/Algorithm/java等方面, 该题目是值得借鉴的project代写的题目 ### Sample Exam 20 17 *

*This is only a sample exam. The number of questions asked in each section in the final exam may vary. The distribution of marks could change depending on the questions.

#### 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 
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.
``````
1. (2 marks) Use the Master Theorem to find the order of growth for the recurrence T(n) = 4T(n/2) + n^2

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

3. (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.
``````
1. (2 marks) Explain briefly when a sorting algorithm is said to be in-place.

#### Section B (3 2 marks): Answer all the questions

1. ( 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.

2. ( 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:

``````Algorithm A has an average  case run time of n , and a worst case run time of n^4 , 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 n^2.
``````

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

1. ( 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
``````
``````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:
``````
1. (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. 1 3 , 21 , 1 6, 4 0 , 3 0 , 2, 1 0 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.

2. ( 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:

##### 90
1. (9 marks) This question is about hashing. a. Insert items with the following keys into a hash table of size 7 12 7 6 8 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

##### 90

shorted bus route layout such that all suburbs between the eastern and western suburbs are connected, thus lowering costs.

``````a. What A bstract 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.

Network | 代做network | 代做Algorithm | 代写java | project – COMP90038 Algorithms and Complexity最先出现在学霸代写 – CS代写, 程序代写, CS作业代写, 代码代写, CS编程代写, java代写, python代写, c++/c代写, R代写, 算法作业代写, web代写, CS assignment代写, MATH代写, 统计代写, 金融代写, business代写, economic, accounting代写等。

Posted

in

by

Tags: