CSE 331 23wi HW0

Due: Friday, January 6 by 10AM. No late assignments will be accepted. Submit your assignment using Gradescope.

Overview

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 (although it's fine to write up your solution using an ordinary computer text editor - not a software IDE editor - if you want). 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.

Requirements

• 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 assign integer values to individual array elements (i.e., b[i]=0 is forbidden).
• You may not create any additional arrays, dictionaries, or other collection data structures to hold a copy or copies of the original data. You are free, of course, to create some scalar variables to hold a few values as part of your algorithm if that is useful.
• 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.

Write Up

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

1. Your name.
2. Your algorithm, written in Java syntax. This should be a sequence of statements, i.e., the body of 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 clear code that will be easy for others to understand.
3. 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.

Submission

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