Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / 1) Draw a tree diagram for Karatsuba’s Algorithm applied to (98)(76) and use it to count the number of single-digit multiplications
1) Draw a tree diagram for Karatsuba’s Algorithm applied to (98)(76) and use it to count the number of single-digit multiplications.
Solution:
2. Draw a tree diagram for Karatsuba’s Algorithm applied to (345)(12231) and use it to count the number of single-digit multiplications. This is a little trickier than the previous example because of the different integer lengths. Trust the pseudocode!
Solution:
3. We observed that if n is even and A = A1 A0 and B = B1 B0 are two n-digit numbers that the special product (A1 + A0)(B1 + B0) might not be a product of two n/2-digit numbers, thereby making the recurrence relation T(n) = 3T(n/2) + q(n) feel a little iffy. We glossed over this but let’s patch it a bit.
(a) Show that in the n = 2 case that even if both a1 + a0 and b1 + b2 are not single-digit numbers that the product (a1 + a0)(b1 + b0) can be calculated using one single-digit multiplication and q(n) additions and decimal shifts.
Solution:
(b) Generalize this argument in the following sense: Show that even if both A1 + A0 and B0 + B0 are not n/2-digit numbers that the product (A1 + A0)(B1 + B0) can be calculated using one n/2-digit multiplication and O(n) additions and decimal shifts, thereby rendering the recurrence relation accurate.
Solution:
4. Let A = a2a1a0 and B = b2b1b0 be the base-10 digit representations of two 3-digit numbers.
Formally then A = 100a2 + 10a1 + a0 and B = 100b2 + 10b1 + b0.
(a) Evaluate the product AB and collect the result into the form:
AB = 10000(T1) + 1000(T2) + 100(T3) + 10(T4) + (T5)
We'll say that the T1,...,T5 are the terms. How many different products arise in all of the terms together?
Solution:
(b) Rewrite the terms T2 and T4 in such a way as to reduce the number of total multiplications which are necessary to evaluate the product down to 7.
Solution:
(c) Explain (not even pseucode) how this might lead to a recursive algorithm for multiplication much like the Karatsuba Algorithm.
Solution:
(d) Write down the recurrence relation for this algorithm and solve it using the Master The-orem. Is it faster or slower than Karatsuba?
Solution:
5. Assume k is unknown. If we used a max heap instead of a min heap to find the kth order statistic and assuming we could build the max heap in O(n) time, what would the O time complexity of extracting the kth smallest element be?
6. Assume k is known and fixed. Modify the BubbleSort pseudocode so that after 7 iterations the first i elements are correctly positioned and so that it stops when exactly the first k elements are correctly positioned.
Solution:
