I am having a hard time solving these questions regarding algorithms for integer multiplication and heap sort

 

CMSC351Homework 4Due: Friday, September 30, 2016Put yournameandsection numberon your solution and (if more than one sheet) staple.Section 3 of the NP-completeness homework will be due Friday, October 7.1. Assume your machine has 64 bit words. Assume you can multiply twon-word numbers in time3n2with a standard algorithm. Assume you can multiply twon-word numbers in time 10nlg 3with a “fancy” algorithm.(a) Approximately, how large doesnhave to be for the fancy algorithm to be better?(b) How many bits is that?(c) How many decimal digits is that?2. Assume that we would like to multiply a two-digit numberabwith a three-digit numbercde.The standard algorithm would do six atomic multiplications. Explain how you can do feweratomic multiplications by forming the product (a+b)(c+d+e). How many atomic multipicationsdo you use?3. Consider an array of size nine with the numbers in the following order 50,30,10,60,80,50,90,70,20.(a) Form the heap using the algorithm described in class. Show the heap as a tree. Show theheap as an array. Exactly how many comparisons did heap creation use?(b) Start with the heap created in Part (a). Show thearrayafter each element sifts downafter heap creation. How many comparisons does each sift use? What is the total numberof comparisonsafter heap creation?4. Assume that we start with a random array of sizen= 2k-1 and form a heap.(a) What is the probability that the third largest element will be a child of the root? Justify.(b) What is the probability that the third smallest element will be a parent of a leaf? Justify.

Attachments:

• 1494569922-hwk4.pdf