Some Interesting Algorithm Questions

1. Here's a problem that occurs in automatic program analysis. For a set of variables x1; ...... ; xn, you are given some equality constraints, of the form "xi = xj" and some dis equality constraints, of the form "xi != xj" Is it possible to satisfy all of them? Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.



2. What are the running times of each of these algorithms, and which would you choose?
   
   
   • Algorithm A solves problems by dividing them into 5 subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
   • Algorithm B solves problems of size n by recursively solving two subproblems of size n-1 and then combining the solutions in constant time.
   • Algorithm C solves problems of size n by dividing them into nine subproblems of size n=3, recursively solving each subproblem, and then combining the solutions in O(n2) time.



3. You are given two sorted lists of size m and n. Give an O(log m+log n) time algorithm for computing the kth smallest element in the union of the two lists.



4. An array A[1....n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element.
   The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is A[i] > A[j]?".
   However you can answer questions of the form: "is A[i] = A[j]?" in constant time.