Popular Posts

  • Robot in an NXN grid
    Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ...
  • CLRS Exercises 2.3-4 Recursive insertion sort
    Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
  • Kth Largest from an infinite stream
    Problem:   Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
  • Print BST keys in the given range
    Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i....
  • Simultaneous minimum and maximum
    How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
  • CLRS Exercises 2.3-7
    Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
  • Delete alternate nodes of a Linked List
    Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
  • Print Ancestors of a given node in Binary Tree
    Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
  • CLRS - Problem 2.1
    Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
  • CLRS Exercises 5.1-2
    Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...

Tuesday, August 9, 2011

CLRS Exercises 5.1-2

Problem:

Describe an implementation of the procedure RANDOM(a, b) that only makes calls to
RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and
b?

Solution:

  1. n = ceil(log(b-a+1))
  2. decimal_number=0;
  3. do
  4. for i = 1 to n: get all binary
  5. decimal_number = generate decimal from binary digits
  6. while decimal_number > b-a+1
  7. return decimal_number

Complexity:  Θ(log (b-a+1))

Posted by anantha at 8/09/2011 12:05:00 AM
Labels: ,

3 comments:

  1. Jayanth KoushikFebruary 29, 2012 at 6:30 PM

    What is the need for while loop?

    Take n as floor(b-a+1).
    Let r be the generated number.

    Then,

    0 <= r <= 2^(floor(b-a+1)) - 1
    <= 2^(b-a+1) - 1
    = b - a + 1 - 1
    = b - a
    So,
    a <= r + a <= a + b - a
    <= b

    So, r + a is random number that satisfies the required conditions.

    And complexity is of course Θ(log (b-a+1)).

    ReplyDelete
  2. Jayanth KoushikFebruary 29, 2012 at 9:45 PM

    Nope...sorry....made a mistake...

    ReplyDelete
  3. UnknownOctober 5, 2013 at 8:33 PM

    can you explain the time complexity

    ReplyDelete

Subscribe to: Post Comments (Atom)