Selection Problem - Matrix

This is a discussion on Selection Problem - Matrix within the Tech Board forums, part of the Community Boards category; Originally Posted by arpsmack I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution ...

  1. #16
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    Quote Originally Posted by arpsmack View Post
    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.
    There is only one row you'd need to search through as all other rows are guaranteed to have it's maximum value less than it. In the case of equality, it wouldn't matter which of the possible rows you'd pick so you can just search through that row.

  2. #17
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    Quote Originally Posted by OnionKnight View Post
    There is only one row you'd need to search through as all other rows are guaranteed to have it's maximum value less than it. In the case of equality, it wouldn't matter which of the possible rows you'd pick so you can just search through that row.
    Ah ok, that's what I figured you were thinking.

    What the problem states is that the *column index* of the maximum element in a row will be less if the row index is less, it doesn't say that the value of the maximum element will be less. The maximum value for the entire matrix could be in any row.

    Here's a valid matrix that has its maximum value in the first row (the max value in each row is underlined):
    Code:
    .   0 1 2 3 4
    .   ---------
    0 | 9 7 4 3 2
    1 | 8 1 1 2 7
    2 | 3 5 2 2 1
    3 | 3 3 4 2 6
    4 | 1 2 5 4 8
    
    Row   | Column Index of Max Value
    0     | 0
    1     | 0
    2     | 1
    3     | 4
    4     | 4

  3. #18
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    Quote Originally Posted by arpsmack View Post
    Ah ok, that's what I figured you were thinking.

    What the problem states is that the *column index* of the maximum element in a row will be less if the row index is less, it doesn't say that the value of the maximum element will be less. The maximum value for the entire matrix could be in any row.

    Here's a valid matrix that has its maximum value in the first row (the max value in each row is underlined):
    Code:
    .   0 1 2 3 4
    .   ---------
    0 | 9 7 4 3 2
    1 | 8 1 1 2 7
    2 | 3 5 2 2 1
    3 | 3 3 4 2 6
    4 | 1 2 5 4 8
    
    Row   | Column Index of Max Value
    0     | 0
    1     | 0
    2     | 1
    3     | 4
    4     | 4
    I can't believe I oerlooked that. But thinking about it, I think there's still an O(n) solution. You only have to check 2n - 1 elements. Basically taxicab geometry where you start in the top left and go to the bottom right of the matrix.

  4. #19
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by OnionKnight View Post
    I think there's still an O(n) solution. You only have to check 2n - 1 elements. Basically taxicab geometry where you start in the top left and go to the bottom right of the matrix.
    How do you decide to switch rows? If I'm not mistaken, you want to advance to the next row when you encounter the largest element in the current row. With your approach, you'll have to check all elements to the right of the current one to determine the largest. Now consider the following matrix:

    Code:
    2 1 1 1 1
    2 1 1 1 1
    2 1 1 1 1
    2 1 1 1 1
    2 1 1 1 1
    In this case, your algorithm runs in time O(n^2).

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  5. #20
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    Quote Originally Posted by Snafuist View Post
    How do you decide to switch rows? If I'm not mistaken, you want to advance to the next row when you encounter the largest element in the current row. With your approach, you'll have to check all elements to the right of the current one to determine the largest. Now consider the following matrix:

    Code:
    2 1 1 1 1
    2 1 1 1 1
    2 1 1 1 1
    2 1 1 1 1
    2 1 1 1 1
    In this case, your algorithm runs in time O(n^2).

    Greets,
    Philip
    Gah, I didn't think that one all the way through. Yes it wouldn't be possible to know when you've hit the maximum element for a row so I'll rest my O(n) case.

Page 2 of 2 FirstFirst 12
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, 12:25 PM
  2. Matrix Problem
    By TheJones in forum C Programming
    Replies: 2
    Last Post: 11-01-2006, 10: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, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21