1. Prove or disprove formally:

(a) The largest even prime number is 2.

For the following, study the definitions in the notes on Binary Trees.

(b) The number of leaf nodes (nodes with no children) in a full binary tree of height h is exactly 2^h .

(c) The total number of nodes in any binary tree of height h is less than 2^(h+1)

(d) The height of a complete binary tree containing N nodes is [log₂ N].

(e) The height of any binary tree containing N nodes is less than N.

(f) The number of internal nodes in a complete binary tree of N nodes is [N/2].

2. Prove or disprove formally that the number of digits needed in the binary representation of any positive number N is [log₂ N].

3. Algorithm A has running time T_A(n) = 10^6 + 10^4 n + 10^5 n^2 and algorithm B has running time T_B(n) = 3 n^3 , where n is the number of values the algorithms processes. Give the big O equations for their running times and state which algorithm is fastest for very large n.

4. Algorithm C has running time T_C(n) = O(n), algorithm D has running time T_D(n) = O(log n), and algorithm E has running time T_E(n) = O( sqrt(n)). Which algorithm is the fastest and which is the slowest for very large n? Justify your answer