<<<[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:

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