Homework 2

PGSS Computer Science Core

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

Any partial answers are acceptable and will be judged according to your background. Be sure to describe in comments exactly which parts your code is to do. If you know of problems with your code, be sure to describe those too as well (but succinctly) as you can. It is far better to know what's wrong with your work than to claim that it is correct.

Please format and adequately comment your code. What we don't understand will be graded accordingly.

1. Cryptographic protocols

This is for the non-programming section. Others can try it, too, though. Section 11.4 of the course notes is the assumed background.

One application of cryptography is in voting schemes. How can we vote without revealing our ideas?

You might think of trying the communicating the total as we discussed in class and as described in Section 11.4 in the course notes. Each person's ``test score'' would be 1 if voting yea, 0 if voting nay. Communicating the total, then, will tell us how many vote yea.

Take five or fewer sentences to describe problems with this idea. Assume that all can accurately tell who sent all information they received, and assume that nobody can eavesdrop.

2. Spreadsheet

In this problem we develop a spreadsheet. You may well have used a spreadsheet before. A spreadsheet is an office application that allows one to easily compute values.

The spreadsheet we'll develop is one-dimensional. It has 16 boxes to hold real numbers. These are labeled #0 to #15. The value of any box can either be a constant number (such as -23.2), a reference to another box (#4), or a single arithmetic combination of these (#3 + #5, or 2 * #0).

As an example, in the following table the second column holds the formulas for each box and the third column tells what would be displayed on the spreadsheet.

  box  formula     displayed value
  # 0: -23.2         -23.2
  # 1: #4              7.5
  # 2: #3 + #5       -78.6
  # 3: 2 * #0        -46.4
  # 4: 15 / 2          7.5
  # 5: #0 - 9        -32.2
   ...

The provided code, ``Spreadsheet.java'', handles the interface and interprets the formulas. Your job is to write a function to compute the values after they are parsed. The provided code will display the values.

The function takes many parameters, but don't let this daunt you. Here's the declaration.

  public static void EvaluateSpreadsheet(double[] result, int[] optor,
      int[] lhs_type, double[] lhs, int[] rhs_type, double[] rhs,
      double undefined) {
	// Your code here
  }

All arrays have sixteen entries. The function's job is to put the numbers that should be displayed into result. The formula in the ith box is specified by a combination of optor[i], lhs_type[i], lhs[i], rhs_type[i], and rhs[i].

optor[i]: 0 if the formula uses addition, 1 for subtraction, 2 for multiplication, and 3 for division.
lhs_type[i]: negative if the left operand is a constant (like -23.2), otherwise the number of the box from which the left operand is to be taken.
lhs[i]: if the left operand is a constant, this will be that constant.
rhs_type[i]: negative if the right operand is a constant, otherwise the number of the box from from which the right operand is to be taken.
rhs[i]: if the right operand is a constant, this will be that constant. The final parameter is undefined. This value should be assigned to any box whose value cannot be computed for some reason. (If your code can't handle the formula for line i, it should make value[i] be undefined.)

The above example would be passed to the function as follows.
```
   i    optor  lhs_type   lhs   rhs_type  rhs
  # 0:    0       -1     -23.2    -1       0
  # 1:    0        4     undef    -1       0
  # 2:    0        3     undef     5     undef
  # 3:    2       -1       2       0     undef
  # 4:    3       -1      15      -1       2
  # 5:    1        0     undef    -1       9
```
Your code will compute which values to put into the boxes. (Currently the function refuses to compute any values by placing undefined in all boxes.)

This problem has a number of intermediate steps. See how far you can get.
1. Assume all numbers appearing are constants; every lhs_type[i] and rhs_type[i] is negative.
2. Assume all box references are to boxes obeying step 1. (If box 0 is #1, box 1 refers to no other boxes.)
3. Assume there are no circular references. (So we can't have #1 + #3 in box 0 and #0 / 3 in box 1, since they refer to each other.)
4. Assume nothing.
A strong beginner's performance would accomplish the second step. A good answer for others (truly outstanding for beginners) will accomplish the third step. The fourth step is extra credit.