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