Unimodal Search

An array A[1...n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence. More precisely, if there is an index m in {1, 2, ... n} such that
A[i] < A[i+1] for 1 <= i < m and
A[i] > A[i+1] for m <= i < n

In particular, A[m] is the maximum element, and it is the unique "locally maximum" element surrounded by smaller elements.

Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(lg n) time.

Source: Problem 1-3.from MIT OpenCourseWare Course - 6.046J / 18.410J Introduction to Algorithms (SMA 5503)

100 Switches & 100 bulbs

There are 100 switches in a room operating 100 bulbs. At iteration '0' all switches are OFF. For every iteration 'i', all switches that are multiples of 'i' are toggled (turn OFF if ON, turn ON if OFF).

You need to find the state of the 'k'th switch/bulb (1<=100) after the 'i' th iteration

Expected O(1) time and space complexity.

[ALGO] Is Binary Search Tree

Given a binary tree, verify if it is Binary Search Tree

[ALGO] Find the string in 2 dimensional matrix

Given a 2-dim matrix of characters 'm' and a string 's' - find if the string 's' is present in the matrix. Only characters in the neighboring cells of a cell can contribute to the string.

For example, for the case below B,D,F,G are neighbors of X. From 'X' possible strings (or substrings) are XB, XD, XF, XH.
|-----|-----|-----|
|  A  |  B  |  C  |
|-----|-----|-----|
|  H  |  X  |  D  |
|-----|-----|-----|
|  G  |  F  |  E  |
|-----|-----|-----|

Finally, an example. Given the matrix

(0,0)
    |-----|-----|-----|-----|
    |  y  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  a  |  o  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  o  |  o  |
    |-----|-----|-----|-----|
    |  h  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  h  |  o  |
    |-----|-----|-----|-----|
                            (3,3)

and asked to check for the string 'yahoo' the solution is true :
y - (3,0)
a - (3,1)
h - (3,2)
o - (3,3)
o - (2,3)

[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...)

Walk the bridge, in pairs as fast a possible

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.