Safari File Edit View History Bookmarks Develop Window Help 99% Mon 12:00 PM Q E

Question

Safari File Edit View History Bookmarks Develop Window Help 99% Mon 12:00 PM Q E learning utdallas.edu/bbcswebdav/pid-708305-dt-content-rid-6074928 1/courses/2152-merged-ce3345501-cs3345501-se3345501-te3345501/hwkl15s.pdf elearning utdallas.edu bbcswebdav/pid-70830 5-dt-conten rid-6074928 1 /courses 2152-merged-ce33 45501-cs3345 501-se3345501-te3345501/hwikl15 Reade Chapt Eth Wikipedi App Pop kboard Lei du/bb pid-708305-d d-6074928 1. 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 (c) The total number of nodes in any binary tree of height h is less than 2h (d) The height of a complete binary tree containing N nodes is Llog2 NJ (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 LN/2J 2. Prove or disprove formally that the number of digits needed in the binary representation of any positive number N is Llog2 NJ 3. Develop an equation for the total number of bit-reversals that occur during N increments of an initially zero binary number (for example, if N 7, there are 11 bit-reversals) 4. Algorithm A has running time TA(n) 10 104 x n 105 x n2 and algorithm B has running time TB(n) 3 x n3, where n is the number of values the algorithms processes. Give the "big O" equations for the running times and state which algorithm is fastest for very large n 5. Algorithm C has running time To(n) O(n) algorithm D has running time TD(n) O(log n), and algorithm E has running time TE(n) O(V(n). Which algorithm is the fastest and which is the slowest for very large n? 19

Explanation / Answer

1)

Definition: A number p > 0 is prime if and only if the only divisors of p are 1 and p.
Definition: A number x is even if and only if there exists an integer k such that x = 2k.

To prove that 2 is the only even prime number we need to prove two things:
1) 2 is an even prime number
2) If there existed another even prime number, then it must be 2

Proof of 1):

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

Proof of 2):

Assume there existed another even prime number say m =/= 2. Since m is even we see that m = 2k for some integer k. Thus, 2 is a divisor of m. Since m is prime, we know that 1 and m are the divisors of m. Thus, since m =/= 2 we have three distinct divisors of m (which are 1, 2, m). This contradicts the definition of prime unless m = 2. Therefore, 2 is the only even prime number

b)

# nodes = 20 + 21 + ... 2h = 2h+1 ? 1

c)

d)

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

EDIT: According to wikipedia, the root node (rather un-intuitively?) does not count in the height, so the formula would be CEIL(log2(n+1))-1. so log2N

2)

The above method can be stated another way: the number of bits is the exponent of the smallest power of two greater than your number. You can state that mathematically as:

bspec = ?log2(n)? + 1

That formula has three parts:

log2(n) means the logarithm in base 2 of n, which is the exponent to which 2 is raised to get n. For example, log2(123) ? 6.9425145. The presence of a fractional part means n is between powers of two.
?x? is the floor of x, which is the integer part of x. For example, ?6.9425145? = 6. You can think of ?log2(n)? as the exponent of the highest power of two in the binary representation of n.
+ 1 takes the exponent to the next higher power of two. You can think of this step as accounting for the 20th place of your binary number, which then gives you its total number of bits. For our example, that

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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