due: Thursday March 13 at 11:59pm (submit on Gradescope here).
In this homework, you will implement the Radix Sort algorithm for an array of integers using a radix (base) of 10, so please review the notes from Lecture 4W (slide 15). The starter code can be downloaded here, which consists of one file: RadixSorter.java. You'll also redo the analysis of the DIYList add method using a slightly different growth technique (Part 1). Part 1 is independent of Parts 2 - 5 so feel free to start with either section and work on them in parallel.
= for the DIYList add method [4 points].When we designed our DIYList (our version of an ArrayList), we decided to double the capacity every time we needed more space to add an item to the array See the notes from Lecture 4M (slides 7-9). Are there other growth techniques we could have used? What would be the impact on the estimated number of operations?
Instead of doubling the capacity of the array whenever we need more space, let's consider increasing the capacity by 10 during each growth. Using this new strategy, count the number of assignments (=) for our DIYList add method when performing n calls to add. For this problem, you can assume the initial capacity is 0, which means we will need to grow the array during the first call to add, as well as the 11th, 21st, 31st, 41st, etc. Recall that we always have 1 assignment to save a new item, and we need to copy existing items when we grow the capacity. Hint: factor out a 10 when counting the number of = to copy existing items and try to match your expression with one of the series we saw.
After you find an expression for the total number of assignments (=) when adding n items using this strategy, divide by n to get the amortized number of = over all n calls. Finally, provide a big-O bound on this expression (as n gets very large). Recall that Oracle's documentation says:
The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.
Is this new growth technique consistent with what Oracle says the runtime of add should be?
To summarize, answer the following questions for the strategy of increasing the capacity by 10 during each growth, and show your work:
a. What is the total number of assignments in big-O when adding n items?
b. What is the amortized cost for each call to add (ie, divide your answer above by n)?
c. Is this consistent with the what Oracle says the runtime of add should be?
Please take a picture of your derivation, name your picture hw4-part1.png and upload it to Gradescope when you submit the code from Parts 2 - 5. If necessary, convert your image to a PNG format using a tool such as FreeConvert.
Note: This question will be graded for two components: (1) the effort put into the derivation [3 points] and (2) the final big-O expressions [1 point]. Therefore, please don't focus on getting the "right" expression for the number of =. The important thing is to show your thought process - only stating big-O results (with no work shown) will receive 1 point.
getMaxDigits method [2 points].Radix Sort is implemented using a certain number of "passes", which we denoted as
For a base of 10, the number of digits in an integer
The notation Math.floor) of some real number Math has a built-in method for Math.log10.
Complete the getMaxDigits method to determine the maximum number of digits for some input integer.
getDigit method [4 points].Recall that during each pass of Radix Sort with base 10, we need to create 10 buckets to hold our current items where each bucket corresponds to a particular digit from 0 to 9.
Therefore, we need a method to extract the getDigit method will take in some integer called number, the digit we want to extract (starting from the rightmost digit) d and the maximum number of digits in the array maxDigits.
Think about how you would extract the digits from the number 12345:
5 is (12345 / 1) % 10
4 is (12345 / 10) % 10
3 is (12345 / 100) % 10
2 is (12345 / 1000) % 10
1 is (12345 / 10000) % 10
Convert these steps into an algorithm and implement it in the getDigit method.
sort method using Radix Sort [9 points].Assume each value is 10 buckets to store the items for each digit (0 to 9) on this pass. Then go through every item and put them in the appropriate bucket. We recommend starting by using an ArrayList-of-ArrayList as we did in Lab 4, but note that Part 5 consists of doing this without ArrayLists at all. After each pass, put the items from the buckets back in the items array so you can treat them on the next pass.
sort method to avoid using ArrayLists [1 point].This part is only worth 1 point but it's a good challenge! Remove the import java.util.* at the top of your RadixSorter.java file and rewrite your Radix Sort algorithm without using ArrayLists. Instead, use a jagged multi-dimensional array (slide 10, lines 11 - 17) for the buckets. During each pass, you'll need to do two loops through the items: (1) to determine how many items are in each bucket and (2) to place the items in each bucket. In between Steps (1) and (2) you'll need to actually allocate the 10 buckets to have enough space to store them. Hint: for Step (1), you might want to use an additional array to store the number of items in each bucket so you know how much to allocate before Step (2).
Upload RadixSorter.java and hw4-part1.png to Gradescope. Remember to check the style of your code and add your name to a comment at the top of your file!