Class Notes: COP3530

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 #3 -- Due Thu 10 June 1999 : 09.30am

This is the key for Homework #3. Answers are in blue typeface.

Question 1. Given an 8-element sequence S = (3, -10, 4, -3, 8, 6, 5, 1), diagram the merge-sort tree (architecture) for the divide, sort, and conquer phases of the merge-sort algorithm, as we did in class. Label each level (e.g., L1, L2, etc.), as you will need this information in Question 2. Do not write code for merge-sort.

Answer:

Level 1                  (3, -10, 4, -3, 8, 6, 5, 1)
                             /                  \
Level 2           (3, -10, 4, -3)            ( 8, 6, 5, 1)
                    /         \               /         \
Level 3       (3, -10)       (4, -3)      (8, 6)       (5, 1)
                  X             X           X            X
SORT          (-10, 3)       (-3, 4)      (6, 8)       (1, 5)
                    \         /               \        /
Level 2'          (-10, -3, 3, 4)            (1, 5, 6, 8)
                             \                  /
Level 1'                 (-10, -3, 1, 3, 4, 5, 6, 8)

Question 2. Produce a budget of computational work for the sorting architecture you developed in Question 1. For example, the number of operations (e.g., external I/O, additions, memory I/O, comparisons, incrementations, etc.) (b) Given this budget, produce a Big-Oh estimate of complexity, and show the assumptions you used to arrive at that estimate.

Answer:

STAGE      EXT.I/O   MEM I/O   COMPARISONS  COMMENT
-------    -------   -------   -----------  ----------------------
Level 1       n                             Read in n data
Level 2                 n                   Split into n/2 per part
Level 3                 n                   Split into n/4 per part
SORT                    n          n/2      All subseq's. reversed
Level 2'                n       2(n/2 - 1)  Merge four n/4-element seq's
Level 1'                n          n-1      Merge two  n/2-element seq's
Output        n                             Optional output of n data
-------    -------   -------   -----------  
TOTAL        2n        5n        5n/2 - 3

Big-Oh:  O(n log n) in I/O ops, O(n) in comparisons

Question 3. Given a 7-element sequence S = (-60, -3, 4, 1, 0, -1, 2) diagram the sorting architecture (divide-and-conquer) for quick-sort using as a pivot the (a) mean, (b) median, and (c) average of lowest and highest values for S and each of the lower-level subsequences employed in the quick-sort algorithm. Do not write code for quick-sort.

Answer:

Case 1: Mean Pivot

Level 1                  (-60, -3, 4, 1, 0, -1, 2)         mean = -57/7 = -8.14
                             /                  \
Level 2                 (-60)    (-3, 4, 1, 0, -1, 2)      mean = 0.5
                        |           /             \
Level 3                 |   (-3, -1, 0)        (4, 1, 2)   mean = -1.33, 2.3
                        |    /       \           /    \
Level 4                 | (-3)     (-1, 0)    (1,2)   (4)
SORT                    V   |        |  |      | |     |
Level 4'              (-60)(-3)    (-1, 0)    (1,2)   (4)
                         \  /           \      /       |
Level 3'               (-60,-3)        (-1,0,1,2)      |
                             \             /           |
Level 2'                  (-60, -3, -1, 0, 1, 2)       |
                                        \              /
Level 1'                          (-60, -3, -1, 0, 1, 2, 4)      


Case 2: Median Pivot

Level 1                  (-60, -3, 4, 1, 0, -1, 2)         median = 0
                             /                  \
Level 2                 (-60,-3,-1)          (0,1,2,4)     median = -3, 2
                         /     \              /     \
Level 3               (-60) (-3, -1)       (0,1)    (4,2)  
SORT                    |     |   |         | |       X
Level 3'              (-60) (-3, -1)       (0,1)    (2,4)  
                         \  /                 \      /    
Level 2'               (-60,-3,-1)            (0,1,2,4)
                               \                /
Level 1'                  (-60, -3, -1, 0, 1, 2, 4)      


Case 3: Pivot as Average of Extrema

Level 1                  (-60, -3, 4, 1, 0, -1, 2)         pivot  = (4-60)/2 
                          /                     \                 = -38
Level 2               (-60)             (-3,-1,0,1,2,4)    pivot  = (-3+4)/2
                        |                    /     \              = 0.5
Level 3                 |          (-3, -1, 0)   (4, 1, 2) pivots = -1.5, 3
                        |           /     \        /   \
Level 4                 |       (-3,-1)   (0)   (1,2)  (4) 
SORT                    |        |   |     |     | |    |
Level 4'                |       (-3,-1)   (0)   (1,2)  (4) 
                        V       /           \    /      |
Level 3'              (-60,-3,-1)           (0,1,2)     |
                               \              /         |
Level 2'                  (-60, -3, -1, 0, 1, 2)        |
                                         \              V
Level 1'                         (-60, -3, -1, 0, 1, 2, 4)

Question 4. Analyze the complexity of the algorithm for each of the three cases you developed in Question 3, in the same way as required in Question 2. Based on in-class discussion, what would be the optimal choice of pivot for S, and why?

Answer:

Case 1: Mean Pivot

STAGE      EXT.I/O   MEM I/O   COMPARISONS  COMMENT
-------    -------   -------   -----------  --------------------------
Level 1       n                             Read in n elements
Level 2                 n           n       First split operation
Level 3                n-1         n-1      Second split operation
Level 4                n-1         n-1      Third split operation
SORT                                1       Check for swap (not needed)
Level 4'                0           0       Carry over values from SORT
Level 3'               n-1                  Concatenation (new array or list)
Level 2'               n-1                  Concatenation (new array or list)
Level 1'               n-1                  Concatenation (new array or list)
-------    -------   -------   -----------
TOTAL         n       5n-5         3n

Big-Oh: O(n²), since there are n ops at each of 
            ceil(n/2) levels

Case 2: Median Pivot

STAGE      EXT.I/O   MEM I/O   COMPARISONS  COMMENT
-------    -------   -------   -----------  --------------------------
Level 1       n                             Read in n elements
Level 2                 n           n       First split operation
Level 3                 n           n       Second split operation
SORT                    2           3       Only one swap operation
Level 3'                n                   Concatenate n/4-element seq's
Level 2'                n                   Concatenate n/2-element seq's
Level 1'                n                   Produce n-element sequence
-------    -------   -------   -----------  
TOTALS        n        5n+2       2n+3

Complexity: O(n log n) comparisons and I/O's

Case 3: Pivot as Average of Extrema

STAGE      EXT.I/O   MEM I/O   COMPARISONS  COMMENT
-------    -------   -------   -----------  --------------------------
Level 1       n                             Read in n elements
Level 2                 n           n       First split operation
Level 3                n-1         n-1      Second split operation
Level 4                n-1         n-1      Second split operation
SORT                    0           2       Two tuples, No swaps
Level 4'                0                   Pass-through of swap results
Level 3'               n-1                  Concatenate n/4-element seq's
Level 2'               n-1                  Concatenate n/2-element seq's
Level 1'                n                   Produce n-element sequence
-------    -------   -------   -----------  
TOTALS        n        6n-4        3n

Complexity: O(n²) memory I/O

Question 5. Given a 7-element sequence S = (9, 4, -3, 6, 8, 12, -14), diagram the insertion-sort tree (architecture), as we did in class. Label each level of the tree. Do not write code for insertion-sort.

Answer:

INPUT   i=2    i=3    i=4    i=5    i=6     i=7
-----   ---    ---    ---    ---    ---     ---
   9      9  \/  4  \/ -3     -3     -3 +-> -14
   4 ____ 4  /\  9\//\  4      4      4 |    -3
  -3     -3 ____-3/\    9  \/  6      6 |     4
   6      6      6 ____ 6  /\  9  \/  8 |     6
   8      8      8      8 ____ 8  /\  9 |     8
  12     12     12     12     12 ____12 |     9
 -14    -14    -14    -14    -14    -14/ ___ 12
-----   ---    ---    ---    ---    ---     ---
#Compares    2     3       2      2     6
#Swaps       1     2       1      2     6

TOTAL:  # Compares = 15 = O(n²)
        # Swaps    = 12 = O(n²)

Question 6. Repeat Question 4 for the sorting architecture diagrammed in Question 5.

Answer:

See Question 5, above. Note: Ask the TAs if you have questions about the homework. You must complete the homework by yourself, but you can work together on general approaches to solving the homework problems. Show your work to get full credit. Any copying will be construed as cheating.