Consider the following edge-weighted graph with 9 vertices

Question

Q1. Analysis of algorithms: For each expression in the leN column, give the best matching description from the right column.

______N³

______1 + 2 + 3 + 4 + 5 + : : : + N                                         A. 1/2N².

______1/2N² + 100NlgN                                                          B. O(N²).

______1/2N²                                                                          C. Both A and B.

______2 + 4 + 6 + 8 + 10 + : : : +N                                        D. Neither A nor B.

______N²

______1 + 2 + 4 + 8 + 16 + : : : + N

Q2. For each quantity in the left column, give the best matching description from the right column.

______Height of a weighted quick union data structure with Nitems.                                 A. lgN in the best case.

______Height of a binary heap with N keys.                                                                   B. lgN in the worst case.

______Height of a left-leaning red-black BST with Nkeys.                                                C. Both A and B.

______Maximum function-call stack size when (top-down) merge sorting N keys.               D. Neither A norB.

______Maximum function-call stack size when quick sorting Nkeys.

______Number of compares to binary search a sorted array of sizeN.

Q3. Consider the following code fragment.

int count = 0;

int N = a.length;

Arrays.sort(a);

for (int i = 0; i < N; i++) {

for (int j = i+1; j < N; j++) {

if (Arrays.binarySearch(a, a[i] + a[j])) count++;

}

}

Suppose that it takes 1.5 second when N = 3,500. Approximately how long will it take when N = 35,000? Select the best answer:

15 seconds         

30 seconds         

1.5 minute         

30 minutes         

1.5 hours            

4.5 hours

Q4. Ordered-array implementation of a set.

Suppose you implement the set data type using an ordered array. That is, you maintain the N keys in the set in ascending order in an array.

What is the order of growth of the worst-case running time of each of the operations below? Write down the best answer in the space provided using one of the following possibilities.

1              logN       sqrt(N) N             NlogN                   N²

function	description	performance
add(key)	add the key to the set
contains(key)	is the key in the set?
ceiling(key)	smallest key in the set >= key
rank(key)	nume of keys in set smaller than given key
select(i)	ith largest key in the set
min()	smallest key in the set
delete(key)	delete the given key from the set
iterator()	iterate over all N keys in order

Q5. Red-black trees

Consider the following left-leaning red-black tree. Add the key Z, then add the key P

(a) Draw the resulting left-leaning red-black tree.

(b) How many left rotations, right rotations, and color flips are performed in total to insert the two keys?

______left rotation(s)                  ______right rotation(s)                                ______color flip(s)

Q6. Hashing

Suppose that the following keys are inserted in some order into an initially empty linear- probing hash table of size 7, using the following table of hash values:

key hash	key hash
A	3
B	1
C	4
D	1
E	5
F	2
G	5

Which of the following could be the contents of the linear-probing array?

I.

0	1	2	3	4	5	6
G	B	D	F	A	C	E

II.

0	1	2	3	4	5	6
B	G	D	F	A	C	E

III.

0	1	2	3	4	5	6
E	G	F	A	B	C	D

Select the best answer.

(a) I only.

(b) I and II only.

(c) I and III only.

(d) I, II and III.

(e) None.

Q7. Hard problem identification.

You are applying for a job at a new software technology company. Your interviewer asks you to identify the following tasks as easy (E) or impossible (I).

______ Build a balanced BST containing N keys using 8N compares (where the array of keys are given to you in ascending order).

______ Build a balanced BST containing N keys using 8N compares (where the array of keys are given to you in arbitrary order).

______ Build a binary heap containing N keys using 2N compares (where the array of keys are given to you in arbitrary order).

______Build a BST containing N keys that has height at most _1/2lgN.

______Design a priority queue that does insert and delete-max in lg lgN compares per operation, where N is the number of items in the data structure.

Q8. Minimum spanning trees

Consider the following edge-weighted graph with 9 vertices and 19 edges. Note that the edge weights are distinct integers between 1 and 19.

(a) Complete the sequence of edges in the MST in the order that Kruskal's algorithm includes them (by specifying their edge weights).

(b) Complete the sequence of edges in the MST in the order that Prim's algorithm includes them (by specifying their edge weights).

Q9. Discuss the dramatic effect that algorithm choice can have on performance by giving example algorithms with markedly different performance characteristics when used to solve the same problem. Describe any theoretical or empirical performance results regarding the problems/algorithms you discuss.

Q10. Is the Partition problem in P or NP? Provide an argument that demonstrates your answer.

Q11. Define Big-O, Big-Theta, and Big-Omega. Describe the differences among them. Define the ~ notation and describe the key differences between it and the other three formalisms.

Q12. Define "loitering" Explain why it can matter. Give an example of code where loitering might occur and detail the changes necessary to prevent it.

Attachment:- Assignment.rar