HW0 — CSE 331 17au

Due: Friday, September 29st by 10:30am (when class starts)

Overview

In this assignment, you will devise an algorithm to solve a simple array problem and argue that your algorithm is correct. You should 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 may be a big change and that it may be difficult. For this assignment, it will be possible to get full credit simply for demonstrating a full effort, even if you do not produce a correct solution. (After the next few lectures, this should become much easier. For subsequent assignments, you will need to give correct solutions to get full credit.)

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 should only need to modify the array using swap operations that 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. As a challenge, you can try to implement it 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 syntax. Note that this should be a single Java function 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.

  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.

  4. The total amount of time you spent working on your algorithm and argument.

If you are unable to produce a correct algorithm and an argument for its correctness after 90 minutes, you may stop trying. In that case, replace the algorithm and argument in your write up with a discussion of what you tried and why it did not work.

Submission

You will need to submit your write up as a PDF. 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.

Use the drop box (linked on the main page) to turn in the PDF file of your write up.