Sketch solutions for tutorials

For week 3

Question 3

 Use a pointer-based implementation:
       struct treeNode {
             itemType item;
             treeNode* LChildPtr;
             treeNode* RChildPtr;
       };

       typedef ptrType treeNode*;
          

 
          int count( ptrType t ) {
          if (t==NULL) return 0;
          else { int left= count (t -> LChildPtr);
                 int right= count (t -> RChildPtr);
                 return 1 + left+ right;}
       } 

         int max( ptrType t ) {
          if (t==NULL) return 0;
          else { int left= max (t -> LChildPtr);
                 int right= max (t -> RChildPtr);
                  if (right > left) returnright;
                  else return left;}
       } 
       
       
            int sum( ptrType t ) {
          if (t==NULL) return 0;
          else { int left= sum (t -> LChildPtr);
                 int right= sum (t -> RChildPtr);
                 return (t-> item) + left+ right;}
       } 
       
       
Question 4


   3                 W
                 /
                T etc (linear tree)

    
            
                W
              /
             T 
           /
          ..   
        etc left down to A, then
           
        A
         \
          B
           .. etc right down to J

       A
        \
          B
           \
            W
          /
         J
       /  \
      E    N
            \ 
              T

For Week 4

2.  (This is hard.)
The algorithm has two phases:
  (i) Inorder traversal to read the files into an array; 
  (ii) add the nodes one at a time to maintain a balanced tree.
  
Phase (i) takes O(n) (the tree has n nodes)
Phase (ii) is a O(nlog(n)^2)

To see that, suppose we have a full tree containing about O(2^k) nodes.
Such a tree has height k
To fill up the next level (k+1) we need to insert 2^k more nodes (each leaf grows
two children).
To insert one leaf requires a search to depth k, so takes O(k), and we do that 2^k times,
thus to grow the tree to level (k+1) takes O(k*2^k)

To finish off we take the sum  SUM (k*2^k) which comes out to be in the worst case O(nlog(n)^2)
                                (1.. log (n))
                                
3. 

    In this diagram
   i is horizontal and j is vertical.  I've only filled in the spaces which correspond
   to even lines of money left on the table, and also those entries required to fill in
   the (5, 5) space.
   
   
        0    1   2   3   4   5
       ==========================
    
   0    0
   
   1    4    0
   
   2    *    8   0     
   
   3    10   *   8   0
   
   4    *    9   *   2   0
   
   5    11   *   10  *   2   0
      
      
4. The following algorithm can be used to compute the player's optimal
strategy in real-time.  Given a valid input (an (i, j) representing V[i..j] portion
of the input array, it sets up a Strategy table which prints out 'l' or 'r' 
to indicate that Player 1 should remove the left or right coin.   To compute this
table, every time a new entry of the LookUp table is calculated we compute Strategy[i][j]
at the same time to be 'l' if the LookUp entry indicates to take V[i] and 'r'
if the LookUp entry indicates to take V[j] (given by the solution of the little
minimax (see the lecture notes).

Below is the code which you can demonstrate plays the game in real time.  

#include<iostream>

using namespace std;

class Game {

public:

Game (int M[], int n);

int maxWin(int i, int j);

char getStrategy(int i, int j);


private:
char Strategy[10][10]; // 'l' for left, 'r' for right.
int LookUp[10][10]; // Assumes line of money no more than 10
int V[10];
int l;
};

Game::Game (int M[], int n):l(n) {
for (int i = 0; i < n ; i++)
  V[i]= M[i];
  
for(int i= 0; i < n; i++)
  for (int j= 0; j< n; j++)  
    LookUp[i][j]= -1;
  
for (int i = 0; i < n ; i++)
  LookUp[i][i]= 0;
// Player 2 picks up the last piece  
  
for(int i= 0; i < n-1; i++) {
  if (M[i] > M[i+1]) {LookUp[i][i+1]= M[i];
                      Strategy[i][i+1] = 'l';}
  else {LookUp[i][i+1]= M[i+1];
        Strategy[i][i+1] = 'r';}
 } // lines of length 2: Player 1 goes first
}

int Game::maxWin(int i, int j) {
// This complexity is O(n^2)
  if(j < i || j >=l || j < 0) return 0; // Invalid games
  if (LookUp[i][j] != -1) return LookUp[i][j]; // Already computed the answer
  else { // Otherwise compute it
    int minab;
    int a= maxWin(i+1, j-1) + V[i];
    int b= maxWin(i+2, j) + V[i];
      if (a > b) minab= b; 
      else minab= a;
    int mincd;  
    int c= maxWin(i,j-2) + V[j];
    int d= maxWin(i+1,j-1) + V[j];
     if (c > d) mincd= d; 
      else mincd= c;
      
    if (mincd < minab)  // Optimal move is to take the left
         {LookUp[i][j]= minab; Strategy[i][j]= 'l'; return minab;} 
    else // optimal move is to take the right.
         {LookUp[i][j]= mincd; Strategy[i][j]= 'r'; return mincd;} 
      
  }}
  
char Game::getStrategy(int i, int j) {
  if (i >= j) return 'n';
  else { maxWin(i, j);
  return Strategy[i][j];
  }
} 
  


int main () {

int A[]= {2, 4, 8, 2, 1, 2};

Game line(A, 6);

cout << "Maximum winnings of Player 1 is ... " <<  line.maxWin(0, 5) << endl;
int i, j;
while (true) {
cout << "input a valid range " << endl;
cin >> i >> j ;
cout << "next optimal move is " << line.getStrategy(i, j) << endl;
}
}

For week 5


1)                cgata      gata       ata       ta       a       ""
    
    
    gtcata        4           4           3         2        1      0
    
    tcata          4           3           3         2         1      0
    
    cata            4          3            3         2        1       0
    
    ata              3          3            3         2        1       0
    
    ta                2          2             2         2        1       0
    
    a                  1          1            1          1        1        0
    
    ""                0            0            0          0        0        0
    
 
 
                 
    2) Smallest number of values is 5 (f(n-1), f(n-2)... f(n-5))
    
           Just like iterative Fibonacci, but with this difference equation, and five extra
           variables to store the last five results.
           
           
    3)      This is just sketched solution, for computing the table.
           
           // initialise LookUp to -1 first of all
           // infty is a convenient very large number which dominates everything.
          // check to see that the LookUp doesn't already exist
          if (LookUp[i][j] == -1) {  //
            if( i >= n-1)  LookUp[i][j]= c[i][j];  // base case
             else { int d, l, r;
                      if (j >= n-1 || j < 0) {d= infty;} 
                      else { d= minCost(i+1, j);}    
                     if (j-1 >= n-1 || j-1 < 0) {l= infty;}  
                      else l= minCost(i+1, j-1);
                      if (j+1 >= n-1 || j+1 < 0) {l= infty;}  
                      else {r= minCost(i+1, j+1);}
                     LookUp[i][j]= c[i][j] + minimum of (d, l, r);
                 }
           
           
           
           
    4) Inorder:         h d b i e  a f c j g k
         Preorder: a b d h e i c f g j k
         Postorder:  k j  g f c i e h d b a     
    
    
FOr week 6

1.  The code for Quicksort (reproduced in lectures) is in Carrano.
    This approach keeps the pivot item in the correct place as it goes.

You could also ask them why this program should terminate:
it's because the unknown region (defined by the indices b and c)
is reduced at each stage.

void swap(int a[], int i, int j) {
int temp= a[i];
a[i]= a[j];
a[j]= temp;
}

void partition(int A[], int F, int L, int& index){
int p= A[F];    
int c= L;  
int b= F;
int unknown= F+1;

while ( unknown <= c ) {
  if (A[unknown] <= p ) {swap(A, b, unknown); b++; unknown++;}
  else if (A[unknown] > p) {swap(A, c, unknown); c--;}
}  
 index= b;
}



.  The partition function is defined in the Carrano (reproduced in lectures)
     
      FirstUnknown is the index which always points to the next unexplored position;
      p is the pivot item (at A[F]);
      LastS1  is the index that points at the very last item in the < p segment.
   
    swaps occur in two places:
     (a) When A[firstUnknown] < p , item A[firstUnknown] and A[LastS1+1] are swapped;
     (b) At the end when item A[F] and A[LastS1] are swapped.

     (a) Here the item is swapped with itself when firstUnknown == LastS1+1,
         which may happen initially;

     (b) Here the item is swapped with itself when LastS1 == F, which might
         happen if all the other items are >= p.

     Change the code:

     before the first swap, put a test: if (LastUnknown != LastS1+1) ... do the swap...
     before the last swap, put a test: if (LastS1 != F) .... do the swap...

    
    
    THe criteria are:

    (a) Base case: When F >= L, nothing to sort;
    (b) For any partition partition element, the calls of QuickSort are
        QuickSort(A, F, i-1)
        QuuickSort(A, i+1, L), and the portions of the array being sorted
        are strictly smaller than the original call;
     (c) (Correctness) The partition element is placed in its correct final position,
         and the partition function moves all items to the correct
         positions relative to the partition.

(3)
Pre-order means the current node is processed before the children;
Use the standard pre-order code for binary trees, but use a loop
to go through the nodes.


(4)
Use the invariant:

"if i is an index st. F <= i < idx1 then A[i] < P AND
  if i is an index st. idx1 <= i < idx2 then A[i] == P AND
  if i is an index st. idx3 <= i <= L then A[i] >P"

This means the "unknown region" is between idx2 and idx3.


 void FatPartition(int A[], int F, int L, int& b1, int& b2);
      int idx1= F;
      int idx2 = F;
      int idx3= L+1;

while ( idx2 < idx3 ) {
   if (A[idx2] > P) {idx3--; swap(A, idx3, idx2);}
   else if (A[idx2] == P) idx2++;
   else {swap(A, idx1, idx2); idx1++;idx2++;} 
 }  
  b1= idx1-1;
  b2= idx2-1;
}

(5)
loop invariant: sum = integers strictly between X and i.

Initialisation sets i to X and sum to 0 --- there are no integers strictly between X and X
hence the invariant is established.

New sum = {Old sum} + old i
               =  {sum of integers strictly between X and old i} + old i
               = sum of integers strictly between X and new i.
               
Termination condition is i == Y+1,
thus "the sum of integers strictly between X and Y+1" is the same as 
         X + X+1 + .... + Y, which is the postcondition.