Chapter 19, Problem 1P

(a)

Program Plan Intro

Explain the assumption that Line 7 can be performed in O(1) actual time.

Explanation of Solution

For performing line 7, the time taken is proportional to the number of children does x have. For adding each child in the root list requires to update the parent’s pointer to NULL instead of x.

Therefore, the updating of parent pointer to x is wrong in this assumption.

(b)

Program Plan Intro

Give anupper bound on the actual time of PISANO-DELETE, when node x is not inH.min .

Explanation of Solution

An actual cost of bounded by x.degree and updating all children of x takes constant time so, the actual time of PISANO-DELETE is $O(x.\mathrm{deg}ree+c)$ , where c is number of calls to CASCADING-CUT procedure.

Hence, the upper bound on the actual time is $O(x.\mathrm{deg}ree+c)$ .

(c)

Program Plan Intro

Use PISANO-DELETE( H,x ), describe that the node x is not a root, bound the potential of H’ in terms of x.degree, c, t ( H ) and m ( H ).

Explanation of Solution

Explanation:

As given CASCASDING-CUT rule we know that if it marked more than one node then $m(H\text{'})\le m(H)+1$ .

If the children increased from the previous that x had then equation will become $t(H\text{'})=x.\mathrm{deg}ree+t(H)$ .

Now taking the consideration and according to question, combiningthese expressions the bound of potential is − $\varphi (H\text{'})\le t(H)+x.\mathrm{deg}ree+2(1+m(H)).$

(d)

Program Plan Intro

Conclude that the amortized time for PISANO-DELETE is asymptotically no better than for FIB-DELETE, even when x $\ne$ H.min.

Explanation of Solution

The amortized time for PISANO-DELETE is asymptotically is $\theta (x.\mathrm{deg}ree)=\theta (\lg n)$ .

When x $\ne$ H.min then the time taken in FIB-DELETE is also $\theta (\lg n)$ which same as the time is taken for PISANO-DELETE.

Therefore, the amortized time for PISANO-DELETE is asymptotically no better than for FIB-DELETE, even when x $\ne$ H.min.