$($Each problem is $2$ points.$)$

$($a$)(2$ points$)$

Suppose that AlgA and AlgB are two algorithms that solve the same problem. If the runtime of AlgA on an input of size $n$ is exponential in terms of $n$ and the runtime of AlgB is polynomial in terms of $n$ then AlgB will always run faster than AlgA on all inputs.

True

False

$($b$)(2$ points$)$ Suppose that $T(n)=4T(\frac{n}{2})+c{n}^2$ and $S(n)=9S(\frac{n}{3})+c\sqrt[\phantom{2}]{n}.$ Assuming that $T(1)=S(1)=c,$ what is true about $T(n)$ and $S(n)?$

$T(n)=O(S(n))T(n)=(S(n))T(n)=(S(n))$

$($c$)$ Suppose $T(n)=6T(\frac{n}{3})+O(n^2).$ Use Master Theorem to solve this recurrence. $($give the values of $ab$ and $d$ and the closed form of the recurrence in terms of $O.)$

$($d$)(2$ points$)$ If $A$ is in NP and A reduces to $B$ then $B$ must be in NP$.$

True

False

Unknown

$($e$)(2$ points$)$ If the vertices of a DAG are put in topological ordering then all of the edges go from a vertex earlier in the list to a vertex later in the list.

True

False

$($f$)(2$ points$)$ If $A$ is in $P$ and $B$ is NP$-$complete then A reduces to $B.$

True

False

Unknown

$($g$)(2$ points$)3$SAT is in $NP.$

True

False

Unknown