代做COMP 3804、代写Computer Science、Python，c/c++，Java程序语言代写

日期：2020-03-10 10:26

COMP 3804: Assignment 2

Winter 2020

School of Computer Science Carleton University

Due Date: Sunday, March 8th at 11:59PM

Your assignment should be submitted online on cuLearn as a single .pdf file. No late assignments

will be accepted. You can type your assignment or you can upload a scanned copy of it. Please use

a good image capturing device. Make sure that your upload is clearly readable. If it is difficult to

read, it will not be graded!

Question 1 [15 marks]

You are given two input heaps, called n-heap and k-heap, on n = 22 and k = 17 elements,

respectively. Determine the two descriptors. Then, determine the descriptor for the heap, called

(n + k)-heap that arises after merging the n-heap and k-heap. Show using clear illustrations how

the shape (not the heap order) of (n + k)-heap is created from the input heaps.

Question 2 [25 marks]

Design a data structure built on a set S, |S|=n, with the below properties:

? Finding the kth orderstatic of S, can be carried out in O(1) time, for 1,

? Deleting the kth orderstatistic can be carried out in O(log n) time, for 1,

? Inserting a new element takes O(log n) time.

? Listing, in no particular order, all elements between the

orderstatic (i.e., all elements in the second quartile) can be done without any element comparison.

? Creating the data structure takes linear time.

Note: A data structure does not necessarily have to be a single tree.

Question 3 [20 marks]

Suppose that we want to find a minimum spanning tree of the graph shown on Figure 1.

? Run Prim’s algorithm on this graph. Start from vertex A and whenever there is a choice of

vertices, always select in the alphabetic order. Draw a table showing the intermediate values

at each step.

? Run Kruskal’s algorithm on the same graph. Clearly show the disjoint-set data structure

(i.e., the structure of the directed trees) at every intermediate step, assuming union using

path compression.

1

Figure 1: The input graph for Question 3.

Question 4 [20 marks]

In this question, all graphs have edge weights. Here, MST denotes the minimum spanning tree.

a. Let T be a minimum spanning tree for G. Assume first that the deletion of an edge with

minimum edge weight does not alter the MST. What can you say about the input graph?

Now assume that it does alter the MST what can you say about the input graph?

b. Explain briefly, but rigorously, why running the Kruskal’s algorithm with doubling of the

weights (of each edge) yields an MST on the original graph (with the original weights).

(Obiously the weight of the two MSTs are different but not their structure.) Here, assume

that all weights are non-negative.

c. Let G = (V, E) be a graph with distinct weights. Let emax be the edge with maximum weight.

Prove that if emax is in a minimum spanning tree, then its removal must disconnect G.

Question 5 [20 marks]

Consider the matrix multiplication of the matrices M2,2M2,8M8,12M12,10M10,23M23,20. Here, Mi,j

denotes a matrix with i rows and j columns. In the below, we will use the notation m[i, j] and

s[i, j] from the course notes.

(a) Run the algorithm matrixChain(·) on the given matrices and determine the minimum number

of scalar multiplications for them. You must show the table m[i, j] and your calculations for

how you got the value of each entry of the table.

(b) Compute the parenthesization corresponding to the minimum value that you obtained in Part

(a). To this end, you must show the table s[i, j] and illustrate how you use this table to find

the parenthesization.

End of Assignment 2.

2