1. Prove or disprove formally: (a) The largest even prime number is 2. For the f

Question

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 [log2 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 [log2 N].

3. Algorithm A has running time TA(n) = 10^6 + 10^4 × n + 10^5 × n^2 and algorithm B has running time TB(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 TC(n) = O(n), algorithm D has running time TD(n) = O(log n), and algorithm E has running time TE(n) = O( sqrt(n)). Which algorithm is the fastest and which is the slowest for very large n? Justify your answer

Explanation / Answer

Answer:

1)

a)

We have two definitions to rpove the given statement:

Definition 1:

If a number is x > 0 and if if and only if the divisors of x is x and 1.then x is a prime number  
Definition 2:

If a number is divided by 2 then only we can call the number an even number

and we need to prove the above definitions in order to prove that

The largest even prime number is 2.

Proof 1:

2 is even number because 2 = 2 * 1
and 2 is prime since it has divisors 1 and 2

b)

As per the definition, A full binary tree is a tree in which each vertex has exactly two children except the vertices present in the last level of the tree or leaves.

From the image given below

Base case:

l(T) = 1, and n(T) = 1 = 2^h = 2^0, where l(T) is number of leaf nodes

Inductive step:

at h = 1, n = 3

and l(T) = 2 = 2^h = 2^1

at h = 2,

n(T) = 7,

l(T) = 4 = 2^2 = 2^h

so we can say that inductive cases are also true.

c)

so we can say that the total number of nodes are <= 2^(h+1) - 1

or total number of nodes are less than 2^(h+1).

d)

It's CEIL(log2(n+1))-1

Please provide your valuable feedback.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.