All Algorithms questions

Single correct

• AOnly S1 is true
• BOnly S2 is true
• CBoth S1 and S2 are true
• DNeither S1 nor S2 is true

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]$

Single correct

• A$\Theta(m + n)$
• B$\Theta(m + n\log(n))$
• C$\Theta(nm)$
• D$\Theta(n^3)$

Single correct

• A$\Theta(n)$
• B$\Theta(\log(n))$
• C$\Theta(n\log(n))$
• D$\Theta(n^2)$

Algorithm B1:  For i = 1, 2, ..., n
                 For j = 1, 2, ..., n
                   T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm B2:  For s = 2, 3, ..., 2n
                 For i = 1, 2, ..., n
                   For j = 1, 2, ..., n
                     If (i + j == s)
                       T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Single correct

• ABoth algorithms $B_1$ and $B_2$ are correct
• BAlgorithm $B_1$ is correct, but algorithm $B_2$ is incorrect
• CAlgorithm $B_2$ is correct, but algorithm $B_1$ is incorrect
• DBoth algorithms $B_1$ and $B_2$ are incorrect

Single correct

• AThe height of $T$ is exactly 15.
• BThe height of $T$ is exactly 30.
• CThe height of $T$ is at least 15.
• DThe height of $T$ is at least 30.

Numerical answer

Single correct

• AEvery MST remains an MST, and every SP remains an SP.
• BMSTs need not remain MSTs, and every SP remains an SP.
• CEvery MST remains an MST, and SPs need not remain SPs.
• DMSTs need not remain MSTs, and SPs need not remain SPs.

Single correct

• A$\Theta(n)$
• B$\Theta(1)$
• C$\Theta(\log^2 n)$
• D$\Theta(\log n)$

someAlgo(G)
  1. Let v be any vertex in G. Run BFS on G starting at v.
     Let u be a vertex in G at maximum distance from v as given by the BFS.
  2. Run BFS on G again with u as the starting vertex.
     Let z be the vertex at maximum distance from u as given by the BFS.
  3. Output the distance between u and z in G.

Numerical answer

Single correct

• A$T(n) = \Theta(n \log\log n)$
• B$T(n) = \Theta(n \log n)$
• C$T(n) = \Theta(n^2 \log n)$
• D$T(n) = \Theta(n^2 \log\log n)$

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$

Numerical answer

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

Numerical answer

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

Numerical answer

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