Results 1 to 4 of 4

Math Help - Computer science algorithm problem

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    96

    Computer science algorithm problem

    If given two arrays, Q and W which are sorted in non-decreasing order along with an integer c, how could I develop an algorithm that finds the cth smallest element in the concatenation of Q and W? The algorithm should only look at O(log c) positions of the arrays Q and W.

    I've only been able to come up with ways that this would work looking at C-1 positions but not log C.

    P.S. log base 2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2012
    From
    United States
    Posts
    97
    Thanks
    21

    Re: Computer science algorithm problem

    I don't see why you cannot just use mergesort...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Computer science algorithm problem

    I found the following online.

    The required kth smallest element lies within A[1]...A[k] or B[1]...B[k]. Consider the following algorithm foo():

    Input:

    a sorted array A
    an index I_A in A
    a sorted array B
    an index I_B in B
    an integer k

    Output: The kth smallest element in the union of A[I_A]...A[I_A + k - 1] and B[I_B]...B[I_B + k - 1].
    Clearly the solution to our problem is foo(A, 1, B, 1, k).

    The following is an implementation of foo():

    Code:
    int foo(int A[], int I_A, int B[], int I_B, int k)
    {
      if(k == 2) return the second smallest among A[I_A], A[I_A + 1], B[I_B] and B[I_B + 1];
    
      int M_A = A[I_A + floor(k/2)];
      int M_B = B[I_B + floor(k/2)];
    
      if (M_A < M_B)
        return foo(A, I_A + floor(k/2), B, I_B, ceil(k/2));
      else
        return foo(A, I_A, B, I_B + floor(k/2), ceil(k/2));
    
    }
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2012
    From
    Ireland
    Posts
    600
    Thanks
    165

    Re: Computer science algorithm problem

    Quote Originally Posted by ShadowKnight8702 View Post
    I don't see why you cannot just use mergesort...
    It's probably a learning exercise. Maybe to teach independant thinking for making efficient algorithms
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. computer science
    Posted in the New Users Forum
    Replies: 1
    Last Post: October 25th 2012, 04:55 AM
  2. computer science problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 05:16 PM
  3. Computer Science
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: August 7th 2009, 05:06 PM
  4. Probability-Computer Science problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: February 8th 2009, 06:35 AM
  5. Computer science: Functions help
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 27th 2009, 12:59 AM

Search Tags


/mathhelpforum @mathhelpforum