Thread: Selection Problem - Matrix

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Selection Problem - Matrix

    Let A be a real valued matrix of order n*n already stored in memory. Its (i, j)-th element is denoted by a[i, j]. The elements of the matrix A satisfy the following property:

    Let the largest element in row i occur in column Li. Now, for any two rows i1, i2, if i1<i2, then Li1<=Li2.

    (a)
    2 6 4 5 3
    5 3 7 2 4
    4 2 10 7 8
    6 4 5 9 7
    3 7 6 8 12

    (b)

    Row I l(i)
    1 2
    2 3
    3 3
    4 4
    5 5

    Figure shows an example of (a) matrix A, and (b) the corresponding values of l_i for each row i.

    Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.

  2. #2
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    To get better help, post the code you have so far.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    no i just want the algo in O(nlogn) time please

  4. #4
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    Quote Originally Posted by anirban View Post
    for any two rows i1, i2, if i1<i2
    What does it mean that a row is less than another?

  5. #5
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    means row number i1 < row number i2

  6. #6
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.
    Are you certain that it is O(n*log n)?
    Because i think that would mean you can perform only 4(~3.5) comparisons at most
    for the example problem you have posted.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by anirban
    means row number i1 < row number i2
    Honestly, I do not understand what that means either. What is a row number?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    I think the OP is referring to the index number of the rows of the matrix (a)
    (a)
    1->2 6 4 5 3
    2->5 3 7 2 4
    3->4 2 10 7 8
    4->6 4 5 9 7
    5->3 7 6 8 12
    The second matrix (b) have the indices of these rows in their 1st column
    and the indices of the columns having the largest number in the current row in the 2nd column.
    This problem would be much easier to solve without the O(nlogn) restriction.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  9. #9
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    Quote Originally Posted by stevesmithx View Post
    I think the OP is referring to the index number of the rows of the matrix (a)

    The second matrix (b) have the indices of these rows in their 1st column
    and the indices of the columns having the largest number in the current row in the 2nd column.
    This problem would be much easier to solve without the O(nlogn) restriction.
    The ordo notation gives upper bounds, which means the obvious O(n) solution is also O(n*log(n)). Not sure if I want to point it out though, seems to be an awful lot like "do my homework".

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by anirban View Post
    no i just want the algo in O(nlogn) time please
    You aren't going to get it.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Quote Originally Posted by stevesmithx
    Are you certain that it is O(n*log n)?
    Because i think that would mean you can perform only 4(~3.5) comparisons at most
    for the example problem you have posted.
    This is not true, you are ignoring the hidden constant. In fact, the algorithm could use 1 billion comparisons for a 5x5 matrix and still be O(n log n).

    On a less important note, logarithms in computer science typically refer to the log base 2, while you are calculating the log base 10. This doesn't matter quite as much since logs of different bases are proportional to each other by a constant factor, making them equivalent in Big-Oh notation.
    Quote Originally Posted by OnionKnight
    which means the obvious O(n) solution
    I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution exists. I'm thinking that you are probably misunderstanding the problem, but I'm willing to hear you out.

    @anirban:

    The presence of "log n" in the upper bound for an algorithm usually indicates some kind of divide-and-conquer approach. Consider an algorithm like mergesort: divide the list in half, sort each half, merge the two halves.

    Is there a way you can partition your problem into two smaller chunks, and then recursively perform your algorithm on those chunks? This hopefully starts you off in the right direction. If not, then there isn't much I can say besides just handing you an answer.

  12. #12
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    Quote Originally Posted by arpsmack View Post
    On a less important note, logarithms in computer science typically refer to the log base 2, while you are calculating the log base 10. This doesn't matter quite as much since logs of different bases are proportional to each other by a constant factor, making them equivalent in Big-Oh notation.
    I agree with this. Now the n log n evaluates to 12 for n=5.

    Quote Originally Posted by arpsmack View Post
    This is not true, you are ignoring the hidden constant. In fact, the algorithm could use 1 billion comparisons for a 5x5 matrix and still be O(n log n).
    Hmm, I am confused here.
    Could you explain what hidden constant i am missing here?
    i think you are exaggerating when you say 1 billion!! here
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by stevesmithx View Post
    I agree with this. Now the n log n evaluates to 12 for n=5.


    Hmm, I am confused here.
    Could you explain what hidden constant i am missing here?
    i think you are exaggerating when you say 1 billion!! here
    Big-Oh notation talks about limits and "aymptotic behavior." I.e. the SHAPE of the curve as N increases. It says nothing about the overall SLOPE of the curve.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Quote Originally Posted by stevesmithx View Post
    Hmm, I am confused here.
    Could you explain what hidden constant i am missing here?
    i think you are exaggerating when you say 1 billion!! here
    Actually, I'm not exaggerating at all.

    Lets say the function f(n) returns the number of steps required to complete your algorithm for a given value of n.

    In order for f to be O(n):

    There must be certain value of n (lets call it N) when f(n) <= K*n for all values of n > N. K is any constant at all. It could be 1, or it could be 1 billion.

    ... I'm sorry, I'm just going to stop. I'm butchering this explanation. It would really make a lot more sense if we were chatting in person and I could draw a picture or something

    [edit]
    I just thought of a great example that might help.

    Think of it this way: Big-O notation doesn't describe how fast your algorithm is. It loosely describes how much it grows as you increase the problem size.

    If your algorithm did 1 billion comparisons for a 5x5 matrix, or a 10x10 matrix, or any sized matrix, then it would be O(1). No matter what the problem size is, it always requires 1 billion comparisons.
    [/edit]
    Last edited by arpsmack; 05-06-2009 at 08:54 PM.

  15. #15
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    If your algorithm did 1 billion comparisons for a 5x5 matrix, or a 10x10 matrix, or any sized matrix, then it would be O(1). No matter what the problem size is, it always requires 1 billion comparisons.
    That clears my misunderstanding.
    Thanks to both of you.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Selection Sort Problem?
    By dcwang3 in forum C Programming
    Replies: 31
    Last Post: 11-07-2008, 01:25 PM
  2. Matrix Problem
    By TheJones in forum C Programming
    Replies: 2
    Last Post: 11-01-2006, 11:34 AM
  3. Problem passing matrix to getopt_long two times
    By jibarz in forum C Programming
    Replies: 0
    Last Post: 04-26-2006, 03:51 PM
  4. Matrix and vector operations on computers
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-11-2004, 06:36 AM
  5. Replies: 0
    Last Post: 02-05-2002, 07:44 PM