Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Exercises

  1.   Consider the sequence of integers

    displaymath69879

    For each of the following sorting algorithms, draw a sequence of diagrams that traces the execution of the algorithm as it sorts the sequence S: straight insertion sort, binary insertion sort, bubble sort, quick sort, straight selection sort, heapsort, merge sort, and bucket sort.

  2.   Draw a sequence of diagrams that traces the execution of a radix-10 sort of the sequence

    displaymath69880

  3. For each of the sorting algorithms listed in Exercises gif and gif indicate whether the sorting algorithm is stable.
  4. Consider a sequence of three distinct keys tex2html_wrap_inline65998. Draw the binary decision tree that represents each of the following sorting algorithms: straight insertion sort, straight selection sort, and bubble sort.
  5.   Devise an algorithm to sort a sequence of exactly three elements. Make your algorithm as efficient as possible.
  6. Prove that the swapping of a pair of adjacent elements removes at most one inversion from a sequence.
  7. Consider the sequence of elements tex2html_wrap_inline69891. What is the maximum number of inversions that can be removed by the swapping of a pair of distinct elements tex2html_wrap_inline68467 and tex2html_wrap_inline68469? Express the result in terms of the distance between tex2html_wrap_inline68467 and tex2html_wrap_inline68469: tex2html_wrap_inline69901.
  8. Devise a sequence of keys such that exactly eleven inversions are removed by the swapping of one pair of elements.
  9. Prove that binary insertion sort requires tex2html_wrap_inline58846 comparisons.
  10.   Consider an arbitrary sequence tex2html_wrap_inline69891. To sort the sequence, we determine the permutation tex2html_wrap_inline67203 such that

    displaymath69881

    Prove that bubble sort requires at least p passes where

    displaymath69882

  11. Modify the bubble sort algorithm (Program gif) so that it terminates the outer loop when it detects that the array is sorted. What is the running time of the modified algorithm? Hint: See Exercise gif.
  12. A variant of the bubble sorting algorithm is the so-called odd-even transposition sort . Like bubble sort, this algorithm a total of n-1 passes through the array. Each pass consists of two phases: The first phase compares tex2html_wrap_inline69913 with tex2html_wrap_inline69915 and swaps them if necessary for all the odd values of of i. The second phase does the same for the even values of i.
    1. Show that the array is guaranteed to be sorted after n-1 passes.
    2. What is the running time of this algorithm?
  13. Another variant of the bubble sorting algorithm is the so-called cocktail shaker sort . Like bubble sort, this algorithm a total of n-1 passes through the array. However, alternating passes go in opposite directions. For example, during the first pass the largest item bubbles to the end of the array and during the second pass the smallest item bubbles to the beginning of the array.
  14.   Consider the following algorithm for selecting the tex2html_wrap_inline61000 largest element from an unsorted sequence of of n elements, tex2html_wrap_inline69931.
    1. If tex2html_wrap_inline69933, sort S and select directly the tex2html_wrap_inline61000 largest element.
    2. Otherwise n>5: Partition the sequence S into subsequences of length five. In general, there will be tex2html_wrap_inline69943 subsequences of length five and one of length tex2html_wrap_inline69945.
    3. Sort by any means each of the subsequences of length five. (See Exercise gif).
    4. Form the sequence tex2html_wrap_inline69947 containing the tex2html_wrap_inline69943 median values of each of the subsequences of length five.
    5. Apply the selection method recursively to find the median element of M. Let m be the median of the medians.
    6. Partition S into three subsequences, tex2html_wrap_inline69957. such that all the elements in L are less than m, all the elements in E are equal to m, and all the elements of G are greater than m.
    7. If tex2html_wrap_inline69971 then apply the method recursively to select the tex2html_wrap_inline61000 largest element of L; if tex2html_wrap_inline69977, the result is m; otherwise apply the method recursively to select the tex2html_wrap_inline69981 largest element of G.
    1. What is the running time of this algorithm?
    2. Show that if we use this algorithm to select the pivot the worst-case running time of quick sort is tex2html_wrap_inline58846.
  15.   Show that the sum of the heights of the nodes in a complete binary tree with n nodes altogether is n-b(n), where b(n) is the number of ones in the binary representation of n.

next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.