All Algorithms questions

One or more correct

• AIn every cycle $C$ of $G$, the edge with the largest weight in $C$ is not in any MST
• BIn every cycle $C$ of $G$, the edge with the smallest weight in $C$ is in every MST
• CFor every vertex $v \in V$, the edge with the largest weight incident on $v$ is not in any MST
• DFor every vertex $v \in V$, the edge with the smallest weight incident on $v$ is in every MST

DFS(G):                          Explore(G, v, t):
  unmark all v ∈ V                 mark v
  t ← 0                            t ← t + 1
  for each v ∈ V                   d[v] ← t
     if v is unmarked              for each (v, w) ∈ E
        t ← Explore(G, v, t)            if w is unmarked
     end if                                t ← Explore(G, w, t)
  end for                               end if
                                   end for
                                   t ← t + 1
                                   f[v] ← t
                                   return t

One or more correct

• A$d[u] < d[v] < f[v] < f[u]$
• B$d[v] < d[u] < f[u] < f[v]$
• C$d[v] < f[v] < d[u] < f[u]$
• D$d[u] < d[v] < f[u] < f[v]$

One or more correct

• A$T(n) = T(n-1) + 1, \quad T(1) = 1$
• B$T(n) = 2T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1$
• C$T(n) = 2T\left(\frac{n}{2}\right) + n, \quad T(1) = 1$
• D$T(n) = T(n-1) + n, \quad T(1) = 1$

One or more correct

• AA DFS tree of $G$ is a Shortest Path tree of $G$.
• BEvery non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.
• CIf $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source vertex $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.
• DBoth BFS and DFS can be used to find the connected components of $G$.

One or more correct

• AThere are no back-edges in $G$ with respect to the tree $T$
• BThere are no cross-edges in $G$ with respect to the tree $T$
• CThere are no forward-edges in $G$ with respect to the tree $T$
• DThe only edges in $G$ are the edges in $T$

One or more correct

• AAll edges in $G$ have even weight
• BAll edges in $G$ have even weight OR all edges in $G$ have odd weight
• CIn each cycle $C$ in $G$, all edges in $C$ have even weight
• DIn each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

One or more correct

• A$f \in O(g)$
• B$f \in \Omega(g)$
• C$f \in o(g)$
• D$f \in \Theta(g)$

Answer key coming soon

Function 1                      Function 2
while n > 1 do                  for i = 1 to 100 * n do
  for i = 1 to n do               x = x + 1;
    x = x + 1;                  end for
  end for
  n = floor(n/2);
end while

One or more correct

• A$f_1(n) \in \Theta(f_2(n))$
• B$f_1(n) \in o(f_2(n))$
• C$f_1(n) \in \omega(f_2(n))$
• D$f_1(n) \in O(n)$

Answer key coming soon

One or more correct

• AThe edge with the second smallest weight is always part of any minimum spanning tree of $G$.
• BOne or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of $G$.
• CSuppose $S \subseteq V$ be such that $S \ne \phi$ and $S \ne V$. Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V \setminus S$. Such an edge will always be part of any minimum spanning tree of $G$.
• D$G$ can have multiple minimum spanning trees.

Answer key coming soon

One or more correct

• A$f(2^n - 1) = 2^n - 1$
• B$f(2^n) = 1$
• C$f(5 \cdot 2^n) = 2^{n+1} + 1$
• D$f(2^n + 1) = 2^n + 1$

Answer key coming soon

One or more correct

• A$R_7 = 18$
• B$R_7 = 19$
• C$R_7$ is achieved by three different solutions.
• D$R_7$ cannot be achieved by a solution consisting of three pieces.

Answer key coming soon

One or more correct

• ARoot of $T$ can never be an articulation point in $G$.
• BRoot of $T$ is an articulation point in $G$ if and only if it has 2 or more children.
• CA leaf of $T$ can be an articulation point in $G$.
• DIf $u$ is an articulation point in $G$ such that $x$ is an ancestor of $u$ in $T$ and $y$ is a descendent of $u$ in $T$, then all paths from $x$ to $y$ in $G$ must pass through $u$.

Answer key coming soon

One or more correct

• AThe graph does not have a topological order.
• BA depth-first traversal starting at vertex S classifies three directed edges as back edges.
• CThe graph does not have a strongly connected component.
• DFor each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$.

Answer key coming soon