HW0

Due: Wednesday, April 1st by 5pm but before you watch Wednesday's lecture.

This assignment will not be graded, but you will receive points for participation. Any submission showing a basic level of effort will receive credit. Nonetheless, you should attempt to produce a correct solution.

Overview

In this assignment, you will devise an algorithm to solve an array problem and argue that your algorithm is correct. You should not execute or debug your algorithm on a computer. The purpose of this exercise is to practice creating a correct algorithm by reasoning rather than by trial-and-error experimentation.

We understand that this assignment may be quite different than your usual experience with programming and that it may be difficult. That is good! Over the next week or so, we will introduce tools that will make this problem easy to solve, so if it is difficult for you now, remember that experience so that you can appreciate why these new tools are so valuable.

Requirements

• The input to your algorithm is an array b containing integer (int) values. You may assume that the array is not empty.

• Your algorithm should rearrange the elements of the array so that all the negative (< 0) elements come first, followed by all of the zeros (== 0), followed by all of the positive (> 0) elements.

• You may only modify the array using swap operations that interchange (switch) the values in two elements of the array. To simplify your code, you can write swap(b[i], b[j]) as shorthand for performing the assignments necessary to replace the value in b[i] with that in b[j] and vice versa.

• You may not create any additional arrays.

• Your algorithm should run in O(n) time. For an extra challenge, you can try to implement it using one pass through the array.

Write Up

The write up of your solution should contain the following parts:

1. Your name.

2. Your algorithm, written in Java-like syntax. This should be a single Java method rather than an entire class or program.

   Keep in mind that this code is to be read by a human, not a compiler, so don't stress out about minor syntax issues. Instead, focus on writing code that will be easy for others to read.

3. An argument that your algorithm is correct.

   Your argument should be aimed at convincing a person that is skeptical about its correctness. Explain to them why the output produced by your algorithm will always be correct. In other words, why, when your algorithm finishes, is it impossible for the requirements above to not be satisfied?

   Do not just describe what your code does in English (e.g., "we go through the array, and for each item, we ..."). You should assume that the reader understands Java and can see what the code does. Your argument should convince them that performing those steps always produces a correct solution for any valid input.

Do not spend more than 90 minutes on this assignment. If, after one hour, you have not come up with an algorithm that you think is correct, you can instead write up a description of the ideas you considered and why it didn't seem like those would work. If you come up with what you believe is a correct algorithm but, after 30 minutes, cannot think of any way to argue that it is correct, you can instead just write "no argument after 30 minutes of thinking".

Submission

When you are done, you should upload your solution to Gradescope.

You will need to submit your write up as a PDF file. It is okay to submit a scanned copy of a handwritten document as long as it is (1) legible and (2) no more than 5 MB in size. If you are new to Gradescope, see this document for instructions on how to scan and submit hand-written solutions.

Gradescope accounts will be created on the first (or second) day of the quarter for all registered students. You will receive an email message from Gradescope with a link that you can use to create an account and submit your solution. Your Gradescope username will be your UW email address. If you are not registered for the course before the assignment is due, please send mail to cse331-staff[at]cs with your name, your UW ID number, and your UW email address (uwnetid@uw.edu) so we can set up a Gradescope account for you.