CS5800-Homework 7 Solved

1             Simple Data Structure
1.1           Stack and Queue
Both are dynamic sets in which the element removed from the set by DELETE operation is prespecified. In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out. or LIFO, policy. In a queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first-out, or FIFO, policy.

1.2           Linked list
A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.

1.3       Representing rooted trees

Binary tree and rooted trees with unbounded branching.

2             Binary Search Tree
Basic operation on a binary search tree take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations run in Θ(lgn) worst-case time. If the tree is a linear chain of n nodes, however, the same operations take Θ(n) worst time.

2.1           What is a binary tree
Theorem 12.1: If x is the root of an n-node subtree, then the call INORDERTREE-WALK(x) takes Θ(n) time.

2.2           Querying a binary search tree
Theorem 12.2: we can implement the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR so that each one runs in Ø(h) time on a binary search tree of height h.

2.3           Insertion and deletion
Theorem 12.3: we can implement the dynamic-set operations INSERT and DELETE so that each one runs in O(h) time on a binary search tree of height h.

2.4           Randomly built binary search trees
Theorem 12.4: The expected height of a randomly built binary search tree on n distinct keys is O(lgn).

3             Exercise 10.1-1
 

Figure 1: image

4             Exercise 10.1-4
When Q.head = Q.tail = 1, the queue is empty, and if we attempt to dequeue an element then the queue underflows. When Q.head = Q.tail + 1, the queue is full, and if we attempt to enqueue an element then the queue overflows.

 

Algorithm 1 Enqueue and dequeue

 

1: function Enqueue(Q,x)

2:                      if Q.head == Q.tail + 1 or (Q.head == 1andQ.tail == Q.length) then

3:                       error”overflow”

4:             end if

5:               Q[Q.tail] = x

6:                 if Q.tail == Q.length then

7:                      Q.tail = 1

8:             else

9:                        Q.tail = Q.tail + 1

10:           end if

11: end function

12:

13: function Dequeue(Q)

14:                if Q.head == Q.tail == 1 then

15:                    error”underflow”

16:           end if

17:            x = Q[Q.head]

18:              if Q.head == Q.length then

19:                    Q.head = 1

20:          else

21:                     Q.head = Q.head + 1

22:           end if

23:            return x

24: end function

 

5             Exercise 10.1-6
 

Algorithm 2 Implement a queue using two stacks

 

1: function Enqueue-Stack(stack1,stack2,value)

2:              stack1.push(value)

3: end function

4:

5: function Dequeue-Stack(stack1,stack2)

6:               if stack2 is not empty then

7:                      return stack2.pop()

8:             else

9:                      while stack1 is not empty do

10:                           stack2.push(stack1.pop())

11:                   end while

12:                    if stack2 is empty then

13:                           return −1

14:                  else

15:                           return stack2.pop()

16:                   end if

17:           end if

18: end function

 

The operation ENQUEUE-STACK is same as pushing an element on to stack 1 and it takes O(1). For DEQUEUE-STACK. we pop an element from stack 2 if stack 2 is not empty; Otherwise, for each element in stack 1 we pop it off, then push it on to stack 2 and finally pop the top item from stack 2. This operation is O(n) in the worst-case.

6             Exercise 10.1-7
 

Algorithm 3 Implement a stack using two queues

 

1: function Push-Queue(queue1,queue2,value)

2:              if queue2 is empty then

3:                        Enqueue(queue1,value)

4:             else

5:                        Enqueue(queue2,value)

6:             end if

7: end function

8:

9: function Pop-Queue(queue1,queue2)

10:            if queue1 is empty and queue2 is empty then

11:                   return −1

12:          else

13:                    DelData ← 0

14:                    if queue2 is not empty then

15:                           len ← queue2.length

16:                            while len > 1 do

17:                                      DelData ← Dequeue(queue2)

18:                                      Enqueue(queue1,DelData)

19:                          end while

20:                              DelData ← Dequeue(queue2)

21:                            return DelData

22:                   end if

23:                    if queue1 is not empty then

24:                           len ← queue1.length

25:                            while len > 1 do

26:                                      DelData ← Dequeue(queue1)

27:                                      Enqueue(queue2,DelData)

28:                          end while

29:                              DelData ← Dequeue(queue1)

30:                            return DelData

31:                   end if

32:           end if

33: end function

 

The implementing a stack using two queues, where pop takes O(n) time and push takes O(1) time. The operation PUSH-QUEUE is same as enqueueing each element as we push it. For POP-QUEUE, we dequeue each element from one of the queues and enqueue another queue in the order, but stopping just before the last element. Then, the single element left in the original queue.

7             Exercise 10.2-2
 

Algorithm 4 Implement a stack using a single linked list

 

1: function Push-List(L,x)

2:               x.next = L.head

3:                 if L.head ̸= NIL then

4:                       L.head.prev = x

5:             end if

6:               L.head = x

7:                x.prev = NIL

8: end function

9:

10: function Pop-List(L,L.head)

11:             x ← L.head

12:               if x.prev ̸= NIL then

13:                      x.prev.next = x.next

14:          else

15:                     L.head ← x.next

16:           end if

17:               if x.next ̸= NIL then

18:                     x.next.prev = x.prev

19:           end if

20: end function

 

The PUSH-LIST operation is same as linked list insertion, and POP-LIST operation is same as linked list deletion.

8             Exercise 10.2-6
This can be implemented by doubly linked list. If both sets are a doubly linked list, we just link the last element of the first list to the first element in the second list. Wherever we have a reference to NIL in list code, we replace it by a reference to the sentinel L.nil lies between the head and tail. .

 

1: function List-Union(L1,L2)

2:                 L2.nil.next.prev = L1.nil.prev

3:                 L1.nil.prev.next = L2.nil.next

4:                 L2.nil.prev.next = L1.nil

5:                 L1.nil.prev = L2.nil.prev

6: end function

 

9             Exercise 10.4-2
 

Algorithm 5 Prints out the key of each node in the binary tree

 

1: function Inorder-Tree-Walk(x)

2:                if x ̸= NIL then

3:                             Inorder-Tree-Walk(x.left)

4:                      print x.key

5:                            Inorder-Tree-Walk(x.right)

6:             end if

7: end function

 

10             Problem 10-1 Comparisons among lists
 
unsorted, singly linked
sorted, singly linked
unsorted, doubly linked
sorted, doubly linked
SEARCH(L,x)
O(n)
O(n)
O(n)
O(n)
INSERT(L,x)
O(1)
O(1)
O(1)
O(1)
DELETE(L,x)
O(n)
O(n)
O(1)
O(1)
SUCCESSOR(L,x)
O(n)
O(1)
O(n)
O(1)
MINIMUM(L)
O(n)
O(1)
O(n)
O(1)
MAXIMUM(L)
O(n)
O(n)
O(n)
O(1)
11             Exercise 12.2-5
Suppose the node x has two children, its predecessor is the maximum value in its left subtree and its successor is the minimum value in its right subtree. If the successor of node x had s left child then it wouldn’t be the minimum element. Depending on the property of binary tree, the successor must not have a left child. Similarly, the predecessor must not have a right child.

12             Exercise 12.2-7
 

Algorithm 6 Finding the successor

 

1: function Tree-Minimum(x)

2:                 while x.left ̸= NIL do

3:                        x = x.left

4:          end while 5:   return x

6: end function

7:

8: function Tree-Successor(x)

9:                 if x.right ̸= NIL then

10:                       return Tree-Minimum(x.right)

11:           end if

12:            y ← x.p

13:                 while y ̸= NIL and x == y.right do

14:                    x = y

15:                    y = x.p

16:          end while 17: return y

18: end function

 

A call to TREE-MINIMUM followed by n − 1 calls to TREE-SUCCESSOR performs the same procedure as INORDER-TREE-WALK does. The algorithm traverse each edge at most twice (once going down the tree and once going up), which takes Θ(n) time. The only time the tree is traversed downward is in code of TREE-MINIMUM, and the only time the tree is traversed upward is in code of TREE-SUCCESSOR when we look for the successor of a node that has no right subtree. Therefore, this algorithm runs in Θ(n) time.

13             Exercise 12.3-3
 

Algorithm 7 Sort a given set of n numbers by first building a binary search tree

 

1: function Tree-Insert(T,x)

2:               y ← NIL

3:              x ← T.root

4:                while x ̸= NIL do

5:                      y ← x

6:                        if z.key < x.key then

7:                               x = x.left

8:                     else

9:                               x = x.right

10:                   end if

11:           end while

12:            z.p ← y

13:               if y == NIL then

14:                    T.root = x

15:          else

16:                     if z.key < y.key then

17:                             y.left = z

18:                  else

19:                            y.right = z

20:                   end if

21:           end if

22: end function

23:

24: function Inorder-Tree-Walk(x)

25:              if x ̸= NIL then

26:                           Inorder-Tree-Walk(x.left)

27:                   print x.key

28:                          Inorder-Tree-Walk(x.right)

29:           end if

30: end function

31:

32: function Tree-Sort(x)

33:            let T be an empty binary search tree

34:             for i = 1 to n do

35:                        Tree-Insert(T,x)

36:           end for

37:                  Inorder-Tree-Walk(T.root)

38: end function

 

The worst-case is that we were inserting in already sorted order, therefore, the worst-case takes Θ(n2). In the best-case, the tree is balanced, which means the height doesn’t exceed O(lg(n)), so the best-case takes Θ(nlg(n)).