Suppose we are given a directed graph $G=(V,E)$ in which every edge has a distinct positive edge weight. A directed graph is acyclic if it has no directed cycle. Suppose that we want to compute the maximum-weight acyclic subgraph of $G$ (where the weight of a subgraph is the sum of its edges' weights). Assume that $G$ is weakly connected, meaning that there is no cut with no edges crossing it in either direction.

Here is an analog of Prim's algorithm for directed graphs. Start from an arbitrary vertex $s$, initialize $S = \{s\}$ and $F = \emptyset$. While $S \neq V$, find the maximum-weight edge $(u,v)$ with one endpoint in $S$ and one endpoint in $V-S$. Add this edge to $F$, and add the appropriate endpoint to $S$.

Here is an analog of Kruskal's algorithm. Sort the edges from highest to lowest weight. Initialize $F=\emptyset$. Scan through the edges; at each iteration, add the current edge $i$ to $F$ if and only if it does not create a directed cycle. Which of the following is true?

Consider a connected undirected graph $G$ with edge costs that are not necessarily distinct. Suppose we replace each edge cost $c_e$ by $-c_e$; call this new graph $G'$. Consider running either Kruskal's or Prim's minimum spanning tree algorithm on $G'$, with ties between edge costs broken arbitrarily, and possibly differently, in each algorithm. Which of the following is true?

Consider the following algorithm that attempts to compute a minimum spanning tree of a connected undirected graph $G$ with distinct edge costs. First, sort the edges in decreasing cost order (i.e., the opposite of Kruskal's algorithm). Initialize $T$ to be all edges of $G$. Scan through the edges (in the sorted order), and remove the current edge from $T$ if and only if it lies on a cycle of $T$.

Which of the following statements is true?

Consider an alphabet with five letters, $\{a,b,c,d,e\}$, and suppose we know the frequencies $f_a=0.32$, $f_b=0.25$, $f_c=0.2$, $f_d=0.18$, and $f_e=0.05$. What is the expected number of bits used by Huffman's coding scheme to encode a 1000-letter document?

Which of the following statements holds for Huffman's coding scheme?