![university of washington logo](/images/purple_w.png)
CSE 331 16su Homework 0
Due: Wednesday, June 20 by 1pm.
Note: no late submissions will be accepted.
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
containingn
integer values in locationsb[0]
tob[n-1]
. You may assume thatn >= 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 inb[i]
with that inb[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:
Your name.
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.
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.
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 two hours, 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 to turn in the PDF file of your write up.
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX
Comments to adminanchor