Homework 4

Homework 4

Homework Reflection SurveyGradescopeStarter Code
Due: Thursday October 09, 2025 5:00PM
Goals:

• Practice counting operations and then determine a big-O bound on the number of operations.
• Implement Radix Sort.

Submit these files:hw4-part1.png,RadixSorter.java

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 4R. 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.

Part 1: Recalculate the number of = for the DIYList add method

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 annotated slides from Lecture 4T (pages 11-15). 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 the proposed 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 and comparison to the Oracle documentation [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 at most 1 point.

Part 2: Complete the getMaxDigits method

Radix Sort is implemented using a certain number of “passes”, which we denoted as \(k\) in class. The number of passes corresponds to the maximum number of digits we are using to represent numbers. In our base-10 Radix Sort example in class, the maximum number in the input array was 802, so the maximum number of digits was 3.

For a base of 10, the number of digits in an integer \(v\) (assume \(v \gt 0\)) is:

\[ k = \lfloor \log_{10}(v)\rfloor + 1. \]

The notation \(\lfloor x \rfloor\) means the “floor” (using Math.floor) of some real number \(x\), which returns the largest integer less than or equal to \(x\). For example, \(\lfloor 2.2\rfloor\) is 2 and \(\lfloor 3\rfloor\) is 3. Note that Math has a built-in method for Math.log10.

Complete the getMaxDigits method to determine the maximum number of digits for some input integer.

Part 3: Complete the getDigit method

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 \(d^{\mathrm{th}}\) digit of an integer in our array. As in class, we will start with the least significant digit (the rightmost digit) and proceed from right-to-left. 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.

Part 4: Complete the sort method using Radix Sort

Assume each value is \(\ge 0\). Please review the steps we used to sort an integer array in the annotated slides from Lecture 4R (page 23) as well as the sorting examples (Radix Sort starts on page 123). During each pass, create a new set of 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.

Part 5: Refactor your sort method to avoid using ArrayLists

This part is only worth a small amount but it’s a good challenge! Remove the import java.util.ArrayList at the top of your RadixSorter.java file and rewrite your Radix Sort algorithm without using ArrayLists. Instead, use a jagged multi-dimensional array (page 55, lines 11 - 18) 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).

Test Case Requirements

We’re keeping it simple for test case requirements this week. The only requirement is that you test RadixSorter.sort on at least two different arrays!

Documentation, Style, and Design

Documentation and Style

Checkstyle will run automatically when you submit to gradescope; up to 10% will be deducted by the autograder from the programming portion of your grade if you have > 2 types of checkstyle problems. Remember you can see more details on checkstyle on this page, including how to run it in vscode.

Design

I will do a manual review for design. Up to 5% may be deducted from your final score due to design problems. This will also include checking the quality (rather than just the form) of your javadoc comments!