Assignment 3 - Solutions.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

Ø - / + * + * 6 + 3 - 2 3 - Ø Ø 3 1 Ø Ø 9 5 Ø Ø Ø Ø 7 4 Ø Ø Ø Ø

2:
In preorder traversing the root of the tree is visited first and then the subtrees rooted rooted at children are pre order traversed in their order in the tree.But in postorder traversing the subtrees rooted at the children of root are traversed in post order first and then the root.T is an ordered tree with more than one node.In any case , in preordering the root is visited first and in post ordering the root is visited last.So it is not possible that the preorder traversal of tree T visits the nodes in the same order as the post order traversal of T.

But it is possible that the preorder traversal of T visits the nodes in the reverse order of the postorder traversal.Consider following example.
A tree in which all nodes have one child or zero child.In this case the preorder traversing is just the reverse of postorder traversing.

3:
T is a balanced binary tree since all the external nodes have the same depth.
   Let 'h' be the height of the tree.
All the external nodes are at depth 'h'.
no of external nodes in T = 2^h .
^{De = sum of depth of all extrenal nodes
of T}
= h .2^h
Di = sum of depth of all internal nodes of T
   = (h-1) .2^{h -1} +   (h -2) .2^{h -2} + (h - 3) .2^h + .......... + (h - h) .2^{h - h}
= (h-1) .2^{h -1} +   (h -2) .2^{h -2} + (h - 3) .2^h + .......... + 0 .2⁰

= (h-2) .2^h+ 2

       = h.2^h- 2 .2^h+   1 + 1   =   h.2^h+   1- 2 .2^h+ 1
       =   De + 1 - 2 .2^h+ 1
De + 1 = D i   + 2 .2^h- 1 = D i   + 2^{h + 1}- 1

We know , total number of nodes in T is n = 2^{h + 1}- 1

So De + 1 = Di + n ----(1)

Given De + 1 = a .Di + b. n ---- (2)

From (1) and (2)

a = 1 and b = 1.

4.
Algorithm :PreorderNext( T ,v)

          if isInternal(T, v)
                then next <- LeftChild(v)
          else if isLeftChild(T,v)
                then next <- RightChild(Parent(v))
                else
                     while isRightChild(parent(v))
                               do v <- parent(v)
                      v <- parent(v)
                      next <- RightChild(Parent(v))
         return next

In worst case the while loop executes height of the tree times.So worst case running time is O(lgn).

Algorithm InorderNext(T, v)

        if isExternal(T, v)
             then if is LeftChild(v)
                      then next <- parent(v)
                     else
                           while isRightChild(parent(v))
                                do v <- parent(v)
                          next <- parent(parent(v))
         else
              v <- rightChild(v)
               if isExternal(T,v)
                   then next <- v
               else
                    while isInternal(T,v)
                         do v <- leftChild(v)
                     next <- v
          return next

The worst case running time is O(lgn)

Algorithm PostorderNext(T , v)

    if   isExternal(T,v)
        then if isRightChild(v)
                then next <- parent(v)
                else
                      v <- rightChild(parent(v))
                      while(isInternal(v))
                           do v <- leftChild(v)
                       next <- v
    else
            if isRightChild(v)
                 then next <- parent(v)
              else
                   v <- rightChild(parent(v))
                      while(isInternal(v))
                           do v <- leftChild(v)
                       next <- v
   return next

The worst case running time is O(lgn)

5.
Algorithm FIND_LCA(T, v , w)
         dv <- depth (v);
        dw <- depth(w);
         if dv > dw
             then i <- dv - dw
              while i > 0
                   do v <- parent(v)
                   if v = w then
                         lca <- w
                          return lca
                    else i <- i -1
          else if dw > dv
                 then i <- dw - dv
                 while i > 0
                   do w <- parent(w)
                   if w = v then
                         lca <- v
                          return lca
                   else
                      i <- i -1
          while v != NIL and w != NIL
                   do v <- parent(v)
                         w <- parent(w)
                         if u = w then
                               lca <- u
                                return lca

Analysis
depth() takes O(n) time . It is executed twice in this algorithm. So O(2n) . parent() takes O(1) time. In the worst case , when v and are leaf nodes in two differnt path and root is their LCA , then parent () is called 2n times. So total time for parent() is Theta(2n).
So total running time of this algorithm is O(2n + 2n ) = O(n).

6.
If S's array is not circular then removing the first element requires moving all other elements in the array to the back by one position.
So the running time is O(n).If the elements inserted to the array are arranged in descending order , then minimum element comes as the last element. The last element can be removed in O(1) time in circular and non-circular implementation of the array.If the priority queue uses a sequence with this implementation , then removeMin runs in constant time in both cases.

7.
Consider an input sequence of 'n' already sorted in ascending order.
eg: (1, 2, 3, 4, 5 , 6, 7, 8, 9, 10 ,.......n)
So time taken for each insertion into the priority queue in Insertion sort is in the order of number of elements already in the priority queue.So for ' n' such insertion , time taken

O(£ⁿ_{i =1}i) = n(n + 1) / 2 = O(n²)
The removeMin() takes O(1) time.There are n removals So total time for removals O(n)
So total running time is O(n²+ n) = O(n²)

input sequence ( 2,5, 16,4, 10,23, 39 , 18, 26 , 25)
In Heap sort , a priority queue is implemented using the heap.First all th elements are inserted into the priority queue.Then removeMin() is called n times where n is the number of elements in the sequence.Initially we make the heap , root of the heap is 2 .we swap that with the last node in the heap ie 25 and decreases the size of the heap by 1.Again we bubble down 25 to proper position.This procedure is repeated till the heap size is one. So the output sequnce is ( 2,4,5,10,16,18,23,25,26,39)

You can show this using the diagram.

10.
For any n we can create a sequence of insertions such that all the entries are arranged in decreasing order of their key values.
So for each insertion , the key of the node to be inserted is lower than all nodes in the heap.So this newly inserted node has to be
bubbled up to the root.This operation is proportional to the height of the tree. ie 'logn ' there are n such insertions .So time to process is 'nlogn'.However the height of the heap is not always the same because the 'n', no of elements in the heap is different in each insertions..It starts from zero and gradually increases to logn.So we can upper bound the time to process to nlogn.ie time to process = Theta(nlogn).

Algorithm Find_Smallest(k):
Step 1: make the heap using the Bottom-Up Heap procedure. ----O(n)

    Step 2: while k > 0
                   remove root from the heap --------O(1)
                   replace that with the last node in the heap -----O(1)
                   bubble down the replaced node . -------O(lgn)

Step 3:
return k

The running time is O(n + klgn) .