CSE2304 Tute Notes, CSSE, Monash, .au, semester 1, 2002

Notes on some of the questions.

Tute 1

1 and 2.

   p  q  p=>q       !p  !q  !p=>!q  (p=>q)=>(!p=>!q)
   F  F   T          T   T    T           T
   F  T   T          T   F    F           F
   T  F   F          F   T    T           T
   T  T   T          F   F    T           T

4.
base case, L1=nil:   sum(append nil L2) = sum L2 = 0 + sum L2 = sum L1 + sum L2

general case, L1=cons H T:   sum(append (cons H T) L2) = sum(cons H (append T L2)) = H + sum(append T L2) = H + (sum T + sum L2) {--by induction on |L1|} = (H + sum T) + sum L2 = sum(cons H T) + sum L2

5 and 6.

  /* PRE: m >= 0 */
  negatives = 0;
  maxLen = 0; startMaxLen = 0; /* best to date (i.e. nothing yet) */
  startCurr = 0;
  for( i = 0; i < N; i++ )
  /* INV: A[startCurr..i-1] is the longest suitable interval
          that finishes at position i-1, and
          negatives == the # of -ve numbers in A[startCurr..i-1], and
          A[startMaxLen..startMaxLen+maxLen-1] is the longest
          suitable interval contained in A[0..i-1]  */
   { if(A[i] < 0) negatives ++ ;

     /* ? A[startCurr..i] may be invalid ? */
     while( negatives > m )
     /* INV: negatives == the # of -ve numbers in A[startCurr..i] */
      { if( A[startCurr] < 0 ) negatives -- ;
        startCurr ++ ;
      }
     /* ASSERT: negatives <= m, i.e. A[startCurr..i] is valid and is the
                longest suitable interval that finishes at position i, etc. */

     currLen = i-startCurr+1; /* is the current one the best so far? */
     if( currLen > maxLen )   /* if so remember the details */
      { maxLen = currLen;
        startMaxLen = startCurr;
      }
   }
  /* POST: INV & i==N
        => the longest interval is A[startMaxLen..startMaxLen+maxLen-1] */

Termination: The inner while-loop must terminate, if for no other reason than an interval of length zero contains zero negative numbers -- if m were as small as zero. The outer for-loop must terminate when i==N.
Correctness follows from the invariants and other assertions in the code.
Complexity: Each element of A[] is examined at most twice, once as A[i] and maybe again as A[startCurr], hence O(N)-time.

Tute 2

1. This is a little puzzle or "competition", many interesting answers are possible, not one best answer, e.g.... think about the parity of x+y+z and x*y*z.

2 and 3: If the following people have the indicated heights,   0: anne 1.68m, 1: bill 1.82m, 2: carol 1.75m, 3: dave 1.82m, 4: elle 1.69m, 5: fred 1.68m,   the two tallest people are bill and dave, and the third tallest person is carol.
Therefore the second largest element is either #3 or #1, and The second largest value is 1.75.

4.

1. (n+1)×(n+2)/2
2. (2n+1)×5
3. n×(1+2n-1)/2 = n²

5. It is, as always, "just" a matter of looking at the problem correctly. Scanning from the left, you must pass at least as many `(' as ')' at any point, i.e. ())... is illegal. Scanning from the right, you must pass at least as many ')' as '(' at any point, i.e. ...(() is illegal. You want to find the next string, i.e. you want to move one of the ')' left. You want to move the rightmost ')' that can be moved. This must be the first ')' from the right such that 1. it would not violate "at least as many ')' as '(', and 2. it has a '(' immediately to its left. When (if) you have found such a ')' swap it with the '(' to its left. Note, you are not done yet! Finally, everything to the right of the ')' must now be made as alphabetically early as possible, i.e. ((...))))

((())) -> (()())
  --        --^^

(()()) -> (())()
   --        --^

(())() -> ()(())
 --        --^^^

()(()) -> ()()()
   --        --^

Tute 3

2. A generalization of Q4, tute 1.

Prove: g (reduce g z L1) (reduce g z L2) = reduce g z (append L1 L2):

base case, L1 = nil:

g (reduce g z nil) (reduce g z L2) = g z (reduce g z L2) {-- by defn of reduce} = reduce g z L2 {-- note g z w = w, for all w} = reduce g z (append nil L2)

general case, L1 = cons h t:

g (reduce g z (cons h t)) (reduce g z L2) = g (g h (reduce g z t)) (reduce g z L2) {-- by defn of reduce} = g h (g (reduce g z t) (reduce g z L2)) {-- note g (g x y) z = g x (g y z), for all x, y & z} = g h (reduce g z (append t L2)) {-- induction, |t|<|L1|} = reduce g z (cons h (append t L2)) {-- by defn of reduce} = reduce g z (append (cons h t) L2) {-- by defn of append}

3. Base case: There is one unrooted tree over three leaf nodes. This tree has one internal (non-leaf) node, and 3 edges.
General case: A tree (in fact all possible trees) over n leaves can be formed by taking a tree over n-1 leaves, choosing any edge, and replacing the edge by a new internal node, the new leaf and 3 edges. Thus the number of edges goes up by 2=3-1.
So the number of trees over n leaves is: 1×3×5×...×(2n-5)

4. Minor variation on the standard binary-tree search algorithm -- make sure you can do it.

5. One possibility: Represent `a' by the bit pattern `01', `b' by `10', and don't care by `11'.
x and y match iff

xy = x & y; (xy>>1 | xy) & mask == mask

where  mask = 0101...   i.e. 01   #questions times.
(NB. >> is right-shift in C, not ``much greater than'' as in mathematics.)

Tute 5

1.   1×(1×3+4×3+1×5)/3 = 1×20/3 = 6 ²/₃   --[Simpson]

2. Integral of x²-x+3 is x³/3-x²/2+3x. Range is [0,2].
[x³/3-x²/2+3x]₀² is 2³/3-2²/2+3×2 = 8/3-2+6 = 6 ²/₃.

(PS. Q1 came from the same quadratic, but with the x-values right-shifted by one.)

3. You can use the [demo'] [programs] to check your answers for your graph.