Imagine you are in a programming interview and are asked to devise an algorithm to solve a simple array problem. As part of the interview, you will need to write some code on a whiteboard and then argue why the code you wrote is correct.
Since you are writing your code on a whiteboard, you will not be able to execute or debug your algorithm on 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 to your interviewer.
To the best of your ability, emulate these conditions for the problem below. You can use a programming editor to write your code and argument, but do not run any code for this assignment. You will not be graded for correctness. Any submission showing a basic level of effort will receive full credit.
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.
The input to your algorithm is an integer array, int[] arr.
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 switch the
values in two elements of the array. To simplify your code, you can write
swap(arr[i], arr[j]) as shorthand for performing
the assignments necessary to replace the value in arr[i] with
that in arr[j] and vice versa.
You may not create any additional data structures.
Your algorithm should run in O(n) time. For an extra challenge, you can try to implement it using one pass through the array.
For example, an array [2, -2, 0, 1, -1, 0] might get rearranged
into [-1, -2, 0, 0, 1, 2] or [-2, -1, 0, 0, 2, 1].
Note that there are multiple valid outputs for each input.
Again, 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.
The write up of your solution should contain the following parts:
Your name.
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.
A written 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?
Crucially, do not just describe what your code does in English (e.g., "we go through the array, and for each item, we ..."). Your interviewer understands Java and can read exactly what the code does. Your argument should convince them that the algorithm your wrote always produces a correct solution for any valid input.
Do not spend more than 60 minutes on this assignment. If, after 40 minutes, you have not come up with an algorithm that you think is correct, you may 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 40 minutes, cannot think of any way to argue that it is correct, you can instead describe what thoughts led you to construct that algorithm in part 3.
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.