Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #4 -- Due Wed 16 June 1999 : 09.30am -- Answer Key

• Question 1. Write pseudocode and a diagram that shows how to implement the merge part of the merge-sort algorithm using two stacks (one for each subsequence), and be sure to use the correct ADT operations for stacks. Do not write Java code, or pseudocode for merge-sort.
  Answer:
  1. Put the two sorted subsequences to be merged, denoted by S₁ and S₂ on stacks of the same name. Assume that the sorting is in ascending order; hence, each stack has its minimum values at the top of the stack.

  2. The merge algorithm proceeds as follows:

     { repeat until S1 or S2 is empty
       { v1 = pop(S1)
         v2 = pop(S2)
         output(min(v1,v2))
         if (max(v1,v2) = v1) then
           push v1 onto S1
         else 
           push v2 onto S2
         endif
       }
       output the remaining nonempty stack by popping its
         values into the output stream
     }
     

• Question 2. Write pseudocode and a diagram that shows how to implement the insertion-sort algorithm using (a) one stack, and (b) two stacks, with appropriate ADT operations for stacks.
  Answer:
  • Case (a) -- One Stack: The trick is to put the sequence on stack S, then pop off the values until you reach the two that need to be swapped. Assuming that the input is randomly ordered, there is no need to worry about reversing the input. With one stack, you have to have a place to store the values you pop off of S, so an array could be used.

  • The insertion-sort algorithm with one stack proceeds as follows:

    Insertion-Sort1(S: stack)
    { read the input in, pushing each value onto S    # n external I/O ops
      for i = 2 to n do:                              # Bubble up min or max
      { for j = 1 to i-2 do:                          # Get to the test value
          pop values off S and store them in an array # One pop, two mem I/Os
        for j = 1 to i-1 do                           # Bubble-up routine
        { InsTest(S)                                  # 2 pop, 2 psh, 3 I/O, 1 comp
          push onto S the last value put into array   # one push, two mem I/O
      } }
    }  
    
    InsTest(S : Stack)
    { v1 = pop(S)                                    # Stack pop
      v2 = pop(S)                                    # Stack pop
      if v1 and v2 are not in proper order           # Comparison
        then swap(v1,v2)                             # Three I/O ops
      push v2 onto S                                 # Stack push
      push v1 onto S                                 # Stack push
    }      
    
    

  • Case (b) -- Two Stacks: Use the same algorithm as in Case (a), except that one uses an array instead of a stack.

  • The insertion-sort algorithm with two stacks proceeds as follows:

    Insertion-Sort2(S,T: stack)
    { read the input in, pushing each value on S   # n external I/O ops
      for i = 2 to n do:                        # Bubble up the min or max
      { for j = 1 to i-2 do:                    # Get to the test value
          push pop(S) onto T                    # One push, one pop
        for j = 1 to i-1 do                     # Bubble-up routine
        { InsTest(S)                            # 2 pop, 2 push, 3 mem I/O, 1 comp
          push pop(T) onto S                    # One push, one pop
      } }
    }  
    
    InsTest(S : Stack)
    { v1 = pop(S)                               # Stack pop
      v2 = pop(S)                               # Stack pop
      if v1 and v2 are not in proper order      # Comparison
        then swap(v1,v2)                        # Three I/O ops
      push v2 onto S                            # Stack push
      push v1 onto S                            # Stack push
    }      
    
    

• Question 3. Develop a complexity budget for each of the implementations in Question 2 (a and b), above. Compare the complexity of the one-stack and two-stack implementations, and explain why a difference in the count of a given type of operation occurs (one or two sentences per operation type).
  Answer: Work requirements noted in 2(a) and 2(b), above.
  • One-Stack implementation: Requires O(n²) stack operations and array I/O's because i values must be examined in consecutive pairs on the i-th step. Thus, we have the worst-case complexity of the standard insertion-sort algorithm realized here, because the stacks are sequential-access structures (versus random-access structures such as arrays). Comparisons are also O(n²).

  • Two-Stack implementation: Requires O(n²) stack operations, with a proportionality constant for stack operations approximately twice that of the one-stack case, since two stacks are employed. Also, the memory I/Os will be decreased by n(n-1) operations, since the array I/O ops are no longer used. Remaining operations have the same complexity as in the one-stack case.

• Question 4. In class, we discussed how to implement a heap using an array. (a) Implement a heap using two stacks, being sure to preserve both the heap-order and heap-structure property.
  Answer: The key operation for any heap ADT operation is the comparison of a parent's value with the value of its left or right child. To begin, we assume that an input sequence is pushed onto stack S₁ (order doesn't matter, since we assume random input).
  • Trick #1: The stack is a linear structure, so you can view it as a one-dimensional array. Recall class discussion about representing a heap using an array - the root of the heap was at element #1, the two children of the root were at elements #2 and #3. The children of element #2 were at elements #4 and #5, etc. This was generalized such that the left and right children of the i-th array element were at the 2i-th and (2i+1)-th array elements, respectively.

    So, all you have to do to find a parent and its child in the heap is to (1) pop off the first i-1 values until you get to the i-th element where the parent is, then (2) pop off the next i-1 values to get to the left child. The popped values can be pushed onto S₂ until you do the comparison and swap (if required), then the values can be pushed back onto S₁.

  • Trick #2: You need three scalar variables. The first two variables store the parent and child values to be compared. The third variable stores the index of the parent. If you really want to be efficient, you can store the index of the child in a fourth variable. Then you can do the popping and pushing operations outlined in Trick #1, above.

  • Pseudocode: The comparison (and possible swapping) of a parent and its left child can be expressed as follows:

    ComparePLC(S1,S2,i):     
    { P = i                                        # Parent at i-th location
      L = 2i                                       # Left child at 2i-th location
      for j = 1 to P-1 do:                         # Get to the parent value
        push pop(S1) onto S2
      pv = pop(S1)                      # Pop parent value off stack
      for j = 1 to P-1 do:                         # Get to left-child (LC) value
        push pop(S1) onto S2 
      cv = pop(S1)                      # Pop LC value off stack
      if pv is not in the proper order with cv     # Swap pv and cv if required
        then swap(pv,cv)
      push cv onto S1                   # Put cv back onto source stack
      for j = 1 to P-1 do:                         # Put back second set of values 
        push pop(S2) onto S2 
      push pv onto S1                   # Put pv back onto source stack
      for j = 1 to P-1 do:                         # Put back first set of values 
        push pop(S2) onto S1 
    }                                              # Stacks are ok, S2 is empty
    

  (b) Implement the heap ADT operations we discussed in class using the stack-based heap you implemented in Part a of this question.

  Answer: The code for INSERT(x) and DELETE(x) can be expressed in many different ways. Here is one such method for INSERT, without the heap restoration code, which you can adapt from Dr. Sahni's book. That code has not been included, to preserve simplicity of the example. DELETE is symmetrically expressed.

  INSERT(x):
  { while (top(S1) < x) do         # Work = 1 comparison
    { pop p from S1                # Work = 2 mem I/O + one list op
      push p onto S2 }             # Work = 2 mem I/O + one list op
    while (not(isEmpty(S2))) do    # Work = 1 comparison
    { pop p from S2                # Work = 2 mem I/O + one list op
      push p onto S1 }             # Work = 2 mem I/O + one list op
  }  
  

• Question 5. Analyze the complexity of the INSERT and DELETE operations on the stack-based heap you developed in Question 4. Use (a) a complexity budget for each operation, (b) Big-Oh estimates of complexity for each type of operation (e.g., memory I/O, comparison, etc.), and (c) tell why any differences between the counts for each operation type occurred between the INSERT and DELETE operations.
  Answer:
  (a) -- The insertion and deletion operations cost O(1) comparisons and I/O operations per insertion and deletion, as shown in the complexity budget accompanying the code for Question 4b), above.

  (b) -- Each call to ComparePLC or ComparePRC (comparing parent with right-child) costs O(n) stack operations. In the best case, there will be no need to sort the heap, so no swaps will be required. But, one will still have to scrabble down through the source stack to find whether or not the heap is properly ordered. This requires O(n²) stack operations for the entire sequence, not O(n log(n)), as in the case of a graph-based heap (implemented, for example, using an adjacency list representation).

  Since build-heap requires O(n²) stack operations, it follows that each insertion will require O(n log(n)) operations, instead of the usual O(log n) operations in the graph-based heap. A similar comment holds for deletion from the heap.

  (c) -- If INSERT and DELETE are written symmetrically, then they have cost that is the same in terms of Big-Oh notation. In specific cases of insertion and deletion operations, there may be more operations required to restore the heap structure and order properties. On average, however, the complexity is as discussed in Question 5b).

• Question 6. Using the procedure for building a heap that we discussed in class, answer the following questions: (a) what are the general characteristics of the best-case input, (b) what are the general characteristics of the worst-case input, and (c) give an example of a) and b) for building a min-heap.
  Answer:
  (a) When best-case input is pushed onto the stack, the stack values have the heap order property. Note that the heap structure property is arrived at by the scanning property of the stack and the array representation that we assumed in Question 4. This concept was discussed in class.

  (b) When worst-case input is pushed onto the stack, the stack values have the opposite of the heap-order property. That is, if one wants a min-heap, you get a max-heap when the input is pushed onto the stack.

  (c) An example of a best-case input for a min-heap is:

  a = (7,6,5,4,3,2,1) ,

  which gets pushed onto the stack S₁ in reverse order, to yield the min-heap array representation (1,2,3,4,5,6,7) that corresponds to the following diagram:

              1
             / \
            2   3
           / \ / \
          4  5 6  7
  

  An example of the worst case is represented by a = (1,2,3,4,5,6,7), since when pushed onto the stack in reverse, it will form a max-heap (worst case for min-heap construction).

Copyright © 1999 by Mark S. Schmalz.