CSE331 Spring 2015: Homework 0

Due 10:00AM Wednesday April 1 — No late submissions accepted

Write an algorithm to partition the elements in an integer array as described below and argue that your algorithm is correct. You should not run your algorithm or debug it on a computer. The idea of this exercise is to get it right by thinking and analyzing, not by executing, debugging, or experimenting.

Use Java syntax for a method, but do not write an entire Java program; just one method. Because you are not using a computer, we will not grade on tiny syntax mistakes like forgetting a semicolon, but do your best to write a clear and correct algorithm.

Your algorithm should work as follows:

Use the catalyst drop-box linked from the course home page to turn in a pdf file containing your answer. The file should contain:

  1. Your algorithm
  2. An argument that your algorithm is correct: You may use any informal, but precise, style you wish. If you were unable to completely solve the problem, for instance to create an algorithm that runs in O(n) time, you should describe those problems. Be brief.
  3. The total amount of time you spent working on this problem

Be sure that your name appears at the top of your solution.

Note: Your solution file must be in pdf format, but it is okay to submit a scanned copy of a handwritten document as long as it is legible when printed and the total file size is no larger than 2-3MB or so.

Valid CSS! Valid XHTML 1.1