• Submission Guideline: Upload your homework file (hw3_[your student id].doc or hw3_[your student id].hwp) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience.
• Deadline: 23:59 PM, Tuesday, December 10, 2024

       

Please feel free to leave your questions about homework problems in the online Ed Discussion platform.

   

1. Consider a modification to the activity-selection problem in which each activity $a_i$ has, in addition to a start and finish time, a value $v_i$. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set $A$ of compatible activities such that $\sum_{a_k \in A} v_k$ is maximized. Give a polynomial-time algorithm for this problem.

   

2. Show how to solve the fractional knapsack problem in $O(n)$ time.

   

3. The transpose of a directed graph $G = (V, E)$ is the graph $G^\text T = (V, E^\text T)$, where $E^\text T = {\{ (v, u) \in V \times V: (u, v) \in E }\}$. Thus, $G^\text T$ is $G$ with all its edges reversed. Describe efficient algorithms for computing $G^\text T$ from $G$, for both the adjacency-list and adjacency-matrix representations of $G$. Analyze the running times of your algorithms.

   

4. What is the running time of $\text{BFS}$ if we represent its input graph by an adjacency matrix and modify the algorithm to handle this form of input?

   

5. The diameter of a tree $T = (V, E)$ is defined as $\max_{u,v \in V} {\{ \delta(u, v) }\}$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.

   

6. Given a graph $G$ and a minimum spanning tree $T$, suppose that we decrease the weight of one of the edges not in $T$. Give an algorithm for finding the minimum spanning tree in the modified graph.

   

7. Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb R$. Give an $O(VE)$-time algorithm to find, for each vertex $v \in V$, the value $\delta^*(v) = \min_{u \in V} {\{\delta(u, v)}\}$.
   • Hint: Modify the Bellman-Ford algorithm.

   

8. Let $Ax \le b$ be a system of $m$ difference constraints in $n$ unknowns. Show that the Bellman-Ford algorithm, when run on the corresponding constraint graph, maximizes $\sum_{i = 1}^n x_i$ subject to $Ax \le b$ and $x_i \le 0$ for all $x_i$.

   

9. Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \le b$ of difference constraints, minimizes the quantity $(\max{x_i} - \min{x_i})$ subject to $Ax \le b$. Explain how this fact might come in handy if the algorithm is used to schedule construction jobs.

   

10. Run the Floyd-Warshall algorithm on the weighted, directed graph given below. Show the matrix $D^{(k)}$ that results for each iteration of the outer loop.