For each of the following, choose true or false and briefly justify your

answer. Each problem is worth $4$ points, $2$ points for your answer and

$2$ points for your justification.

$(1)$ T$/$F With all equal$-$sized intervals, a greedy algorithm based on earliest

start time will always select the maximum number of compatible intervals.

$(2)$ T$/$F If we divide an array into groups of $3,$ find the median of each group,

recursively find the median of those medians, partition, and recurse, then

we can obtain a linear$-$time median$-$finding algorithm.

$(3)$ T$/$F Van Emde Boas sort $($where we insert all numbers, find the min, and

then repeatedly call SUCCESSOR$)$ can be used to sort $n=$lgu numbers

in $O(lgu*lglglgu)$ time.

$(4)$ T$/$F $3$SAT cannot be solved in polynomial time, even if $P=NP.$

$(5)$ T$/$F Negating all the edge weights in a weighted undirected graph G and

then finding the minimum spanning tree gives us the maximum$-$weight

spanning tree of the original graph G$.$