Question

A Mystery Algorithm

Input: An integer n ≥ 1

Output: ??

Find P such that 2^p is the largest power of two less than or equal to n.

Create a 1-dimensional table with P +1 columns. The leftmost entry is the Pth column

and the rightmost entry is the 0th column.

Repeat until P < 0

If 2^p≤n then

put 1 into column P

set n := n - 2^p

Else

put 0 into column P

End if

Subtract 1 from P

Return the filled-in table

(a) Show a trace of the Mystery algorithm on n = 9

(b) In general, what is the output of the Mystery algorithm? Be clear and concise in your answer.

(c) What is the run time of the Mystery Algorithm? Your answer should be a function of

n. You may assume that “Find P such that 2^p is the largest power of two less than or

equal to n” takes θ(1) time to compute. Show all of your work clearly with complete

sentences; do not leave out any details.

Answer 1

Repeat until P < 0 ==> this statement have a mistake.I think (p>0),so i am assuming p>0

(a) Show a trace of the Mystery algorithm on n = 9

  

Find P such that 2^p is the largest power of two less than or equal to n.:

p=3 because 2^3=8 which is <=9

Create a 1-dimensional table with P +1 columns. The leftmost entry is the Pth column

and the rightmost entry is the 0th column.

pth column 0th column

(i)3> 0

(ii) 2^3≤9 then

put 1 into column P

1

pth column (3th) 0th column

set n := 9 - 2^3=>1

(iii)Subtract 1 from P => P=2

(i)2>0

(ii)2^2<=1 (false) so else condition

Else

put 0 into column P

1

0

pth column (2th)     0th column

End if

Subtract 1 from P ==>p=1

(i)1>0

(ii)2^1<=1 (false) so else condition

Else

put 0 into column P

1

0

0

pth column (1th) 0th column

End if

Subtract 1 from P ==>p=0

(i)0>0 (condition false)

loop exits and return table as below:

1

0

0

(b) In general, what is the output of the Mystery algorithm?

The myster algorithm finding the largest power of 2 value which is less than or equal to n

if n=9 we get binary representation as (1 0 0 0) ==> value is 8, which highest power of 2 <=n(9)

if n=8 we get binary representation as (1 0 0 0) ==> value is 8, which highest power of 2 <=n(8)

(c)

Given a number n, find the highest power of 2 that is smaller than or equal to n.

Examples :

Input : n = 10
Output : 8

Input : n = 19
Output : 16

Input : n = 32
Output : 32

A simple solution is to start checking from n and keep decrementing until we find a power of 2.

# Python3 program to find highest # power of 2 smaller than or # equal to n. def highestPowerof2(n):     res = 0;     for i in range(n, 0, -1):                   # If i is a power of 2         if ((i & (i - 1)) == 0):                       res = i;             break;               return res; # Driver code n = 10; print(highestPowerof2(n));       # This code is contributed by mits

Output :

8

Time complexity : O(n). In worst case, the loop runs floor(n/2) times. The worst case happens when n is of the form 2^x – 1.