m4_divert(2) m4_define(_commentnesting, 0) m4_define(_begincomment,m4_dnl m4_ifelse(_commentnesting, 0, )) m4_define(_warning,m4_dnl _begincomment()This document was created by gen-_name.html Do not edit this document, edit gen-_name.html._endcomment()) m4_define(_hdrs, ) m4_define(_anchor_no, 0) m4_define(_abs, m4_ifelse(m4_eval($1 < 0), 1, m4_eval(-($1)), $1)) m4_define(hdr, _warning() $2 _warning() m4_ifelse(m4_eval($1 >= 0), 1, m4_define(`_hdrs', _hdrs`'_anchor_no $1 m4_translit(`$2', `,', ) )) m4_define(_anchor_no, m4_eval(_anchor_no + 1)) ) m4_define(usetag, _warning()$2_warning()) m4_define(puttag, _warning()$2_warning()) m4_changecom() m4_define(sps, $1$2) m4_define(sbs, $1$2) m4_define(,_warning()$1_warning()) m4_define(,_warning()$1_warning()) m4_define(itl,_warning()$1_warning()) m4_define(bld,_warning()$1_warning()) m4_define(hrf,_warning()$2_warning()) m4_define(mailat,_warning()hrf(mailto:$1,$1)_warning()) m4_define(nwsgrp, hrf(news:$1, $1)) m4_define(bookref, $1, $2. $3: $4, $5.) m4_define(i2m,m4_ifelse( $1,01,January, $1,02,February, $1,03,March, $1,04,April, $1,05,May, $1,06,June, $1,07,July, $1,08,August, $1,09,September, $1,10,October, $1,11,November,December)) m4_dnl $Revision: 1.5 $, $Date: 1999/12/09 19:16:32 $ CS 512 Test 2 hdr(2, Test 2 - Data Structures and Sequences) hdr(3, CS 512, Algorithm Design)

  1. The even-odd sorting problem requires that an array of integers be re-arranged so that the even integers appear before the odd integers. Explain how you would use a heap to implement even-odd sorting; you do not need to write code, just explain the general approach you'd use. Explain why you wouldn't use a heap to implement even-odd sorting.

    A heap can be used as it is in heapsort, but that's not useful here because sorting mixes up even and odd numbers, and we want them separated. We need to modify the heap property so that it puts all the even numbers before any of the odd numbers, then a heap would be useful because the modified heap property would put all even numbers (if any) at the top of the heap, followed by the odd numbers (if any).

    To get some idea of what the modified heap property child.data ? parent.data might be, consider the table of all possible data parities

    heap propertyresult
    child even ? parent eventrue
    child even ? parent oddfalse
    child odd ? parent eventrue
    child odd ? parent oddtrue
    A little thought shows that the heap property child.data ? parent.data translates into the test odd(child.data) or even(parent.data). Alternatively, you could observe that if itl(n) is even, then itl(n) mod 2 is 0 and if itl(n) is odd, then itl(n) mod 2 is 1; the heap property would then translate directly to child.data mod 2 => parent.data mod 2.

    You would not use a heap to perform an even-odd sort because you'd be implementing heapsort, which does order itl(n) log itl(n) work. The scanning approach developed in the homework does only order itl(n) work.

  2. Suppose an algorithm uses depth-first traversal to walk a tree. Would the algorithm run more quickly of the tree was in k-child form or in child-sibling form? Explain. You may assume the processing that the algorithm does on nodes and edges is independent of the order in which nodes and edges are visited.

    The algorithm would take the same time for both forms: they both have the same number of nodes and edges, and depth-first traversal will cover them all.

  3. Quicksort can exhibit itl(O)(itl(n)^2) run-time behavior when it uses a bad pivot to divide the array into two greatly unequal parts. Consider the following modification, suggested as an improvement when using quicksort to sort integers: divide the array into two parts so that the even numbers are in one part and the odd numbers are in the other part. The modification is justified by noting that, in the general case, about half the integers in the array are even and the other half are odd. Is this modification a good idea or a bad idea? Explain.

    It's a bad idea, for at least two reasons. First, the purpose of the pivot is to move lower-valued integers towards the front of the array and higher-valued integers towards the end of the array (assuming an ascending sort) with the pivot in between, making it easy to merge the two sorted halves. Dividing an array based on parity does not move lower values to one end and higher values to the other end; this makes merging the sorted parts more expensive than it would be in regular quicksort.

    Another problem with the modification is that, once an array is divided into even and odd parts, it can't be further subdivided because each part is all even or all odd.

  4. Implementing a heap using binary-tree nodes allows the heap to grow to arbitrary size, but introduces the possibility that adding new entries to the heap will unbalance the heap. Suggest a way of inserting entries that would prevent the heap from becoming too unbalanced; your new insertion technique should assume nothing stronger than the heap property (AVL rotations are not allowed). Demonstrate the effectiveness of your new insertion technique by showing how it would never create a left- (or right-) linear tree; you need not worry about deletions.

    Perhaps the easiest way is to include an extra boolean called go-left in each tree node. If go-left at node itl(n) is true, insertion traverses itl(n)'s left child (or inserts a left child if itl(n) doesn't have one); otherwise insertion traverses or inserts the right child. Insertion flips the value of go-left after examining it.

    Flipping go-left on each traversal of node itl(n) insures that each of itl(n)'s children gets about half the new nodes created in the subtree rooted at itl(n). Because a node's subtrees have more or less the same amount of nodes, the overall tree is reasonably balanced.

    Another approach is to include two integers in each binary-tree node indicating the heights of the left and right subtrees of the node. Insert would then traverse the subtree with smaller height. This approach is not as good as the previous approach because it requires that the heights along the path from the root to the inserted node be adjusted, but is not such a big deal for recursive traversals.

    The minimum-height technique cannot create linear trees because it insures a node has all its children before it has any of its grandchildren.

This page last modified on 1 i2m(10) 1999. m4_dnl $Revision: 1.2 $, $Date: 1999/03/12 17:36:48 $ m4_divert(1) m4_changequote({, }) {m4_define(tblfcntnts, _toc_tableit(}_hdrs{) _toc_down(_toc_ilevel, _toc_level) ) m4_define(_toc_tableit, m4_regexp($1, \([0-9]+\) \([0-9]+\) \([^ ]+\) \(.*\), m4_ifdef(_toc_level, , m4_define(_toc_level, m4_eval(\2 - 1)) m4_define(_toc_ilevel, _toc_level)) _toc_entry(\1, \2, \3) _toc_tableit(\4)) ) m4_define(_toc_down, m4_ifelse(m4_eval($1 < $2), 1, _toc_down($1, m4_eval($2 - 1))) ) m4_define(_toc_entry, m4_ifelse(m4_eval($2 > _toc_level),1,