Assignment 7

Contents:

  • Overview
  • Internet Requirements
  • Practice Problems
  • Problems to be Submitted
  • Extra Credit
    •

    Overview

    Topic: Algorithms
    Related Reading: Ch. 6.1, 9.4: only pp. 297-299, 9.5 and pp. 545-551
    Due:  

    Internet Requirements

    You may want an Internet connection for several practice problems. However you do not necessarily need the connection for completing the assignment, other than for submission. 

    Practice Problems

  • Exercise 23, 29 of Ch. 6 (p. 193); answer in back of text
  • Exercise 47 of Ch. 9 (p. 327); answer in back of text
  • Consider the following sorted list of numbers:
    • 2 4 7 10 13 16 17 20 24 28 31 38 41 43 45
  • What sequence of 'middle' values are compared to the target when performing binary search with target 28?
  • What sequence of 'middle' values are compared to the target when performing binary search with target 16?
  • What sequence of 'middle' values are compared to the target when performing binary search with target 5?
    •  Note: The solution for the above questions can be found by running a Binary Search Demonstration with parameter "#items: 15" and "seed: 15849" and with target set appropriately.
  • Use this initial list for each part below.  Answer at the end of the assignment:
    • 8 3 5 1 9 4 2 6
  • Show the state of the list after each time through the outer loop of the selection sort algorithm.
  • Show the state of the list after each time through the outer loop of the insertion sort algorithm. How many comparisons are done between elements of the list?
  • Show all the levels of merges for different length sublists coming from the mergesort algorithm.
    •

    Problems to be Submitted (20 points)

      Use this initial list for each of problems 1, 2, and 3.
      E C G F A K H D
    1. (3 points)

      2. Show the state of the list above after each time through the outer loop of the selection sort algorithm.
    2. (5 points)

      3. Show the state of the list above after each time through the outer loop of the insertion sort algorithm. How many comparisons are done between elements of the list?
    3. (7 points)

      4. Show all the levels of merges for different length sublists coming from the mergesort algorithm for the list above.
    4. (5 points)

      5. Consider the following sorted list of numbers:
      2 4 9 16 19 21 25 27 32 33 35 38 41 42 43
      1. What sequence of 'middle' values are compared to the target when performing binary search with target 4?
      2. What sequence of 'middle' values are compared to the target when performing binary search with target 17?
      3. What sequence of 'middle' values are compared to the target when performing binary search with target 22?
      4. What sequence of 'middle' values are compared to the target when performing binary search with target 34?
      5. What sequence of 'middle' values are compared to the target when performing binary search with target 41?
    Overall, please type your answers to all of the problems in a single document to be submitted electronically. Please see details about the submission process.

    Extra Credit (2 points)

    In problem 3, we have not stressed the order in which the recursive calls are completed in Mergesort, except that the two halves of each list must be sorted before the combined list is merged.  Follow the Mergesort algorithm in order as it was written for class, and write down all the sorted lists in the order they are determined.  (Everything that needs to be done to sort a first half is always done before the second half.)  To assist you, the first sorted list and the last two sorted lists are shown.
    E
    ...
    ADHK
    ACDEFGHK

    Answer to the last practice problem:

    Selection sort
    9 3 5 1 8 4 2 6  after first loop
    9 8 5 1 3 4 2 6  after second
    9 8 6 1 3 4 2 5  after third
    9 8 6 5 3 4 2 1  after fourth
    9 8 6 5 4 3 2 1  after fifth, sixth, and seventh

    Insertion sort (comparisons to all elements moved and to the first element not moved, if there is one)
    3 8 5 1 9 4 2 6  after first loop, one comparison to a list element
    3 5 8 1 9 4 2 6  after second, two comparisons
    1 3 5 8 9 4 2 6  after third, three comparisons
    1 3 5 8 9 4 2 6  after fourth, one comparison
    1 3 4 5 8 9 2 6  after fifth, four comparisons
    1 2 3 4 5 8 9 6  after sixth, six comparisons
    1 2 3 4 5 6 8 9  after seventh, three comparisons
    20 comparisons to list elements in all

    Merge sort
    (1  2  3  4  5  6  8  9)
    (1  3  5  8)(2  4  6  9)
    (3  8)(1  5)(4  9)(2  6)
    (8)(3)(5)(1)(9)(4)(2)(6)

    Last modified: 20 October 2004