Java Need help implementing an algorithm

Question

This algorithm is so advanced for my basic programming skills that I just don't see how I could implement it. I'm posting this in a new question because I can't keep bothering the guy who gave me the algorithm alone about this in the comment section in the previous question.

MaxSet(node) = 1 if "node" is a leaf
MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) },  
                       Sum{ i=0..1: MaxSet(node.Children[i])      })

Thanks too mehrdad for the algorithm.

The problem here for me is to implement the part of the two sum lines, how can I do that? And I need to mark every node that this algorithm chooses. It's just a "marked" variable in the node class set to true. I don't understand were it makes a decision too choose a node?

EDIT to include my code so far:

public int maxSet(Posisjon<E> bt){
     if (isExternal(bt)){
      return 1; 
     }
     return Math.max(1 + helper1(bt), helper2(bt));
    }

private int helper1(Posisjon<E> node){
 int tmp = 0; 
 if (hasLeft(node)){
  if(hasLeft((Position<E>)node.leftChild())){
   tmp += maxSet(node.leftChild().leftChild());
  }
  if(hasRight((Position<E>)node.leftChild())){
   tmp += maxSet(node.leftChild().rightChild());
  }
 }
 if(hasRight(node)){
  if(hasLeft((Position<E>)node.rightChild())){
   tmp += maxSet(node.leftChild().leftChild());
  }
  if(hasRight((Position<E>)node.rightChild())){
   tmp += maxSet(node.leftChild().rightChild());
  }
 }
 return tmp; 
}
private int helper2(Posisjon<E> node){
 int tmp = 0; 
 if(hasLeft(node)){
  tmp +=maxSet(node.leftChild());
 }
 if(hasRight(node)){
  tmp +=maxSet(node.rightChild());
 }
 return tmp; 
}

This seems to be working, what is left now. Is to actually mark the nodes as chosen? Were would I do that?

---

Updated with code:

public ArrayList<Posisjon<E>> getSelectionSet(Posisjon<E> bt, ArrayList<Posisjon<E>> s){
     if(bt.marked){
      s.add(bt);
     }
     if(hasLeft(bt)){
      if(hasLeft(bt.leftChild())){
       getSelectionSet(bt.leftChild().leftChild(),s);
      }
      if(hasRight(bt.leftChild())){
       getSelectionSet(bt.leftChild().rightChild(),s);
      }
     }
     if(hasRight(bt)){
      if(hasLeft(bt.rightChild())){
       getSelectionSet(bt.rightChild().leftChild(),s);
      }
      if(hasRight(bt.rightChild())){
       getSelectionSet(bt.rightChild().rightChild(),s);
      }
     }
     return s; 
    }

public int maxSet(Posisjon<E> bt){
     if (bt.visited){
      return bt.computedMax; 
     }
     bt.visited = true; 
     int maxIfCurrentNodeIsSelected = 1 + helper1(bt);
     int maxIfCurrentNodeIsNotSelected = helper2(bt);
     if (maxIfCurrentNodeIsSelected > maxIfCurrentNodeIsNotSelected){
      bt.marked = true; 
      bt.computedMax = maxIfCurrentNodeIsSelected; 
     }else{
      bt.marked = false; 
      bt.computedMax = maxIfCurrentNodeIsNotSelected; 
     }
     return maxSet(bt);
    }

After submission, I will post the entire code for this!

Answer 1

You currently have does not memoize the return value of the function each time. Every time you call maxSet, you should check if you have already computed the result or not. If you have, just return it. If you haven't compute it and store it somewhere. Otherwise, your algorithm will be inefficient. (This approach is called "Dynamic Programming." Learn about it.)

// pseudocode:
public int maxSet(Posisjon<E> bt){
    if (visited[bt])
        return computedMax[bt];

    visited[bt] = true;        

    // You don't need to manually check for being a leaf
    // For leaves 'maxIfCurrentNodeIsSelected' is always larger.
    int maxIfCurrentNodeIsSelected = 1 + helper1(bt);
    int maxIfCurrentNodeIsNotSelected = helper2(bt);

    if (maxIfCurrentNodeIsSelected > maxIfCurrentNodeIsNotSelected) {
         shouldSelect[bt] = true;
         computedMax[bt] = maxIfCurrentNodeIsSelected;
    } else {
         shouldSelect[bt] = false;
         computedMax[bt] = maxIfCurrentNodeIsNotSelected;
    }
}

public Set getSelectionSet(Posisjon<E> bt, Set s) {
    if (shouldSelect[bt]) {
        s.Add(bt);

        // You should check for nulls, of course
        getSelectionSet(bt.leftChild.leftChild, s);
        getSelectionSet(bt.leftChild.rightChild, s);
        getSelectionSet(bt.rightChild.leftChild, s);
        getSelectionSet(bt.rightChild.rightChild, s);
    } else {
        getSelectionSet(bt.leftChild, s);
        getSelectionSet(bt.rightChild, s);
    }
    return s;
}

call getSelectionSet with the root node and an empty Set as arguments after you called maxSet.