Please write a full answer, and give a good explanation 3 Below are some stateme

Question

Please write a full answer, and give a good explanation

3 Below are some statements. For each statement say if it is true or false and justify that in a few words. Note that here the justification is the most important thing. a) If one letter has a frequency of 0.45 (i.e. 45%) then it will always have 1-bit code in Huffman coding, no matter what frequency the other letters have. b) If P NP the you need exponential time algorithms for all problems in NP. c) We do a depth-first search on the directed graph G. If (u, v) is an egde in G and if we have then (u, v) is a forward edge in the depth-first tree. d) It makes no difference to the time complexity of Radix sort whether the input is aleady sorted or unsorded. e) Ef x and y are two leaves in a binary heap then the difference between their depth (i.e. distance from the root) is at mos

Explanation / Answer

Solution:

3)

a)

True

Explanation:

Since 0.45 is such a high frequency and if there is on one another number with 0.55, then we will be encoding both with 1 bots, else if there are more than 1 then the encoding will be assigning 1 bit to the highest frequency element which is going to be 0.45 element.

b)

False

Then P will still be the subset of NP, which means all the polynomial-time algorithms will be residing in NP.

c)

True

Explanation:

Forward edge: (u, v), where v is a descendant of u, but not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

d)

True

Since the radix sort will still be sorting the elements based on there indexes values, which means irrespective of the array the same number of steps will be performed.

e)

True

Because a heap is an Almost complete binary tree.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---