Introduction to Algorithm Assignment 3

   

  • 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, Friday, June 14, 2024

       

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

   

  1. 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.

   

  1. 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?

   

  1. 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.

   

  1. 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.

   

  1. 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.

   

  1. 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.

floyd_warshall