Please write a full answer, and give a good explanation 4 Below are statements t

Question

Please write a full answer, and give a good explanation

4 Below are statements that are either true or false. For each statement say whether it is true or false and justify your answer in a few words a) The Radix sort algorithm in the textbook uses Counting sort to sort individual digits. We could swap Counting sort out for another sorting algorithm, e.g. Quicksort, and Radix sort b) We only need O(1) rotations in the worst case when inserting into a red-black tree with n c) If all the edge weights of a graph G are multiplied by a positive constant c, then the minimum d) If the graph G has edges with negative weights, then Dijkstra's algorithm for shortest path can e) Assume the problem TAS is in the complexity class NP and let SAT be the NP-complete would still work correctly. nodes spanning tree of G is unchanged get into an infinite loop on G problem Satisfiability. If we prove that TAS P SAT then TAS is also NP-complete.

Explanation / Answer

Solution:

a)

True

Explanation:

There can be any algorithm used but not quicksort since it is not a stable sort algorithm. The algorithm which is going to be used must be a stable sort algorithm.

b)

False

The number of rotations can be done at any point f time if the tree is getting unbalanced, so this depends on the order of the vertices which is getting inserted in the Red black tee

c)

True

The effective value of the edge weights won't have differed.

d)

True

Since in this case there might be a negative edge weight cycle present in the graph

e)

True

then, in this case, TAS will become NP-hard first but since TAS is also in NP means that it is NP-complete.

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

---