Homework 1: Welcome to Java

Due Tuesday, 16-Aug @ 8:00pm on Gradescope

This assignment will help you refresh your programming abilities and get you a basic introduction to Java. You should start early so that you can attend office hours when problems come up.

For this assignment you have 7 submissions. You should write your own testcases while you work so that you don’t waste submissions. There are two example testcases provided that you can use to get started.

After you have used your submissions, you may continue to submit, but your submission will be penalized 4 points for every extra submission. (So, your 8th submission receives a -4, your 9th submission a -8, etc.)

1. Introduction

In this assignment you will be creating a basic class that acts as a data structure store integers. It is backed with a simple array.

Download the pre-prepared Eclipse Project hw1.zip and import it into Eclipse using these instructions. You will make all of your changes inside of MyArray.java.

2. MyArray

You will be implementing a simple data structure that can be used to store integers. You can add new integers to it (either to the end or the beginning), rearrange those integers in specific ways, etc. Your data structure needs be able to grow “infinitely”, meaning that you can keep adding integers to it as long as the computer has available memory.

You will actually store the integers in an array, but in arrays in Java have a fixed size defined when they are created. That means that if your array is full and you still need to add another integer to it, you will need to create a new array that is larger, copy all of the old values to it, and then add your new value. As a consequence of this, your array may have more “space” available then there are values currently stored. In order to keep track of which spaces in your array have valid integers and which don’t, you will also be tracking how many items are actually stored in the array.

3. Documentation

Inside the file MyArray.java you will find method declarations with empty bodies. You need to implement each incomplete method and write code to test them inside in the main method.

You are free to add new methods to the file (such as helper methods), but do not change the names of any of the provided methods. If you do, you will automatically fail the autograder.

The methods you are writing are as follows:

public MyArray()

Default constructor. You probably shouldn’t change this.


public MyArray(int[] arr)

Constructs a MyArray object from an array of integers such that only the unique values from the array are stored in intArray.

e.g., if the argument contained [1,3,5,1,8,2,42,5,1], the MyArray object would contain [1,3,5,8,2,42]

After this constructor runs, the size of intArray and the value of numValues should be the same: The number of unique items in arr.

  • Parameters: arr — The array of values to add to to the MyArray. The original arr must remain unchanged after the call to this constructor, meaning this constructor is non-destructive.


public boolean isEmpty()

Determines if the MyArray object is empty or not

  • Returns: true if there are no items in the array, and false otherwise


public boolean isFull()

Determine if the array is full.

  • Returns: true if array is full and false otherwise


public boolean isDecreasing()

Checks if all the items are in sorted, decreasing order. i.e., a[i] >= a[i+1] for all valid array elements

  • Returns: true if all elements are in decreasing order, false otherwise


public int maximum()

Find the maximum integer value currently stored

  • Returns: the maximum value stored or Integer.MIN_VALUE if there are no items

    stored


public void randomizeItems()

Randomize the order of the items in the array.

Use the following algorithm:

for i from 0 to n-2 do
    j = random integer such that i <= j < n
    exchange a[i] and a[j]


public void rotateLeft()

Rotates all the elements in the array one position to the left, placing the last element in position 0

For example: if the array before the call to rotateLeft is [4, 5, 6, 1] it is [5, 6, 1, 4] after the call


public void reverse()

Reverses the elements stored in the array

For example: if the array before the call to reverse is [1, 4, 5, 6] it is [6, 5, 4, 1] after the call


public void makeDups()

Makes a duplicate of each value in the array, but considers the length on intArray when doing it.

If the array contains [1,7,5] and intArray has a length of 6 before calling this method, then the data structure would contain [1,1,7,7,5,5] after.

If the array contains [1,7,5] and intArray has a length of 5 before calling this method, then the data structure would contain [1,1,7,7,5] after.


public void append(int i)

Adds a new integer to the end of the array.

e.g., If the arrays contained 12, 4, 5 and this method was called to insert 13, the array would contain 12, 4, 5, 13.

If the array is full prior to appending, you should resize it first to be double its current size. To do this, you’ll need to create a new, larger array, and copy the existing items into it. If intArray has length 0, then resize it to hold one item.

Don’t forget to update the instance variable that tracks how many items are stored in the array.

  • Parameters: i — The new value to add to the array


public void insertFront(int i)

Adds a new integer to the beginning of the array.

e.g., If the array contained 12, 4, 5 and this method was called to insert 13, the array would contain 13, 12, 4, 5.

If the array is full prior to inserting, you should resize it first to be double its current size. To do this, you’ll need to create a new, larger array, and copy the existing items into it. If intArray has length 0, then resize it to hold one item.

Don’t forget to update the instance variable that tracks how many items are stored in the array.

  • Parameters: i — The new value to add to the array


public String toString()

Returns a string representing the array.

e.g., if the intArray contained [1,7,5] then this should return the String "[1,7,5]"

  • Returns: String representing the array


4. Grading and Submission

Your submission will be graded as follows:

  1. For the first 90 points, your submission will be auto-graded on Gradescope.

  2. For the next 5 points, your submission will be manually graded to check for good implementation methodologies. (Did you use a good approach to solving the problems?)

  3. For the next 5 points, your submission will be manually graded to check for good testcases that you include in the main method. (Do you have 2-3 of your own testcases for each method, and do they all execute automatically?) There are two testcases already included to serve as examples.

  4. Your code will also be checked for style. The parts of style that can be checked automatically (things like spacing, indentation, the use of CamelCase, etc.) are automatically checked by the autograder. Other parts of style, such as choosing good variable names, will be checked manually. Autograded style guide violations can result in, at most, -10 points. Manually checked style guide violations can result in, at most, -5 points.

You will submit your program to Gradescope. Login to the system and you will see the homework. Once there, you need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Look at these instructions for exporting. On Gradescope, you’ll submit that exported zip file. On the page that follows your submission you will see your live score (out of 90). It may take up to a few minutes for your score to appear. If you receive a lower score than you expect, you can click on the individual testcases to see the feedback from the autograder.

You must follow the model of our testcases from previous assignments (meaning you print when you start, print the results (pass/fail) when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

5. Restrictions

You may only use the following Java libraries in this assignment:

java.util.Random

6. Important Notes