It is due in 2 hours.. Thanks ! Suppose that an algorithm runs on a tree contain

Question

It is due in 2 hours.. Thanks !

Suppose that an algorithm runs on a tree containing n nodes. What is the time complexity of the algorithm if the time spent per node in the tree is proportional to the number of grandchildren of the node? (Assume that the algorithm spends O(1) time for every node that does not have a grandchild.) In modern software development, a useful utility called make is usually employed to manage the compilation order of files. The problem is: you are given n files that need to be compiled. Some of the files can only compile when some other files have been compiled. Your job is to find an ordering to compile the n files. Can you solve this problem in polynomial (in n) time by some algorithm you learned in this course (you only need to spell out the name of the algorithm)? If so, what is the running time of your algorithm? Consider an array A[1...n] of integers in the range 1...n^2. A number a is a heavy hitter in A if a occurs in A at least n/2 times. Note that an array of size n can have at most two heavy hitters. Give an O(n log n) algorithm that finds all heavy hitters in a given array A.

Explanation / Answer

I can help you with this. But I can't give detailed explanaton for some

a) suppose this is a binary tree then root has 2 child subtrees each having n/2 nodes. which in turn have 4 grandchild of root each having n/4 nodes

hence T(n) = c*T(n/4) + constant

using master theorem we can say that time complexity is O(nlog4c)

2) This is basically problem to prevent deadlocks which you might have studied in your operating system course. We can use Banker's algorithm here or any other which you might have studied like "resource allocation graph" or "safety algorithm" Complexity is O(n3)

3) Use self-balancing BST

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.