Java Reference
In-Depth Information
(b) Consider an underflow strategy that cuts the array size in half whenever
the array falls below half full. Give an example where this strategy leads
to a bad amortized cost. Again, we are only interested in measuring the
time of the array copy operations.
(c) Give a better underflow strategy than that suggested in part (b). Your
goal is to find a strategy whose amortized analysis shows that array
copy requires O(n) time for a series of n operations.
14.22 Recall that two vertices in an undirected graph are in the same connected
component if there is a path connecting them. A good algorithm to find the
connected components of an undirected graph begins by calling a DFS on
the first vertex. All vertices reached by the DFS are in the same connected
component and are so marked. We then look through the vertex
mark
array
until an unmarked vertex i is found. Again calling the DFS on i, all vertices
reachable from i are in a second connected component. We continue work-
ing through the
mark
array until all vertices have been assigned to some
connected component. A sketch of the algorithm is as follows:
staticvoidconcom(GraphG){
inti;
for(i=0;i<G.n();i++)//Fornverticesingraph
G.setMark(i,0); //Vertexiinnocomponent
intcomp=1; //Currentcomponent
for(i=0;i<G.n();i++)
if(G.getMark(i)==0)//Startanewcomponent
DFScomponent(G,i,comp++);
for(i=0;i<G.n();i++)
out.append(i+""+G.getMark(i)+"");
}
staticvoidDFScomponent(GraphG,intv,intcomp){
G.setMark(v,comp);
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(G.getMark(w)==0)
DFScomponent(G,w,comp);
}
Use the concept of potential from amortized analysis to explain why the total
cost of this algorithm is (jVj + jEj). (Note that this will not be a true
amortized analysis because this algorithm does not allow an arbitrary series
of DFS operations but rather is fixed to do a single call to DFS from each
vertex.)
14.23 Give a proof similar to that used for Theorem 14.2 to show that the total
number of comparisons required by any series of n or more searches S on a
self-organizing list of length n using the count heuristic is never more than
twice the total number of comparisons required when series S is applied to
the list stored in its optimal static order.
