the disjoint sets class  show  how to implement all three operations so that the sequence of operations takes ( log /log log ntime suppose we want to add an extra operationremove( )which removes from its current set and places it in its own show how to modify the union/find algorithm so that the running time of sequence of unionfindand remove operations is (ma(mn)show that if all of the unions precede the findsthen the disjoint sets algorithm with path compression requires linear timeeven if the unions are done arbitrarily prove that if unions are done arbitrarilybut path compression is performed on the findsthen the worst-case running time is ( log nprove that if unions are done by size and path compression is performedthe worstcase running time is (ma(mn)the disjoint set analysis in section can be refined to provide tight bounds for small show that (mn and (mn are both show that (mn is at most let < choose and show that (mnris at most suppose we implement partial path compression on find(iby making every other node on the path from to the root link to its grandparent (where this makes sensethis is known as path halving write procedure to do this prove that if path halving is performed on the finds and either union-by-height or union-by-size is usedthe worst-case running time is (ma(mn)write program that generates mazes of arbitrary size if you are using system with windowing packagegenerate maze similar to that in figure otherwise describe textual representation of the maze (for instanceeach line of output represents square and has information about which walls are presentand have your program generate representation references various solutions to the union/find problem can be found in [ ][ ]and [ hopcroft and ullman showed an ( lognbound using nonrecursive decomposition tarjan [ obtained the bound (ma(mn))where (mnis as defined in exercise more precise (but asymptotically identicalbound for appears in [ and [ the analysis in section is due to seidel and sharir [ various other strategies for path compression and unions also achieve the same boundsee [ for details lower bound showing that under certain restrictions (ma(mn)time is required to process union/find operations was given by tarjan [ identical bounds under less restrictive conditions have been shown in [ and [ applications of the union/find data structure appear in [ and [ certain special cases of the union/find problem can be solved in (mtime [ this reduces the running time of several algorithmssuch as [ ]graph dominanceand reducibility (see references