CS 535 Design and Analysis of Algorithms

1.    Show that the algorithm requires O(n) expected time.

The algorithm is similar with algorithm in lecture16, but it is different since in lecture  16, it should consider both two partitions, but in this algorithm, we only consider one partition.

T(n) = T(n/2) +cn

=T(n/4)+cn/2+cn

=T(n/8)+cn/4+cn/2+cn

=……

=T(n/n)+2+4+…+cn/2+cn

Which is sum of geometric sequence, so

T(n) = 2cn = O(n)

2.    Give a polynomial-time randomized algorithm whose expected number of edges it satisfies should be at least 2/3c*

The algorithm can be designed as that color each node with random color selected from three

colors, which should be selected uniformly and independently. Then the expected number of edges it satisfies should be at least 2/3c*

Prove: since the color for each node is colored randomly, so for each edge e in the Graph, the probability of e which is satisfied is 2/3. Define a Xe as the variable if edge is satisfied, then the expectation of total number edges which is satisfied is:

E[∑e∈E Xe] = ∑e∈E E[Xe] = ∑e∈E P  = (2/3)*|E|

Since the maximizes the number of satisfied edges is c*, so c* <= |E|.

So E[∑e∈E Xe]>=(2/3)c*

The expected number of edge it satisfies is at least (2/3)c*

3.    For any Bi-connected graph G = (V,E), prove that all three properties list below are equivalent.

For abiconnected graph, it is defined that removing any edge from the graph will not disconnect it into two unconnected parts.

(1)  Removing any one vertex cannot disconnect the graph. Remove ant one vertex means remove at least one edge in the graph, so removing any one vertex cannot disconnect the graph means remove any vertex x, there is other edges connected each other which reached from x.

(2)  Between any pair of vertices u, v   ∈ V , there exist at least two vertices-disjoint paths. If there is only one path from u to v, then remove one vertex either u or v, the connection from u to v will be disconnected, which will be contradicted with (a).

(3)     For each pair of nodes u, v∈V, there exists a simple cycle connecting u and v. if there is no any cycle connecting u and v, which means that remove any vertex either u or v will disconnect the graph, and there is only one path connect u and v, which us contradicted with both (a) and (b).

So (1), (2), (3) are equivalent

4.    Show that an edge(u, v) in E and in the DFS tree is a bridge if and only if lowpt(v)   =  dfsno(v). First show if (u,v) is a bridge, then lowpt(v) >= dfsno(v):

(u,v) is a bridge,then if remove it, the graph will be disconnected, which means (u,v)is the only edge which connect node u and v. In DFS tree, (u,v) is the DFS tree edge, which means u is the parent of v. so v is visited from u in DFS, so dfsno(v) > dfsno(u). based on definition, lowpt(v)represents the lowest DFN of anode that can be reached from v, including v itself, since v is visited from u, no other nodes with lower dfsno than v can reach to v, so lowpt(v) >= dfsno(v), so

lowpt(v)>= dfsno(v)

Next, show if lowpt(v) >= dfsno(v), then (u,v) is a bridge.

lowpt(v) >= dfsno(v), it means no edge from v to lower dfsno node, which means there is no back edges or crossedgein the DFS tree from v. In other words, all the edges in the subtree are either tree edges or forward edges. This implies that there is no other way to reach v from its subtree without using the edge (u, v), so if (u,v) is removed, the graph will be disconnected.

5.    In DFS of a strongly connected graph, prove that a vertex is a root of a subtree that corresponds to a strongly connected component if and only if lowpt(v) = Dfsno(v).

First, if v is a root of a subtree that corresponds to a strongly connected component, then lowpt(v) = dfsno(v).

Since v is root of subtree that corresponds to a strongly connected component, then any node in this subtree can be reached from other node, DFS tree visited other nodes from v in this subtree. Sodfsno v is the smallest value in this subtree. Based on lowpt definition, lowpt(v) is the smallest dfsno of the nodes which v can be reachable, including v. so dfsno(v) = lowpt(v).

Next,prove that if lowpt(v)= dfsno(v), then vis the root of the subtree that corresponds to a strongly connected component.

If lowpt(v) == dfsno(v),it means that others nodes in this subtree with larger dfsno can reach this node in DFS tree,which means that there are no back edges or cross edges in the subtree rooted at vv, and all edges in the subtree are either tree edges or forward edges. So v is the root of subtree in DFS of a strongly connected graph