DAA-Assignment-2

Question 1

Question 2

Question 3

Question 4

A tree  is the maximum spanning tree of a graph  if  is a spanning tree of  and the weight on the tree  is maximized.

Mr. Smart designs an algorithm to find the maximum spanning tree. Is his algorithm correct?

\begin{algorithm}
\caption{MaxST(G, w)}
\begin{algorithmic}
\Require a connected graph $G = (V, E)$ with a weight function $w: E \to \mathbb{Z}$
\Ensure the maximum spanning tree $T$ of $G$
\State begin
\State $E \gets \text{sort}(E)$ in decreasing order based on $w$
\State $A \gets \{\}$
\ForAll{$u \in V$}
    \State $\text{CREATE-SET}(u)$
\EndFor
\ForAll{$(u, v) \in E$}
    \If{$\text{FIND-SET}(u) \neq \text{FIND-SET}(v)$}
        \State add $(u, v)$ to $A$
        \State $\text{UNION}(u, v)$
    \EndIf
\EndFor
\State \Return $(V, A)$
\State end
\end{algorithmic}
\end{algorithm}

Note that his algorithm is exactly same as Kruskal’s algorithm except that the loop from line 7 to 12 iterates on edges in the decreasing order. (15pts)

I think his opinion is correct.

Definitions

• Heavy Edge: An edge is considered a heavy edge crossing a cut if its weight is the maximum among all edges crossing that cut.
• Safe Edge: An edge is considered safe if its inclusion in the growing forest does not violate the properties of the maximum spanning tree (i.e., it does not create a cycle with edges already included in the MST and its addition results in a spanning tree with the maximum possible total weight).

Proof

Case I: Heavy Edge is Safe Edge

• If the heavy edge is part of the MST, then by definition, it contributes to forming the maximum possible weight of the MST.
• Since it is the heaviest edge across a particular cut and it is part of the MST, it is safe because its exclusion would result in a non-optimal tree (i.e., a tree with less total weight).

Case II: Heavy Edge is Not Safe Edge

• Assume for contradiction that there is a heavy edge$(u,v)$ across a cut which is not included in the MST, implying it is not safe.
• If$(u,v)$ is the heaviest edge crossing the cut and is not included, then to maintain connectivity and maximize total weight, there must be another edge$(x,y)$ through the cut.
• However,$(u,v)$ was defined as the heaviest edge, so no edge$(x,y)$ can have a greater weight than$(u,v)$.
• This leads to a contradiction because it would imply that the current MST is not truly the maximum spanning tree as excluding$(u,v)$ reduces the possible total weight.

Question 5

Given a weighted connect graph $G=(V,E)$, a path from $u$ to $v$ is simple if no vertex on the path is repeated. A simple path is maximum if the length on the simple path is the largest. Such length is called maximum distance from $u$ to $v$ , denoted as $\mathrm{\Delta }(u,v)$.

Mr. Smart designs the following algorithm to find the maximum simple path from one vertices to all other vertices. Is his algorithm correct? Prove your answer.

\begin{algorithm}
\caption{MaxSP(G, w, s)}
\begin{algorithmic}
\Require a connected graph $G = (V,E)$ with a weight function $w: E \rightarrow \mathbb{Z}$, a source vertex $s \in V$
\Ensure the maximum distance $\Delta(s,v)$ for all $v \in V$
\State begin
\ForAll{$u \in V$}
    \State $d[u] \gets \infty$
    \State $color[u] \gets W$
\EndFor
\State $d[s] \gets 0$
\State $pred[s] \gets \text{NULL}$
\State $Q \gets \text{new PriorityQueue}(V)$
\While{$Q$ is not empty}
    \State $u \gets Q.\text{extractMax}()$
    \ForAll{$v \in \text{adj}[u]$}
        \If{$d[u] + w(u,v) > d[v]$}
            \State $d[v] \gets d[u] + w(u,v)$
            \State $Q.\text{increaseKey}(v, d[v])$
            \State $pred[v] \gets u$
        \EndIf
    \EndFor
    \State $color[u] \gets B$
\EndWhile
\State \Return $d[u]$ for each $u \in V$
\State end
\end{algorithmic}
\end{algorithm}

Note that his algorithm is exactly same as Dijkstra’s algorithm except that the priority queue is implemented by a Max Heap. Each round of the loop from line 9 to 19 extract the largest weight edge. And  is updated if . (15pts)

I think his algorithm is not correct.

• When updating distances using the condition $d[u]+w(u,v)>d[v]$, the algorithm attempts to assign new values based on the assumption that there exists a greater path value from $s$ through $u$ to$v$.
• However, since all $d[v]$ are initially $\mathrm{\infty }$, the algorithm's condition will always find that $d[u]+w(u,v)>d[v]$ is false, because you cannot have a real number that is greater than $\mathrm{\infty }$. This results in no updates to $d[v]$ .

Question 6

From the lecture, Mr. Smart knows that Prim’s algorithm runs in $O(elogn)$ time and Kruskal’s algorithm runs in  $O(eloge)$time. Then, Mr. Smart claims that the time complexity of Prim’s algorithm is lower than Kruskal’s algorithm. Is he correct? Prove your answer. (10pts)

I think he is not correct.

Time Complexities

1. Prim's Algorithm: Actually as $O((e+n)\log n)$, where $e$ is the number of edges, and $n$ is the number of vertices.
2. Kruskal's Algorithm: Commonly has a complexity of $O(e\log e)$.

Dense map

• In dense graphs, there are far more edges than vertices, for example $e=n^2$.

The time complexity of Prim's algorithm is $O(n^2\log n)$. The time complexity of Kruskal's algorithm is $O(n^2\log n^2)=O(2n^2\log n)$. In this case, the time complexity of Prim's algorithm is lower than Kruskal's algorithm.

Sparse graph

• In a sparse graph, the number of edges is close to the number of vertices, that is, $e\approx n$.

The time complexity of Kruskal's algorithm is $O(n\log n)$, because the number of edges is small, the sorting burden is relatively light. The time complexity of Prim's algorithm is $O(n+e)\log n)=O(2n\log n)$. In this case, the time complexity of Kruskal's algorithm is lower than that of Prim algorithm.

Conclusion

Therefore, it cannot be said that the time complexity of Prim's algorithm is always lower than that of Kruskal's algorithm.