All Algorithms questions

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(n) = \Theta(2^n)$
• B$T(n) = \Theta(n2^n)$
• C$T(n) = \Theta(3^n)$
• D$T(n) = \Theta(n3^n)$

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

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

Numerical answer

Answer key coming soon

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

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

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