CSSE Monash University .au CSE2304 2001 tute Notes

Notes on some of the tutorial questions.

T1

1. 1st year revision
2. action, not a question
3. by induction
   • (a) base case L1=nil
     length (append L1 L2) = length (append nil L2) = length L2 = 0 + length L2 = length L1 + length L2
   • (b) general case L1 = cons H T
     length (append L1 L2) = length (append (cons H T) L2) = length cons H (append T L2) = 1 + length append T L2
     = 1 + length T + length L2 {by induction on |L1|}
     = length (cons H T) + length L2 = length L1 + length L2
4. Keep index pointers, `first' and `last' to the ends of an EOR. Try to increase last until the end of the data is reached, or until the condition is violated, i.e. three odds or three evens adjacent. Now increase first, but as little as possible which is [_________?]. Remember the longest run seen during this process.
5. Argument depends on program. Termination: Probably involves an increasing index which must eventually meet the end of the array, switching the loop control test. Correctness: Probably an invariant including  A[first..last] being the longest EOR in A[0..last], that terminates at A[last]. Thus when last>=N ...

T2

1. -
2. -
3. 1.

     /* PRE: N >= 1 */
     biggest = A[0];
     for(i=1; i < N; i++)
     /* INVARIANT: biggest is largest value in A[0..i-1] */
        if(A[i] > biggest) biggest = A[i];
   
     /* POST: biggest is largest value in A[0..i-1] and i=N,
        so biggest is largest value in A[], as required. */
     

   Termination: i increases, must reach N, program then halts.
4. 1. 30
   2. 55
   3. 100
5. Notes: We need to find the right-most number in the partition that can be incremented. A number cannot be incremented if it has the same value to its left, nor if it is the last number in the partition. So find the right-most number, A[i] say, that can be incremented and increment it. Now replace the partition to the right of A[i] by the all 1's, to the appropriate length.
   e.g. 2+1+1+1 --> 2+2+1, or 3+2 --> 4+1.
   Should be able to turn that into code.

T3

1. A bit of 1st year Boolean algebra in another guise
   • base case L = nil
     not (reduce and true L) = not (reduce and true nil) = not true = false = reduce or false nil = reduce or false (map not nil) = reduce or false (map not L)
   • general case, L= cons h t
     not (reduce and true L) = not (reduce and true (cons h t)) = not (and h (reduce and true t)) = or (not h) (not (reduce and true t)) = or (not h) (reduce or false (map not t)) --by induction on list length = reduce or false (cons (not h) (map not t)) = reduce or false (map not (cons h t)) = reduce or false (map not L)
2. You should end up with something like [Radix Sort].
3. -
4. Something like

     search( Tree T;  Int Lo, Hi )
     // PRE: T is a binary search tree
        if T is not empty then
   	e := T.element;
   	if e > Hi then
   	   search( T.left, Lo, Hi ) // don't waste time on right
           else if e < Lo then
   	   search( T.right, Lo, Hi ) // don't waste time on left
           else // e is between Lo and Hi inclusive
              search( T.left, Lo, Hi );
              print e;
   	   search( T.right, Lo, Hi )
           end_if
        end_if
   

T4

These questions were for general discussion.

T5

1. -

2. #include <stdio.h>
   #include <stdlib.h>             /* C by Tony Jansen, April 2001 */
   
   void pb(int open, int closed, int index, char *s)
   /* PRE: open >= closed >= 0 */
   {
           if (open + closed == 0) {    /* none left to do, so done */
                   printf("%s\n", s);
                   return;
           }
           if (open == closed) {         /* only option is to add ( */
                   s[index] = '(';
                   pb(open-1, closed, index+1, s);
           }
           else if (open == 0) {         /* only option is to add ) */
                   s[index] = ')';
                   pb(open, closed-1, index+1, s);
           }
           else { /* assert: open > closed > 0 */
                   s[index] = '(';                   /* try both ... */
                   pb(open-1, closed, index+1, s);     /* ( ...  and */
                   s[index] = ')';
                   pb(open, closed-1, index+1, s);     /* ) ...      */
           }
   }
   
   
   int main(int argc, char *argv[])
   {
           int     num;
           char    *s;
   
           if (argc != 2) {
                   printf("Usage: program num_pairs_brackets\n");
                   exit(0);
           }
           num = atoi(argv[1]);
           s = (char *) malloc (sizeof(char) * (2 * num + 1));
           s[2 * num] = '\0';
   
           pb(num, num, 0, s);
   
           return 0;
   }
   

3. We have done plenty of these in lectures.