Homework 1

PGSS Computer Science Core

Your answers for this assignments may be handwritten or typed. They are due Thursday, July 10, at the beginning of class.

If you have code that you couldn't fix in time, you can still get partial credit if you include what you did write and describe the problem as best you can in a few succinct sentences. Identifying the problems with wrong code is much better than claiming that wrong code is correct, both in real life and in this class.

Please adequately comment your code. What we don't understand will naturally receive a poor evaluation.

1. Adding binary numbers

To become more familiar with manipulating binary numbers, we'll write a Java function to add two arbitrarily big positive numbers in binary representation. It will look like the following.

public static int AddIntegers(int[] result, int[] a, int[] b) {
    // Your code here...
}

Your code will accept two input arrays, a and b. Both arrays will contain only zeroes and ones (you can assume this), with the least significant (right-most) bit as the first element in the arrays. In other words, the decimal number 11, represented as 1011 in binary, would be represented as

  a[0] == 1
  a[1] == 1
  a[2] == 0
  a[3] == 1

because 1's bit is 1, the 2's bit is 1, the 4's bit is 0, and the 8's bit is 1.

Place the sum in result using the same representation. If the number doesn't fit in result, your function should return -1. Otherwise, it should return 0.

Java code to implement an interface for testing AddIntegers may be found on the course Web page as ``AddBigNumbers.java''.

For beginners: An acceptable, simpler problem is to assume that all three arrays have the same length. Handling three different lengths is more difficult; for those who have never programmed before, handling the more general case would be going an extra mile. If you choose to handle only equal-length arrays, be sure to comment your code to indicate that you know that the code does not meet the original specifications in this way.

2. Improving Prime-Test-All

In this problem, we investigate Prime-Test-All, of which we have a pseudocode description (page 4), a Java implementation (page 27), and a HYMN Assembly implementation (page 18). We note two possible improvements. You are to change the Java implementation to implement both improvements together. (You will receive partial credit for either improvement alone.) You will receive extra credit for doing either or both in HYMN Assembly language.

You can virtually half the number of iterations of the loop by initially testing whether 2 divides n and then trying only odd numbers. Here is a rough pseudocode description.
Algorithm Prime-Test-All(n)
if n is even then output NOT_PRIME fi
for each odd i such that 2 <= i <= sqrt(n) do
od
output IS_PRIME
This pseudocode is not perfect, however. Implement a fixed version of this improvement.
On many computers, multiplication takes much longer than addition or subtraction. In our implementations, we use multiplication to find squares of successive values for i. It happens that, for every positive integer m, the square of m is the sum of the first m odd integers. (Section A.3 proves this using mathematical induction.) Find a way to use this to remove all multiplication from the program.

You can (and should) test the Java code using the compiler on the Macintoshes. ``Prime.java'', from the course Web page, provides an interface for testing. Homework 0 tells how to download this code and how to use the Java compiler on the Macintoshes.

Because this problem is complicated and involves intermediate steps, be sure to save your work when you have met intermediate success, so that you can hand in whatever you have found that works. For this problem, it is better to submit working code with only one of the two improvements than to submit code for both that fails.

For beginners: Do the first improvement (trying odd n) first. Feel free to submit this improvement alone. Doing the second improvement is, again, going the extra mile for people just getting started with programming.

Extra credit: Implement either of the two improvements or both using the HYMN assembler. To test your assembly code, you can use a HYMN Assembler available through the Web page. This program simulates a machine with the instructions outlined in the course notes. Unfortunately, it's a pain to use. You will want to think carefully about how to alter the code before trying the on-line assembler. For this reason, implementing improvements in Java first is strongly encouraged.