GATE CS 2021 Set 2 Q.65 (CS Q.55): Dynamic Programming

In a directed acyclic graph with a source vertex $s$ , the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $s$ , the quality-score of $v$ is defined to be the maximum among the quality-scores of all the paths from $s$ to $v$ . The quality-score of $s$ is assumed to be 1.

Directed acyclic graph on a 3 by 3 grid. Bottom row s, a, b; middle row c, d, e; top row f, g, t. Edges: s to a (9), a to b (1), c to d (1), d to e (9), f to g (1), g to t (1); upward edges s to c (1), a to d (1), b to e (1), c to f (9), d to g (9), e to t (9). — Directed acyclic graph with edge weights

The sum of the quality-scores of all the vertices in the graph shown above is ______.

Your answer

Official answer and solution

Official answer: 929
From: Official GATE 2021 answer key

Solution

Compute the quality-score of each vertex in topological order by maximizing the product of incoming edge weights and predecessor scores.

Let the 9 vertices be arranged in a $3 \times 3$ grid with coordinates:

Bottom row: $s$ (source), $a$ , $b$
Middle row: $c$ , $d$ , $e$
Top row: $f$ , $g$ , $t$
Given that $Q(s) = 1$ .

Compute quality scores in topological order:

$Q(a) = Q(s) \times w(s, a) = 1 \times 9 = 9$
$Q(c) = Q(s) \times w(s, c) = 1 \times 1 = 1$
$Q(b) = Q(a) \times w(a, b) = 9 \times 1 = 9$
$Q(f) = Q(c) \times w(c, f) = 1 \times 9 = 9$

Vertex $d$ $d$ has incoming edges from $c$ $c$ and $a$ $a$ :
- From $c$ : $Q(c) \times w(c, d) = 1 \times 1 = 1$
- From $a$ : $Q(a) \times w(a, d) = 9 \times 1 = 9$
$Q(d) = \max(1, 9) = 9$

Vertex $g$ $g$ has incoming edges from $f$ $f$ and $d$ $d$ :
- From $f$ : $Q(f) \times w(f, g) = 9 \times 1 = 9$
- From $d$ : $Q(d) \times w(d, g) = 9 \times 9 = 81$
$Q(g) = \max(9, 81) = 81$

Vertex $e$ $e$ has incoming edges from $b$ $b$ and $d$ $d$ :
- From $b$ : $Q(b) \times w(b, e) = 9 \times 1 = 9$
- From $d$ : $Q(d) \times w(d, e) = 9 \times 9 = 81$
$Q(e) = \max(9, 81) = 81$

Vertex $t$ $t$ has incoming edges from $g$ $g$ and $e$ $e$ :
- From $g$ : $Q(g) \times w(g, t) = 81 \times 1 = 81$
- From $e$ : $Q(e) \times w(e, t) = 81 \times 9 = 729$
$Q(t) = \max(81, 729) = 729$

Sum the quality-scores across all 9 vertices:

\text{Sum} = Q(s) + Q(a) + Q(b) + Q(c) + Q(d) + Q(e) + Q(f) + Q(g) + Q(t)

\text{Sum} = 1 + 9 + 9 + 1 + 9 + 81 + 9 + 81 + 729 = 929

Final answer

929

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 65 of 65, printed as CS Q.55
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source