All Algorithms questions

Single correct

• A$T_1(n) = \Theta(n^2)$
• B$T_1(n) = \Theta(n^2 \log_2 n)$
• C$T_1(n) = \Theta(n^{\log_4 5})$
• D$T_1(n) = \Theta(n^{\log_4 5} \log_2 n)$

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$\log(n),\ n^{1/3},\ 2^{\log(n)},\ \log(n!)$
• B$n^{1/3},\ \log(n),\ \log(n!),\ 2^{\log(n)}$
• C$\log(n),\ n^{1/3},\ \log(n!),\ 2^{\log(n)}$
• D$2^{\log(n)},\ n^{1/3},\ \log(n),\ \log(n!)$

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$

Numerical answer

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

• A$d_1(u, v) = d_2(u, v)$
• B$d_1(u, v) \le d_2(u, v)$
• C$d_1(u, v) \ge d_2(u, v)$
• D$d_1(u, v) \ne d_2(u, v)$

Single correct

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

fun(int A[0,…,n-1]){
    for i=0 to n-2
        for j=0 to n-i-2
            if (A[j]>A[j+1])
                then swap A[j] and A[j+1]
}

Numerical answer

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

• A1
• B$N - 1$
• C$N$
• D$2N - 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$.

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