Interesting Algorithms

1. Let A be a list of n elements in non-decreasing order where some elements are replicated.
The problem is to find the element that appear most frequently. Give an O(k log n) time
algorithm to solve the problem where k denotes the number of distinct elements in A.


2. You are given a list A = [a1; a2; - - - ; an] of n distinct numbers in an arbitrary order.
You are supposed to find two numbers _i and _j from A such that (i) i < j, (ii) _j > _i, and
(iii) satisfying (i) and (ii), aj - ai is minimum over all possible such pairs. Give an O(n) time
algorithm.


3. A carpenter has a piece of wood of a certain length that must be cut at positions a₁, a₂ ..., a_n where a_i is the distance from the left end of the original piece of wood. Notice that after making the first cut, the carpenter now has two pieces of wood; after making the second cut, the carpenter has three pieces of wood, etc. Assume that the cost of making a cut in a piece of wood of length l is equal to l, and is the same no matter which position in that piece of wood is being cut. Let L be the length of the original piece of wood.
Derive the recurrence relation which could be used to design a recursive algorithm to find the minimum total cost for making all the cuts.


4. Describe a Θ(n lg n)-time algorithm, that given a set of n integers and another
integer x, determines whether or not there exist two elements in S whose sum is exactly x. Write
pseudocode.
Hint: Sort using mergesort and iterate once after sorting. Θ(n lg n+n) = Θ(n lg n)


5. Suppose you are given an array A containing n sorted elements followed by lgn unsorted elements. Thus, entire array contains N = n+lgn elements. Can the entire array sorted in O(n) time.

6.  You are given an array of n numbers. Write an algorithm with O(n)=nlogn  that returns the number of distinct numbers in the array.