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)