Q1. Analysis of algorithms: For each expression in the leN column, give the best matching description from the right column.
______N3
______1 + 2 + 3 + 4 + 5 + : : : + N A. 1/2N2.
______1/2N2 + 100NlgN B. O(N2).
______1/2N2 C. Both A and B.
______2 + 4 + 6 + 8 + 10 + : : : +N D. Neither A nor B.
______N2
______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 N2
|
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