Time left $3$:$21$:$41$

Question $1$

Not yet answered

Marked out of $3$

Remove flag

Question text

We want to pre$-$process a given unweighted digraph G$=($V$,$E$)$

to set up a suitable data structure so that we can use it to answer any query of the following form in O$(1)$

time:

Query: Given an arbitrary pair of vertices u$,$v in V

$,$ is there a directed path in G

from u

to v

whose length is divisible by $5?[$Length of each edge is $1.]$

With the techniques learned in this course, the pre$-$processing can be done most efficiently in worst$-$case $\backslash$theta $($Vd$)$

time, where d$=$

$\_\_\_\_\_\_.$

Question $1$Answer

a$.$

$2$

b$.$

$3$

c$.$

$7$

d$.$

$5$

e$.$

$8$

f$.$

This problem cannot be solved $($deterministically$)$ in polynomial time, unless P$=$NP

$.$

g$.$

$6$

h$.$

$4$

Question $2$

Not yet answered

Marked out of $4$

Flag question

Question text

Let G$=($V$,$E$)$

be any planar graph with $3$ or more vertices. It is a known fact that in any such graph $|$E$|<=3|$V$|3$

$.$

$($If there is more than one correct choice, select the red choice.$)$

Question $2$Answer

a$.$

G

must have a node with degree at most $5.$

b$.$

None of the other choices.

c$.$

There is a planar graph G

in which every node has degree at least $10.$

d$.$

More than one of the other choices are correct.

e$.$

At least half of the nodes in G

must have degree at most $12.$

Question $3$

Not yet answered

Marked out of $4$

Flag question

Question text

Suppose we apply Prim$$s Minimum Spanning Tree $($MST$)$ algorithm to the weighted graph G

shown below starting from vertex a

$.$ Let T

denote the resulting MST$.$

$($If more than one answer is correct, select the one in red.$)$

Question $3$Answer

a$.$

Edge $($b$,$c$)$

is the $9$th edge added to T

$.$

b$.$

More than one of the other choices are correct.

c$.$

Edge $($e$,$i$)$

is the $8$th edge added to T

$.$

d$.$

There are at most $5$ edges on the unique simple path in T

between vertices b

and j

$.$

e$.$

Edge $($i$,$j$)$

is added to T

before edge $($g$,$l$)$