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.

8 comments:

  1. Ans 1 - I can think of a O(n^2) Soln. Construct an adjacency matrix and use Warshall's algo(not floyd Warshall) to convert it into path matrix - and if there occurs a situation, where you have to exchange a positive variable(+1 is =) with a -ve one(-1 mean !=), or vice versa, then it is not possible.

    Other method could be by maintaining sets and combining them in equal to condition and after all equals verify the not equal tos, but i think that'll take more time.

    ReplyDelete
  2. Hi,

    Could you give me the solution for problem number 1? I've been trying for the last few days and I don't seem to get forward.

    ReplyDelete
  3. Answers Please???????

    ReplyDelete
  4. i have worked on these algorithms where can i

    check my answer ???

    ReplyDelete
  5. please
    the solution
    thanks a lot

    ReplyDelete
  6. for problem 1
    two adjacent elements in the array are same
    1,2,2,3,3,4,5,6,7,8,9,10
    =>1=2;2=3; and so on
    now create a new array :
    1,1,1,1,5,5,7,7,9,9; (union/find algo)
    then say other array is
    1,3,5,6
    =>1!=3 AND 5!=6
    just check for the indexes in the previous array, if they are same=> not possible.

    ReplyDelete
  7. Really interesting algorithm. i like it. Thank you.

    Upcoming Bank Exams

    ReplyDelete
  8. 1) A chess board is represented with the help of 2D Array (such as [0][0]......[63][63]). The game is going on and one opponent is left with only and only KING (it is not CHECKMATE yet). Write a program which takes current position of KING from the user and tells the all possible moves of the KING according to the position given by the user.

    Can anyone answer this algorithm...please help me with this question...Monica..:)

    ReplyDelete