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

• Aboth $O(N)$ and $\Omega(N)$
• B$O(N)$ but not $\Omega(N)$
• C$\Omega(N)$ but not $O(N)$
• Dneither $O(N)$ nor $\Omega(N)$

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

Single correct

• A$t > 2n - 2$
• B$t > 3\left\lceil \frac{n}{2} \right\rceil$ and $t \le 2n - 2$
• C$t > n$ and $t \le 3\left\lceil \frac{n}{2} \right\rceil$
• D$t > \lceil \log_2(n) \rceil$ and $t \le n$

Answer key coming soon

Single correct

• A$f_3, f_2, f_1$
• B$f_2, f_1, f_3$
• C$f_1, f_2, f_3$
• D$f_2, f_3, f_1$

Answer key coming soon

Single correct

• ASelection sort
• BMergesort
• CInsertion sort
• DQuicksort using the last element as pivot

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

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

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