Complete the sequence of edges in the mst

Assignment Help Data Structure & Algorithms

Reference no: EM131310303

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?

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.

(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

Reference no: EM131310303

Questions Cloud

Describe the he main idea of your cryptography method : Describe the he main idea of your cryptography method along with its type (whether it's Symmetric encryption or Asymmetric encryption).

Supply chain erp systems and advanced planning : Compare and contrast the role of supply chain ERP systems and advanced planning and scheduling systems in enhancing firm and supply chain competitiveness.

How the principle of least privilege could be used : The PostScript language [11] describes page layout for printers. Among its features is the ability to request that the interpreter execute commands on the host system.

Internet for logistics and supply chain information exchange : Discuss and compare the role that ED1 and the Internet will play in facilitating communication between supply chain partners.

Complete the sequence of edges in the mst : Consider the following edge-weighted graph with 9 vertices and 19 edges. Complete the sequence of edges in the MST in the order that Kruskal's algorithm includes them (by specifying their edge weights)

Identify a common task that might occur regularly : Identify a common task that might occur regularly. The task should be one that might occur in a business setting rather than one in someone's personal life.

Importance of information security for organization : Describe the importance of information security for an organization, supporting with evidence. How could a lack of security affect not only consumers,but a company as well?

Discuss the relative benefits of software purchase : Discuss the relative benefits of software purchase, use of third-party providers, and use of application service providers.

How do each of these styles relate to theory : Chapter 7 discusses several styles of leadership, including autocratic, democratic, and laissez-faire. How do each of these styles relate to Theory X and Theory Y assumptions about workers?

Reviews

len1310303

12/13/2016 2:41:23 AM

Submit your answers to the above questions organized very clearly. If I can’t tell what your answer is or which question you are answering, I can’t give you credit. You may answer your questions in an electronic document or you can answer on paper and then scan those answers in to submit them via D2L. But I must be able to read it, and know which answer goes with which part of which question. There is no need for a proctor. There is no time limit. But I will not accept late submissions. Do not wait until the last minute. Submit your solutions, then if you can answer more questions before the due date and time, submit an update to your answers. You may use your textbooks, your notes, other resources from our class site when answering questions. You may not use internet searches or human assistance. You may contact me to ask questions about the exam problems up until 24 hours before it is due. If any question seems ambiguous, you may add an explanation for your answer.

Write a Review

Required(*) Message

User Account

All Pages