Algorithm

Let T[1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <= i <= n and T[i] = i, provided such an index exists. Your algorithm should take a time in Big "O" (log n) in worst case.

Solving Recurrence Relations/Difference Equations

See attached file for full problem description.

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Proof : Tree Contains a Cycle

Prove that a graph with n nodes and more than n-1 edges must contain at least one cycle.

Dynamic Programming : Write an Algorithm to Minimize Cost

There are n trading posts along a river. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is next to impossible to paddle against the current.) For each possible departure point i and each possible arrival point j the cost of a rental from i to j is known. However, it can happen that the cost of renting for i to j is higher that the total cost of a series of shorter rentals. In this case you can return the first canoe at some post k between i and j and continue your journey in a second canoe. There is no extra charge for changing canoes in this way. Give an efficient algorithm to determine the minimum cost of a trip by canoe for each possibl... click for more