CPSC 2120 - DAY 5
MAY 17, 2016

===============================================================================

QUIZ REVIEW

Permutations of 100 Objects can be represented by 100! O(n!)

Printing diagonals of a NxN matrix is O(n)

2. (10) Consider the following nested loops.  For each, determine the order of 
complexity counting multiplications..  Show clearly how you arrived at your 
answer.
 
   (a) for (int i=0; i <= 10; i++)
          for (int j=0; j < n; j++)    
             M[i][j] = i*n + j * 5;
        
Outer loop executes 11 times.  For each iteration, inner loop executes n times.  2 multiplications per inner loop iteration.  Hence:

	2 * 11 * n = 22n multiplications => O(n) complexity



   (b) for (int i=0; i < n; i++)
          for (int j=0; j <= i; j++)    
             M[i][j] = i*n + j * 5;

Outer loop executes n times.  For each value of i, the inner loop executes (i+1) times. For this type of problem, we should build a table.

Build a table:               i   0   1   2   3   …   (n-1)
                 #j-iterations   1   2   3   4         n

Therefore, total #j-iterations = 1 + 2 + 3 + … + n = n(n+1)/2

Two multiplications per j-iteration 

=> total multiplications = 2[n(n+1)/2] = n(n+1) = O(n2)


BINARY TREES

A BINARY TREE MUST HAVE ONLY TWO CHILDREN FOR EACH NODE.

  0   1   2    3    4    5    6
| 5 | 9 | 12 | 15 | 16 | 18 | 24 |
----------------------------------


              (15)               <---------------Root
	    /      \
        (9)         (18)         BINARY SEARCH TREE
      /     \      /    \
    (5)    (12)   (16)   (24)    <---------------Leaves



Implementation

-Nodes and Links
-One Arrays
-Three Arrays

Traversals
-Preorder, Inorder, Postorder

K-ary Trees
- Converting trees k-ary <-> binary

DEFINITIONS

Nodes - Interior Nodes in center, Root is beginning
Edges - 
Degree - Number of Children
Height - distance from leaves
Interior node - not root, not a leave
Descendants of "A" are including a, proper descendants do not include A itself

Doubly linked lists can be represented as a binary tree


Using one array, we can implement an binary tree
Left child is less, right child is greater when implementing binary search tree

left child of A[i] is A[2i]
right child of A[i] is A[2i+1]

To place elements into the array, you can start at the root and read down,
left to right moving downward.  This produces the same result as doing A[2i]
or A[2i+1]

(10)
   \
   (12)
     \
     (15)
       \
      (19)
	\
	(20)

  0   1    2   3    4   5   6   7    8   9  10         15        31
|   | 10 |   | 12 |   |   |   | 15 |   |   |   | ... | 19 |... | 20 |
---------------------------------------------------------------------


Three Array is good to use if the language has no nodes and pointers

Must have root variable and then three arrays

               0  1  2  3  4  5  6  7  8  9
Object value:  D  -  -  -  A  -  B  -  C  -
int   lchild:  /  /  3  5  6  1  /  9  0  2
int   rchild:  /  /  /  /  8  /  /  /  /  /

Other variable declarations necessary...
root = 4
freelist = 7
null = “/” = -1