1. For each of these problems, indicate TRUE if the statement is always true. Ot

Question

1. For each of these problems, indicate TRUE if the statement is always true. Otherwise, enter FALSE. Any text other than either TRUE or FALSE may result in no credit for the problem part.

a. There exists an AVL tree on at least 4 vertices that can be colored to make a valid red-black tree.

b. Adding a constant to every edge weight does not change the vector resulting from Dijkstra's algorithm implementation on a graph.

c. The language NONPLANAR consists of all graphs that are not planar. NONPLANAR is in NP.

d. Each iteration of Bellman-Ford must relax edges in the same order for the algorithm to produce the shortest paths in a graph.

e. If the edges of a graph all have different weights, then the shortest path between any two vertices is unique.

g. Consider an implementation of a B-tree (t=2) with lazy deletion: when a node is deleted, we simply mark it "deleted"; every 100 operations, we reorganize the entire data structure by inserting its (non-deleted) nodes into a new B-tree (t=2). For this data structure, any total of n insertions or deletions require at most O(n log n) time.

Explanation / Answer

a.TRUE

b.FALSE

c.FALSE

d.TRUE

e.FALSE

f.TRUE

g.FALSE

As you said any text other than TRUE or FALSE will result to no credit.Therefore,I am not giving explanation

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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