<<<[ans 1-3]<<<   [CSE2304] [progress]

Tutorial #4, 2000

#4 was intended to form the basis of general discussions about prac's #4 and #5. So there are no solutions as such.

Tutorial #5, 2000:

C
o
m
p
.
S
c
i
.

M
o
n
a
s
h

a
u

1: Here's something approaching an algorithm. Assume typedefs and function definitions as appropriate. This code requires X and Y to be of about the same number of digits (padding with leading zeroes if necessary). Note how there are no arithmetic operations in the code apart from shifts (constant time), additions and subtractions (linear time) and multiplication.

BigNum mult(BigNum X, BigNum Y)
{ BigNum X1, X0;
  BigNum Y1, Y0;
  BigNum X1Y1;
  BigNum X0Y0;
  BigNum Middle;
  int n;

  /* Get size of the numbers to multiply. */
  n = max(size(X), size(Y));

  if(n == 1)
  { //*Base case, do some normal multiplication */
    return normal_mult(X,Y);
  }
  else
  { /* Recursive case, split the numbers into two. */
    split(X, n >> 1, &X1, &X0);
    split(Y, n >> 1, &Y1, &Y0);
    /* Calculate the three terms needed for the multiplication. */
    X1Y1 = mult(X1, Y1);
    X0Y0 = mult(X0, Y0);
    Middle = add(mult(sub(X0, X1), sub(Y1, Y0)), add(X1Y1, X0Y0));
    return add(add(X0Y0, shift(X1Y1, n)), shift(Middle, n >> 1));
  }
}

2: Use back-tracking. The return value of the function is used to mark when a successful pattern has been printed. Otherwise the progam will print out all sequences of length l:

int Thue(int A[], int n, int l)
{ int i;

  if(n == l)
   { printsequence(A, l);
     return 1;
   }
  else /* n < l */
   { for(i = 1; i <= 3; i++)
     { A[n] = i;
       if(checksequence(A, n+1))
       { if(Thue(A, n+1, l)) return 1;
       }
       else
         return 0;
     }
   }
}

int checksequence(int A[], int n)
{ /* NB. we know that A[0..n-1] is a Thue sequence,
     that was checked at the previous rec' level,
     so here we only have to check if
     A[n-2*i .. n-i-1] == A[n-i .. n-1]
     for any i in 1 .. n div 2,
     returning false if so.
  */
  ...
}
 

3: See course notes.

- © Debbie Pickett, 2000



2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia