Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$ E, define w'(u, v) as w(u, v) + f(u) - f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”.
A
for every f : V $$ \to $$ R
B
if and only if $$\forall u \in V$$, f(u) is positive
C
if and only if $$\forall u \in V$$, f(u) is negative
D
f and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex
s to G and edges of zero weight from s to every vertex of G
2
GATE CSE 2020
Numerical
+2
-0.67
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
Your input ____
3
GATE CSE 2020
MCQ (Single Correct Answer)
+1
-0.33
Consider a relational database containing the following schemas.
The primary key of each table is indicated by underlying the constituent fields.
SELECT s.sno, s.sname
FROM Suppliers s, Catalogue c
WHERE s.sno = c.sno AND
Cost > (SELECT AVG (cost)
FROM Catalogue
WHERE pno = ‘P4’
GROUP BY pno);
The number of rows returned by the above SQL query is
A
4
B
5
C
2
D
0
4
GATE CSE 2020
MCQ (Single Correct Answer)
+1
-0.33
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?
