Given the following code to compute "n to the power of x"

 
static int fastPower(int n, int x){
		int a= x; int b= 1; int i= n;
		while(i>0) {
			if (i%2==0){
				a= a*a;
				i= i/2;
			}
			else {
				b= a*b;
				i= i-1;
			}
		}
		return b;
	}

Which of the following logical statements is a valid and useful invariant for proving this code does actually compute n to the power of x?

Which is an post-order traversal of the following tree

                        t
              /                 \
            h                   a
         /      \             /      \
       n         k           s        k
      /  \      / \        /   \     /   \ 
     i    v    e   r      y     m   u    c
   /     /
  h    s
 / \
k  i

Which is an breadthfirst traversal of the following tree?

                        t
              /                 \
            h                   a
         /      \             /      \
       n         k           s        k
      /  \      / \        /   \     /   \ 
     i    v    e   r      y     m   u    c
   /     /
  h    s
 / \
k  i

Each of the following code snippets finds the value target in a sorted list lst.  Which is using divide and conquer?  If you spot any errrors in the code, ignore them and answer for a corrected version of that snippet.

What line of code at line XXXXX will result in ThisData being a recursive data type?

class ThisData{

    XXXXX

    int value;

}

Which of the following numerical sequences is ameanable to dynamic programming?  I.e. which could be significanlty sped up by applying dynamic programming to the programming of an algorithm to compute each value in the sequence?  You may assume for all that

m(0) = 0

m(1) = 1

m(2) = 2

Which of the following definitions of recursive data is most correct?