$(10$ points$)$ True or False?

For each of the statements below, determine whether it is True or False. Then, briefly explain

your answers or provide counterexamples. Incorrect answers or unanswered questions are worth

zero points. $($Each subproblem is worth $2$ point.$)$

$($a$)$ Claim: $A(nlogn)$ algorithm runs faster than a $(n^2)$ algorithm for any input instance.

$($b$)$ Consider an instance of the Stable Matching Problem in which there exists a hospital $h$

and a student $s$ such that $h$ is ranked first on the preference list of $s$ and $s$ is ranked first

on the preference list of $h.$

Claim: In every stable matching $S$ for this instance, the pair $(h,s)$ belongs to $S.$

$($c$)$ Consider the interval scheduling problem we discussed in the class, where we want to

maximize the number of compatible $($i$.$e$.,$ non$-$overlapping$)$ intervals.

Claim: The latest$-$start$-$time$-$first algorithm is optimal for the above problem.

$($d$)$ Consider a forest graph $G$ consisting of $k$ trees. Suppose $G$ has $n$ nodes.

Claim: Graph $G$ has $n-k$ edges.

$($e$)$ Let $T$ be a minimum spanning tree of a graph $G.$

Claim: for any pair of vertices $s$ and $t,$ the shortest path from $s$ to $t$ in $G$ is the path from

$s$ to $t$ in $T.$