Resilient Binary Search-search an element in O(log n) time in the perturbed array?

You are about to search for an element in a sorted array A[1..n] using binary search when the array suddenly gets perturbed. By perturbed, we mean a number in ith position in the array can now be either in i, i-1 or i+1th position; but all the numbers are still in A[1..n]. Can you still search an element in O(log n) time in the perturbed array?

Valid Strings-erase the smallest possible number of characters such that the remaining string after the erasures is valid

A string over the characters (, [, ] and ) is said to be valid if one can reduce the string to the null string by repeatedly erasing two consecutive characters of the form () or []. For example, the string [([])[]] is valid but neither ([)] nor ([ is valid.
Give a polynomial time algorithm to solve the following problem: Given a string, erase the smallest possible number of characters such that the remaining string after the erasures is valid. For example, given the string [(], we can erase ( to get [].

Nab the thief-prove that Alice can win in at most 3n moves.

Alice and Bob play the following game: Two cops(c) and a thief(t) are positioned at some vertices of an nxn grid. Alice controls the two cops and Bob controls the thief. The players take turns to play, starting with Alice. In one turn, Alice can move each cop to a neighboring vertex, i.e. left, right, up or down or keep the cop in the same place. In his turn, Bob can move the thief similarly.
If the thief and a cop end up in the same vertex, Alice wins.
For any arbitrary positioning of the two cops and the thief, prove that Alice can win in at most 3n moves.

Estimating Distance-Find maximum distance between any pair of points in a plane

A set of n points are on a plane. Let d denote the maximum distance between any pair of points. Design a linear time algorithm to guess the value of d. Your guess is good if it lies between 0.7d and d. also proove correctness of algorithm.

Beaded Necklace-Find a sequence of such operations with minimum total cost for a given initial distribution of beads.

You are given a circular necklace containing n beads. Each bead maybe black or white. You have to rearrange the beads so that beads of the same color occur consecutively.

The only operation allowed is to cut the necklace at any point, remove some number of beads from both ends and put them back in any order, and join the cut ends. The cost of this operation is the number of beads removed. Any number of such operations can be used. You have to find a sequence of such operations with minimum total cost for a given initial distribution of beads.

For example, if the initial string is wbwbwb, this can be done by a single operation of cost 4, or two operations of cost 2 as shown.

Describe a polynomial-time algorithm for this problem; with short proof of correctness. You get points only if you match (or better) the judge solution's time complexity.