Due: Wednesday, January 5 by 10AM. No late assignments will be accepted. Submit your assignment using Gradescope.
In this assignment, you should devise an algorithm to solve a simple 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. The goal is not just to come up with some code that you think might be correct, but that you know is correct.
(Hint: imagine you are in front of a whiteboard trying to present your algorithm to a colleague (or to a person interviewing you!) and convince them that it works.)
This is probably quite different than your usual experience with programming and may seem more difficult than just “trying stuff” on the computer. You should not spend unreasonable amounts of time on it (a couple of hours should be more than enough). If you haven't come up with a full solution after a couple of hours, write up a description of what you have figured out and why you believe it should work (or why not!), The goal is to start to think about programming in a more analytic way, and even if you don't get a completely correct solution you still will get the intended benefit from the exercise and will receive credit if you put in the effort to create a reasonable solution. Over the next week or two we will introduce techniques for thinking about these kinds of problems to make them much easier to solve. Doing this exercise now will help us understand the issues involved and see later why these techniques are so valuable.
The input to your algorithm is an array b containing
n integer values in locations b[0] to
b[n-1]. You may assume that n >= 1.
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 (interchange) 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, dictionaries, or other collection data structures to hold copies of the original data. You will, of course, want to create some scalar variables to hold various values as part of your algorithm.
Your algorithm should run in O(n) time. You should try to solve the problem using one pass through the array if you can.
You may not execute or debug your algorithm on a computer.
The write up of your solution should contain the following parts:
Your name.
Your algorithm, written in Java syntax. This should be a single Java method rather than an entire class or program. Also, 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.
An argument that your algorithm is correct. Your argument should be aimed at convincing a person that is skeptical about its correctness. Explain, in small steps that they cannot disagree with, why the output produced by your algorithm will always be correct.
Your argument should not just describe what the code does in English (e.g., "we go through the array and for each item we ..."). You should assume the reader understands Java code and can see what it does. Your goal is to convince them that performing these steps always produces a correct solution to the problem.
When you are done, you should upload your solution to Gradescope. Gradescope will ask you identify which problems are contained on which pages; just select the page(s) with your solution.
Be sure that your name appears at the top of your solution.
Note: 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 you can use to access the turnin page.
Your gradescope.com 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.
You will need to submit your writeup 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.