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

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

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

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.

Single correct

• A1
• B$N - 1$
• C$N$
• D$2N - 1$

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

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

Single correct

• A$T(n) = \Theta(2^n)$
• B$T(n) = \Theta(n2^n)$
• C$T(n) = \Theta(3^n)$
• D$T(n) = \Theta(n3^n)$

Single correct

• A$f(n^2) = \theta(f(n)^2)$, when $f(n)$ is a polynomial
• B$f(n^2) = o(f(n)^2)$
• C$f(n^2) = O(f(n)^2)$, when $f(n)$ is an exponential function
• D$f(n^2) = \Omega(f(n)^2)$

Answer key coming soon

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

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