Use python to solve this problem and please give a detailed solution. Imagine th
ID: 3793318 • Letter: U
Question
Use python to solve this problem and please give a detailed solution. Imagine there is an algorithm that multiplies two n-bit binary integers x and y in time n^a, where a = log 2^3. Call this procedure lastmultiply(x;y). (i) We want to convert the decimal integer 10^n (a 1 followed by n zeros) into binary. Here is the Algorithm (assume n is a power of 2) Function pwr2bin (n) if n = 1: return 1010 base 2 Else z = ??? Return lastmultiply(z; z) Fill in the missing code Next, give a recurrence relation for the running time of the algorithm, and solve the recurrence (ii) Then, convert any decimal integer x with n digits (where n is a power of 2) into binary Consider the following algorithm Function d2bin(x) if n 1: return binary[x] else: split x into two decimal numbers xL, xR with n/2 digits each return??? Here binary[.] is a vector that contains the binary representation of all one-digit integers. That is, binary[0] = 0_2, binary[1] = 1_2, up to binary[9] = 1001_2. Assume that a lookup in Binary takes O(1) time Fill in the missing info. Give a recurrence for the running time of the algorithm, and solve it.Explanation / Answer
Solution for question 1:
function power2bin(x)
1 if n = 1 : return 1010base2
2 else:
3 z = power2bin(n/2)
4 return lastmultiply(z,z)
//The lastmultiply function will convert the two bnary integers into a binary integer by multiplying them
The recurrence relation can be written as T(n) = T(n/2) + O(n^a)
as lastmultiply operation will take O(n^a) time.
Solution for the question 2:
function dec2bin(x)
1 if n =1 : return binary[x]
2 else:
3 split x into two decimal numbers xL, xR with n/2 digits each
4 return lastmultiply(dec2bin(xL),pwr2bin(n/2)) + dec2bin(xR)
//The lastmultiply function will convert the two bnary integers into a binary integer by multiplying them
The recurrence relation can be written as T(n) = T(n/2) + O(n^a)
as both lastmultiply and power2bin() takes O(n^a) time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.