HW0

Due: Wednesday, March 30th by 5pm

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

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 straightforward to solve. We want you to experience how perplexing these problems can be without these tools so that you can appreciate why they are so valuable.

Overview

Imagine you are in a programming interview.... Actually, this should help you imagine it:

You need to answer Ardi's question by writing code that correctly solves his problem, but since you are in front of a whiteboard, you will not have the help of a computer!

Furthermore, your goal is not just to come up with some code that you think is correct but rather with code that you can prove is correct. Having a convincing correctness argument for your code will allow you to leave the interview being certain that you solved the problem correctly.

Formal 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.

Do 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.

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 60 minutes, 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" for part 3.

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.