Notes on some of the questions.

**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 Tan alternative representation for Q1:

p=> q | q | ||
---|---|---|---|

F | T | ||

p | F | T | T |

T | F | T |

**4**.

base case, L1=nil:

general case, L1=cons H T:

**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.

**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,

Therefore the second largest element is either #3 or #1, and
The second largest value is 1.75.

**4**.

- (n+1)×(n+2)/2
- (2n+1)×5
- n×(1+2n-1)/2 = n
^{2}

**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

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

**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. #questions times.`01`

(NB. >> is right-shift in**C**, not ``much greater than'' as in mathematics.)

1. 1×(1×3+4×3+1×5)/3 = 1×20/3
= 6 ^{2}/_{3}
--[Simpson]

2. Integral of x^{2}-x+3
is x^{3}/3-x^{2}/2+3x.
Range is [0,2].

[x^{3}/3-x^{2}/2+3x]_{0}^{2}
is 2^{3}/3-2^{2}/2+3×2
= 8/3-2+6 = 6 ^{2}/_{3}.

(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.

© L. Allison, School of Computer Science and Software Engineering, Monash University, Australia 3800. Created with "vi (Linux & IRIX)", charset=iso-8859-1