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

Exam #1 -- Solutions (in blue type)

• Question #1 (10 points): Given the input vector (-10,23-14,-2,5,43,1,-94), diagram the merge (not mergesort) procedure used in the left-hand branch of Level 1 of the Merge-Sort algorithm:

        (-10,23,14,-2)     # Divide step: Level 1
            /    \
     (-10,23)    (14,-2)   # Divide step: Level 2
       |  |         X      # Sorting tuples
     (-10,23)    (-2,14)   # Conquer using merge
            \    /
        (-10,-2,14,23)
  

  Write pseudocode for the merge-sort procedure:
  Assuming that the Merge routine exists, we have

  MergeSort(a,n):
  { if size(a) = 1 then return(a)
    elseif size(a) = 2 then
      if a[1] and a[2] are not in proper order, then
        swap(a[1],a[2])
      endif
    else 
    { split a into two lists of equal size, L and R
      return(Merge(MergeSort(L,n/2),MergeSort(R,n/2))) }
    endif
  }
  

• Question #2 (10 points) Given the following list, (1) show in detail (with sketch that has numbered steps, and with p-code) the steps involved when inserting a new list element with datum "B" between nodes with data "C" and "D", where H and T denote the head and tail of the list, and (2) produce a complexity budget for each step, and for the total work involved in insertion.

  +---+--+   +--+---+--+   +--+---+--+   +--+---+--+   +--+---+
  |   |  |<--+-o|   |  |<--+-o|   |  |<--+-o|   |  |<--+-o|   |
  | H |  |   |  | A |  |   |  | C |  |   |  | D |  |   |  | T |
  |   |o-+-->|  |   |o-+-->|  |   |o-+-->|  |   |o-+-->|  |   |
  +---+--+   +--+---+--+   +--+---+--+   +--+---+--+   +--+---+
  

  Answer:

  Step 1: Make new list element el.
  Work = 1 "new" operation.

  Step 2: el.value <- B
  Work = 1 memory I/O

  Step 3: el.prev <- ElementAt(2)
  Work = 3 mem. I/O

  Step 4: el.next <- ElementAt(3)
  Work = 4 mem. I/O

  Step 5: el.prev.next <- el
  Work = 1 mem. I/O

  Step 6: el.next.prev <- el
  Work = 1 mem. I/O

  Total Work = 10 memory I/O ops + 1 "new" operation

• Question #3 (5 points): What is the worst-case input for quick-sort? Why? You must illustrate your answer with a brief example (an 8-element vector will do).

  Answer:

  • Worst-case input causes splitting of n-element sequence into one element and an n-1 element subsequence on the first step, with a one element subsequence and an n-i element subsequence on the i-th step, for 1 < i < n.

  • This splitting causes an n-level tree to be formed, which has a maximum of O(n) work at each level, for O(n²) complexity of quick-sort.

  • Example: (10¹⁶, 10¹⁴, 10¹², 10¹⁰, 10⁸, 10⁶, 10⁴, 10²) with pivot at the mean of each sequence or subsequence.

• Question #4 (5 points) In class, we discussed selection algorithms whose input was a sorted sequence of numbers. Give a one- or two-sentence explanation of why such sorting is required.

  Answer:

  Such sorting is required in binary search tree construction, to establish an order property that, together with the tree structure, constrains the search process to O(log n) complexity.

• Question #5 (5 points): Given the worst-case input described in Question 3, how will the insertion-sort versus merge-sort process be affected by this input? Your answer should be 1-2 sentences for each sorting algorithm, accompanied by a sketch that uses an eight-element input.

  Answer:

  • Merge-Sort complexity will be minimum if sorting is in the same order as the input sequence, since the swap operation will not be required at the sorting step (after splitting of the input sequence into two-element subsequences). However, the merge-sort architecture, as well as the number of comparison operations, is not affected by the input configuration. Merge-sort complexity thus remains O(n log n) regardless of the input ordering.

  • Insertion sort complexity is O(n) comparisons for sorting an input sequence that is presorted in the same order as the sort. If the input sequence is presorted in the opposite order, then O(n²) comparisons are required.

  • Examples of the best- and worst-case inputs for merge-sort and insertion-sort were given in class.

• Question #6 (5 points): What is the maximum number of comparison and I/O operations required to find the value closest to the mean in the sequence S = (-1,3,4,-2,2,3,1,-4)?

  Answer:

  • Mean = (-7 + 13)/8 = 6/8 = 3/4 = 0.75.

  • Value closest to mean = 1.0, the 7th value in S.

  • Work for mean: n-1 adds + 1 multiplication = 7 adds + 1 mult.

  • Work for difference of mean and value in S: n = 8 adds

  • Work for comparison of differences: n = 8 comparisons

  • Total work W(n) = 15 additions + 8 comparisons + 1 multiplication

• Question #7 (10 points): In each of the following cases, state which (a-c) is a heap or is not a heap. If it is not a heap, (a) state why, and (b) make it into a heap by rearranging values or nodes.

  Answer:

  (a)    5     Not a heap, since    (i)  1   Swap      (ii)  1    Swap 
        / \    5 > 1 < 6 .              / \   1&5           / \   2&5
       1   4                           5   4               2   4
      / \                             / \                 / \     MIN-
     6   2                           6   2               6   5    HEAP
  
  (b)    6     Is a MIN-HEAP
        / \    
       7   8   
      / \   \  
     8   9   10
  
  (c)    22    Not a heap, since    (i)  22   Rotate   (ii)  46    Swap 
        / \    22 < 46 > 21              / \   Left          / \   46&22
       13  46  violates heap-order     46   13             22  13  
           / \                        / \                  / \     MAX-
         12  21                      21  12              21   12   HEAP
  

Copyright © 1999 by Mark S. Schmalz.