CSE 321 Winter 2010
Homework #2

Due Wednesday, January 20th at the start of lecture.  Bring to class to turn in.

1. [10 points] Section 1.3, problem 10.

2. [10 points] Section 1.3, problem 12.

3. [10 points] Section 1.3, problem 14.

4. [10 points] Section 1.3, problem 38.

5. [10 points] Section 1.3, problem 40.

6. [10 points] Section 1.3, Problem 48: use Natural Deduction to prove
   both these statements.

7. [10 points] Section 1.4, problem 12, only the odd numbered
     questions: a, c, e, g, i, k, m, o

8. [10 points] Section 1.4, problem 32.

9. [20 points] Let a, b, c be three integer arrays of dimensions m, n,
   and p respectively.  For each of the two sentences below, write a
   Java fragment that checks if the sentence is true.  The expression
   |x - y| denotes the absolute value of x-y.

  (i) forall i in [0..m-1].
          (exists j in [0..n-1].
              (forall k in [0..p-1]. (|a[i]-b[j]| > |b[j] - c[k]|)))


  (ii) forall i in [0..m-1].
        (exists j in [0..m-1]. (j >= i and 
                               a[i] = a[j] and
                               (forall k in [0..m-1]. k >= j ==> a[i]<a[k])))


EXTRA CREDIT [10 points].  The following program fragment takes n^5
iterations:

{
Boolean f = true;
for (int x=0; x<n; x++)
  for (int y=0; y<n; y++)
     for (int z=0; z<n; z++)
        for (int u=0; u<n; u++)
            for (int v=0; v<n; v++)
                  if (a[x][z]==0 && b[z][v]==2 && c[v][y]==1 && d[y][u]==3)
                     f = false;

if (f) Systems.out.println("YES");
else  Systems.out.println("NO");
}

Write an equivalent program that consists of four non-nested loops,
each with n^2 iterations, for a total time of 4n^2.

Hint: think about "reusing variables" in predicate calculus.