We are given as input a set of $n$ requests (e.g., for the use of an auditorium), with a known start time $s_i$ and finish time $t_i$ for each request $i$. Assume that all start and finish times are distinct. Two requests conflict if they overlap in time --- if one of them starts between the start and finish times of the other. Our goal is to select a maximum-cardinality subset of the given requests that contains no conflicts. (For example, given three requests consuming the intervals $[0,3]$, $[2,5]$, and $[4,7]$, we want to return the first and third requests.) We aim to design a greedy algorithm for this problem with the following form: At each iteration we select a new request $i$, including it in the solution-so-far and deleting from future consideration all requests that conflict with $i$. Which of the following greedy rules is guaranteed to always compute an optimal solution?

We are given as input a set of $n$ jobs, where job $j$ has a processing time $p_j$ and a deadline $d_j$. Recall the definition of completion times $C_j$ from the video lectures. Given a schedule (i.e., an ordering of the jobs), we define the lateness $l_j$ of job $j$ as the amount of time $C_j-d_j$ after its deadline that the job completes, or as 0 if $C_j \le d_j$. Our goal is to minimize the maximum lateness, $\max_{j} l_j$. Which of the following greedy rules produces an ordering that minimizes the maximum lateness? You can assume that all processing times and deadlines are distinct.

Consider an undirected graph $G=(V,E)$ where every edge $e\in E$ has a given cost $c_e$. Assume that all edge costs are positive and distinct. Let $T$ be a minimum spanning tree of $G$ and $P$ a shortest path from the vertex $s$ to the vertex $t$. Now suppose that the cost of every edge $e$ of $G$ is increased by $1$ and becomes $c_e+1$. Call this new graph $G'$. Which of the following is true about $G'$?

Suppose $T$ is a minimum spanning tree of the connected graph $G$. Let $H$ be a connected induced subgraph of $G$. (I.e., $H$ is obtained from $G$ by taking some subset $S \subseteq V$ of vertices, and taking all edges of $E$ that have both endpoints in $S$. Also, assume $H$ is connected.) Which of the following is true about the edges of $T$ that lie in $H$? You can assume that edge costs are distinct, if you wish. [Choose the strongest true statement.]

Consider an undirected graph $G=(V,E)$ where edge $e\in E$ has cost $c_e$. A minimum bottleneck spanning tree $T$ is a spanning tree that minimizes the maximum edge cost $\max_{e\in T} c_e$. Which of the following statements is true? Assume that the edge costs are distinct.