Write an algorithm that takes as input a binary string b1b2 . . . bn and outputs

Question

Write an algorithm that takes as input a binary string b1b2 . . . bn and outputs its decimal equivalent. Express the run-time in terms of the size of the input string.

4. (a) Write an algorithm that takes as input a binary string bib...bn and outputs its decimal equiva- lent. Express the run-time in terms of the size of the input string b) Given a set S of integers, the range of S is defined as the difference between the largest and the smallest integers in S. Write an algorithm to find the range of S and analyze its run-time (use big-O) in terms of |S for each of the following cases: i. S is a sorted array of integers ii. S is an un-sorted array of integers.

Explanation / Answer

(a) Here, the binary string is b1b2........bn (b1 being the most-significant bit).

Take dec=b1, where dec is used to store the decimal equivalent of the given binary string.

We will run a loop from i=2 to n and for each i perform, dec=dec*2+bi.

At the end of the loop, dec will be equal to the decimal equivalent of the given binary string.

For eg: Consider 1011 is the given binary string. Then initialise dec with 1.

Then for i=2, dec=1*2+0=1. So, dec=2.

For i=3, dec=2*2+1=5. So, dec=5.

For i=4, dec=5*2+1=11. So, dec=11.

So, the answer is 11 which is correct.

(b) (i) In a sorted array, the first element is the smallest and last element is the largest. So, the range is simply last element - first element.

The time complexity for this algorithm is constant, i.e, O(1).

(ii) In an unsorted array, we have to find the smallest and largest elements by traversing through the array. For this take 2 variables min and max for storing minimum and maximum elements.

Initialise both with first element of array.

For each element e of array, if min>e, then assign e to min and if max<e, then assign e to max.

Finally min and max have minimum and maximum elements of array.

Now max-min is the range of the array.

The time complexity of this is O(n) where n is the number of elements in array as we have to traverse the complete array for maximum and minimum elements.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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