Navigation

• Preliminaries
• MAX
• 3SUM
• 3SUM_DISTINCT
• FAQ
• Submission
• Getting Help

A. Preliminaries

Goals

The exercises here aim to introduce you to a few basic points of Java syntax.

• Initializing variables, e.g. int x = 5;
• Comparisons and logical operators
• Conditionals (if statements)
• Iteration (using for and while)

Grading for this assignment will be pretty lenient and will just consist of making sure you've submitted the presemester survey, though full grader details will be coming soon. You won't be graded on whether or not the code works as it should, but with that said we suggest that you do give them a serious try in order to give yourself a chance to get comfortable with Java and dust off your programming skills from last semester.

For each of the problems,

• No starter code is provided. Use examples from class and the textbook to write your solutions. We don't care what you call your classes, since we don't intend to test your submissions.
• You can use whatever tool you'd like to write and run your code. This could be the javac/java on your own computer or the lab machines, etc., or IntelliJ, or an online execution tool.
• For each problem, use the main method to perform an ad-hoc test (by ad-hoc, I just mean a crude test that isn't generalizable like the fancier tests that you'll be developing in HW1). For example, you can write in your main method a few print statements calling your method to ensure it correctly prints the right thing.

Setup

As with lab1, start this homework by using the following commands in your local repo directory (assuming that you are using our normal setup--working on the default master branch--and that you have committed any files you you already have there from other assignments.)

git fetch shared
git merge shared/hw0 -m "Get HW0 skeleton"
git push

This time there will be no skeleton file for your solution. The idea is for you create and add the necessary files. As you create new files, be sure to use git add to add bring them under Git's control.
We have provided a skeleton Tester.java file for writing simple tests of your solutions. However, you will have to figure out how to get it to actually call your solutions before you can compile and run it. You can use javac to compile it, and java Tester to run it.
To submit, you will tag a specific commit. Details can be found in the submission section.

Do the Reading

Make sure you've done the first reading assignment: AJR 1.1 through 1.9 (found here) and Chapter 1 of Head First Java. If you don't have Head First Java, that's fine, AJR provides all the information you need (but might be a harder read).

While you're reading, you may find it helpful to be able to run Java code so that you can experiment. You can compile and execute as you have done in lab, of course. There is also a convenient online Java compilation tool. To run code, simply add the code you'd like to execute to the main method and then press the Compile and Execute buttons.

Head First Java provides you with exercises that you can do as you read. Feel free to skip doing these if you'd like.

B. Max

Write a function max(int[] a) that takes in a non-empty array (that is, size(a)>0) and returns the maximum value of the array. Try writing this function using both a while loop and a for loop.

A note about convenient syntax for creating arrays:

You can specify an array using curly braces. A strange choice of symbols, for a Python programmer, but we're in the C family of languages here. For example:

int[] a = new int[]{1, 2, 3, 4}

would create an array containing 1, 2, 3, and 4 and then give it the name a.

In this context, the curly braces are interpreted in a completely different way from when we use them to begin and end a block of code.

To test, modify your main function to perform an ad-hoc test of your method. In this context, this means a non-generalizable test in which you feed in specific test cases as input to the function, compile, and check that the output is what is expected.

C. 3SUM

Suppose we have a non-empty array of integers int[] a. The 3SUM problem asks if there are three integers (not neccesarily distinct) in a[] whose sum is zero. You may assume that the array is not empty.

For this problem, write a function threeSum(int[] a) that returns true if there exist three integers in a that sum to zero and false otherwise. Integers may be used more than once. As in part 1, use your main function to perform an ad-hoc test that threeSum works.

For loops will look a lot more compact than while loops for this problem.

Examples:

• threeSum(new int[]{-6, 2, 4}) is true, can select -6, 2, and 4.
• threeSum(new int[]{-6, 2, 5}) is false.
• threeSum(new int[]{-6, 3, 10, 200}) is true, can select -6, 3, and 3.
• threeSum(new int[]{8, 2, -1, 15}) is true, can select 2, -1, and -1.
• threeSum(new int[]{8, 2, -1, -1, 15}) is true, can select 2, -1, -1.
• threeSum(new int[]{5, 1, 0, 3, 6}) is true, can select 0, 0, and 0.

This might seem daunting at first, but it's relatively straightforward. As a hint, consider an alternative way of stating the problem: Do there exist three indices (not necessarily distinct) f, g, and h such that a[f] + a[g] + a[h] == 0?

D. 3SUM_DISTINCT

Repeat the exercise from Part C, but with the constraint that each element in the array can be used only once. Where in the last problem we wanted the three not necessarily distinct indices, we here require three distinct indices. Numbers can appear more than once in our sum if and only if they appear more than once in the given array. Again, you may assume the array is not empty.

Examples:

• threeSumDistinct(new int[]{-6, 2, 4}) is true, can select -6, 2, and 4.
• threeSumDistinct(new int[]{-6, 2, 5}) is false.
• threeSumDistinct(new int[]{-6, 3, 10, 200}) is false.
• threeSumDistinct(new int[]{8, 2, -1, 15}) is false.
• threeSumDistinct(new int[]{8, 2, -1, -1, 15}) is true, can select 2, -1, and -1.
• threeSumDistinct(new int[]{5, 1, 0, 3, 6}) is false.

E. FAQ

1. I am really lost on 3SUM? How do I start?

Consider first how you would handle 1SUM. How would you figure out if there is a specific index in the given array which is equal to 0? From there, think about how you would implement 2SUM. How would you find out if there exists two indices in the array j,k (not necessarily distinct, that is j can equal k) such that array[j] + array[k] = 0? From here, try to generalize for the number of terms you are summing over! You'll see that 3SUM, 4SUM, 5SUM, etc are all very similar and you could easily make any of them!

2. How many test cases do I have to write?

You should think through the basic cases and as many of the corner cases as you can think of. Though you are not being graded on the correctness of your code for this assignment, later assignments will be graded on correctness and require you to test your own code! It is a good idea to start practicing now.

3. I am getting a weird compiler error!! Help!

Before you post on Piazza, try googling the error you are getting. This is how you learn, Google is one of the most important tools for any person who writes software. For example, if your terminal says that you are getting an "IndexOutOfBoundsError", try typing that into Google and following the advice of a reputable website (for example, stackOverflow).

4. My main method can't find my classes!

Can't access method from main

5. I am getting issues with multiple methods of the same name!

Check out this documentation!

F. Submission

We don't intend to test the correctness of your methods, just that you have created the required methods (max, 3SUM, 3SUM_Distinct) and created tests for them. We will also be checking that you've filled out the presemester survey. If you haven't done all of these things, then you will not receive full credit for this homework.

Before beginning the submission process, take a moment to make sure all of the files you created have been added to Git's control (by using git add <insert file name here>).

To submit, follow the same instructions as for lab1:

• Commit (with git commit -a) any changes you've made.
• Tag the submission (e.g., git tag hw0-0).
• Push your commits and tags (git push and git push --tags).

G. Getting Help

For future assignments we are using an infrastructure called Git Bugs for interfacing with staff for debugging help. More info to come on that in the next homework. We won't be using Git Bugs on this assignment. If you need help on this homework, you should ask your lab TA or visit office hours for in person help. You're also welcome to use Piazza, but please read our Piazza guidelines before that.