[ALGO] Random number generator, with equal probability

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)


Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here  http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/

Things To Do...

I recently attended a Spring training by SpringSource. While learning the framework and admiring its features, it prick me that there is a LOT that I don't know and have to gather.

So, after a long time I'm starting this post, that I anticipate to update regularly with things I want to do, things I want to learn and things I want to talk about.

Expect one blog title for each entry in this list. So, here I go :

1. P1: Spring - an E2E tutorial - put to use all the learning from the training into a live example.
2. P2: OSGi - post an article listing resources I read to understand OSGi. Maybe with a few self comments
3. P?: Groovy - I really loved the way Groovy scripts helped code Java applications quickly. I'm going to try them out
   
4. P?: Grails - Another quick build of a web application. I'm going to try this out too.
5. P?: Castor - Data binding framework : http://www.castor.org/
6. P?: JBoss Seam
7. P?: Spring Roo : http://en.wikipedia.org/wiki/Spring_Roo
8. P2: Why should one refrain from using Stubs and prefer using XPath for Web service implementation (server side)
9. P2: Code-first VS contract-first approach for webservices
10. P?: The JSF standard
11. P2: Distributed transactions - an interesting concepts / field. How about starting here : Distributed transactions in Spring, with and without XA
12. P2: Java Persistence API : https://glassfish.dev.java.net/downloads/persistence/JavaPersistence.html
13. P?: JDO : http://java.sun.com/jdo/
14. P2: JSR-250 Common Annotation
15. P1: Introduction to Algorithms @ MIT Open Courseware - http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm
16. P?: A course / reading on OOAD, Systems Analysis, Design
17. P?: Machine Learning Modeling Algo : Linear CRF - What? How?
    

.... (To be continued...)