COMPUTING SCIENCE 310
Algorithm Design and Analysis

Assignment 1

Due Date: Wednesday, Jan. 28, at the start of the class session (10:30 a.m.)

Exercises

1. Do Exercise 1.6 (page 61), but write your solution in Java rather than in pseudocode. Test your code using an actual Java compiler and run-time system. Solve the problem specified in the exercise (i.e., calculating the ceiling of the base-2 logarithm of n+1 for any nonnegative integer n) in a function (static method), and write a test driver in main that shows the outputs of the function for inputs 0 .. 9 and -3. Use an assert statement in the function to ensure that its argument is nonnegative. See the Hints section below for tips on using assertions in Java.

2. Do Exercise 1.27 (page 64).

3. Do Exercise 3.4 (page 141).

4. Do Exercise 3.7 (page 143).

5. Do Exercise 3.8 (page 143).

6. Do Exercise 3.12 (page 145).

7. Implement Quicksort in Java using the three improvements to the algorithm suggested in the textbook:

   • use median-of-three pivot selection
   • use Insertion sort to sort small subsets
   • do stack space optimization

   Test your implementation using Cay Horstmann's sort testing and timing framework from Big Java or Computing Concepts with Java Essentials, and compare the performance of your version of the algorithm with that of his implementation. Use QuickSortTest to ensure that your implementation works correctly, then use QuickSortTimer (with very large arrays) to compare the performance of the two implementations of the quicksort algorithm.

   ArrayUtil.java     QuickSort.java     QuickSortTest.java     QuickSortTimer.java     StopWatch.java

Submission

Hand in a hardcopy of your assignment solutions. Hand-written or -printed answers are acceptable (and encouraged, to save you time), but please ensure that all answers are clearly legible.

Also submit the Java programs written in response to questions 1 and 7 of this assignment in electronic form using the following submission form:

Java program to calculate the ceiling of the base-2 logarithm of n+1


Optimized Java implementation of Quicksort (only file QuickSort.java)

Web Password

Your assignment submissions are password-protected. These passwords apply only to form data submitted via the Web server. They are separate from (and typically different from) your network password or the password for your Unix account (if you have one).

Hints

Assertions

Assertions are a built-in part of Java beginning with version 1.4 of the SDK. An assertion takes the form of a statement that includes a condition (as opposed to a method call that accepts a parameter). For example, to check that x is less than 100, write

   assert x < 100;

To compile a program with assertions, ensure that the compiler conforms to version 1.4 of the language by specifying:

   javac -source 1.4 <program>.java

You must also enable the checking of assertions at run time:

   java -enableassertions <program>

or, in abbreviated form:

   java -ea <program>

If you are using a Java IDE to develop your program, you will have to ensure that the IDE is using a version 1.4 compiler and that assertions are enabled. BlueJ appears to have assertions enabled by default. To use Eclipse, set the Java language version to 1.4 as follows:

Select menu options Window - Preferences, then Java - Compiler - Compliance and Classfiles, and set Compiler compliance level to 1.4.

Then enable assertions:

Select menu options Run - Run..., select the Arguments tab, and enter "-enableassertions" (without the quote marks) under VM arguments.

For those who insist on using TextPad under Windows, you can enable assertions as follows:

• Choose menu options Configure - Preferences... - Tools - Compile Java
• Revise the contents of the "Parameters" text box to read

     -source 1.4 $File

• Under Tools - Run Java Application, revise the "Parameters" text box to read

     -enableassertions $BaseName

• Click OK.