Homework 5

Due: Tuesday, May 8, 2022 by 8am

Overview

For this assignment you may work with at most one partner. Consult the resources provided and your professor for help if you need it. Please type your answers. Use good grammar, correct spelling, and complete sentences.

This assignment will be submitted on iLearn by the deadline and you will bring a physical printed copy the day of your final exam whenever that is for your section. Homework turned in after the deadline will not be accepted. Homework turned in after I have collected it will lose 20%. Please do not email late homework to your professor.

Only one student's submission is required on iLearn and one printed submission is to be turned in, provided, both student's names appear on the assignment.

Any code you write should "just work" if the professor types it in and compiles and runs it.

Total points: 55. (not including the extra credit)

Assignment

  • 1. (20 points extra credit) Implement quicksort and bucket sort. Use the code in your book to help; the partition in quicksort is tricky. Make sure your implementations are correct — it is easy to gain some confidence in the correctness of your code by writing a program which creates arrays filled with random numbers, sorts them, and then checks that they are sorted.

    Then time your code (using System.nanoTime() or similar methods) on both methods for arrays filled with random integers of the following sizes (where n is the number of elements to be sorted, and m is the maximum integer value of the items in the input array):
    1. * n is very large, m is very small
    2. * n is very small, m is very large
    3. * Find values of n and m where both implementations take (approximately) equal time.
    Discuss where quicksort performs best, and where bucket sort performs best.

    A clock time of 0 isn't very meaningful. When timing your code, try doing the same thing many times (like 100 times or more) to get more accurate results. Show both your code and your results. Experiment with the values of m and n and with your code to get reasonable, interesting, reportable results.

    Note that the quicksort code in the book is incorrect if you remove the dependence on insertionSort. If you include insertion sort, the code is correct. If you want to eliminate insertion sort, then you should do the following: surround line 27 in quicksort (the "restore pivot" step) with an if block: 
                if ((right - left + 1) > 2) {
/* 27 */        swapReferences(a, i, right - 1); // Restore pivot
            }
    Thanks to Jordan Willis for pointing out this bug.

  • 2. (10 points) Write a program which, given an unsorted array of numbers, will print out the information that would allow us to sort the array (least-to-greatest) in one pass. This is the permutation that the original array is in, relative to its sorted order.

    For example, if you were given the array A = [100, 50, 60, 250], then the permutation is P = [1, 2, 0, 3]. Then if we were to walk across this permutation, we could create the sorted array S by doing the following:
    • S[0] = A[P[0]]
    • S[1] = A[P[1]]
    • S[2] = A[P[2]]
    • S[3] = A[P[3]]
    You may use a sorting algorithm to solve this problem. This is a hint!

  • 3. (10 points) Do question 9.1 in your book.
  • 4. (10 points) Do question 9.5 in your book.
  • 5. (5 points) Do question 9.7 part (a) in your book.
  • 6. (10 points) Do question 9.15 parts (a) and (b) in your book. Show each step of each algorithm for part (a).
  • 7. (10 points) Do question 9.16 in your book. Justify/Explain your answer.