Algorithm analysis help

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 7449 Views - Last Post: 16 April 2007 - 02:48 PM

#1 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Algorithm analysis help

Posted 27 January 2007 - 10:06 PM

I'm fairly certain that the problem I'm working on is a misprint. I'll give the exact text and then I'll pose my solution. After than, maybe someone will agree that the problem is wrong, or give me a clue as to what I'm doing wrong. Here goes:

Problem(verbatim):
Suppose that each row of an n x n array A consists of 1s and 0s such that in any row of A, all the 1s come before any 0s in that row. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for finding the row of A that contains the most 1's.

Yes, you read correctly. The problem in the book wants it in O(n) time! The absolute best I could get is O(n log n). My solution involved having an outer for loop that runs from 0 to n -1. The inner loop does a binary search on each row. So, the outer loop runs n times and the inner loop runs, at most, around log n times, which gives n*log n is O(n log n). Am I missing something? I mean, the only way for the algorithm to run at O(n) would be for there to only be constant time operations within the outer loop right? My instincts tell me it's a misprint, but I'd like some confirmation on that. Anyone?

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Algorithm analysis help

#2 m2s87  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 21
  • View blog
  • Posts: 390
  • Joined: 28-November 06

Re: Algorithm analysis help

Posted 27 January 2007 - 10:33 PM

Quote

Problem(verbatim):
Suppose that each row of an n x n array A consists of 1s and 0s such that in any row of A, all the 1s come before any 0s in that row. Assuming A is already in memory, describe a method running in O(n) time (not O(n2) time) for finding the row of A that contains the most 1's.

Example 100 elements in a row, within there is (36)*1 and (64)*0

I thought 2 cool way of solving it difrently.

First one
  • add the vector up as value. It would be 36.
  • add vector up as string. (something like 010001100010101...)
  • get Ax - start a loop can you find a "new string("1", i )", where i decreases each time
  • if a<ax then a value would be ax
  • when starting a new round you can limit the bypass checks with - if A > vector as value

Second one
  • add the vector up as string
  • eliminate repeating 0's (so 10000110001 would become 101101
  • split it by 0's
  • get the max length of array elements
  • A = total max lenght

Hope it helped :D
Was This Post Helpful? 0
  • +
  • -

#3 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 28 January 2007 - 07:50 AM

Thank you. I appreciate your response, but I don't think you understood the problem. All 1's come before any 0's, so you can't have a mixed string like, 100011010, you can only have strings like 11111110000. So, let's look at this a little closer.

Example:

array A is 5 x 5 and contains
1 1 1 0 0
1 0 0 0 0
1 1 1 1 0
1 1 0 0 0
1 1 1 1 1

This is basically an array with 5 elements, each of which is another array of 5 elements: A[5][5].

The problem states that each row has 1's AND 0's, so there are no 0 rows. However, it leaves the door open for 1 only rows. I have code that tests for both edge cases and avoids the loop, but the running time analysis, must take into account the worst case, so I'm going to leave that out.

Pseudocode:
Algorithm OneCount(A)
Input: An n x n array A
Output: N integer representing the array index with the greatest number of 1's
longest <-- 0
for i <-- 0 to n - 1
  // test for edge cases
  current <-- 0
  L <-- 0 // left side of binary search
  R <-- n-1 // right side
  while (R - L) >= 2
	 midpoint = (L+R)/2
	 if (A[midpoint] = 1) do
		L = midpoint
	 else
		R = Midpoint
	 if (current <-- L) > longest do
		longest <-- current
  return longest



So, in this case the algorithm would return an integer, 4, because array in row a[4] has five 1's. I just realized that I missed the case where two rows both contain the largest number of 1's, but let's leave that alone for now to focus on the main problem. Can anyone think of a faster algorithm to do this? Thanks.
Was This Post Helpful? 0
  • +
  • -

#4 m2s87  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 21
  • View blog
  • Posts: 390
  • Joined: 28-November 06

Re: Algorithm analysis help

Posted 28 January 2007 - 12:09 PM

So you use splitter, its about A.upperboundofarray(wherearestoredvalues)/2^n fast.
If you want to get a faster result, then you can :
  • check multiple arrays at the same time.
  • get the max out tactics (do this for the first time, and then for the new vector, just start checking if (A[longest] = 1) do...)
  • you can use massive max out tactics (do this for the first time,
    then find all vectors where A[longest] = 1 but the results on the integer (index) vector, if vector upperbound is 0(only 1) then you have your max element[or if all have it null or nothing{means you have multible maximums}] [this should be a lot faster])
  • if you do not mind error handling, you can use threading (you might can get even better results)

Hope it helped :D
Was This Post Helpful? 0
  • +
  • -

#5 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 28 January 2007 - 12:33 PM

View Postm2s87, on 28 Jan, 2007 - 01:09 PM, said:

So you use splitter, its about A.upperboundofarray(wherearestoredvalues)/2^n fast.
If you want to get a faster result, then you can :
  • check multiple arrays at the same time.
  • get the max out tactics (do this for the first time, and then for the new vector, just start checking if (A[longest] = 1) do...)
  • you can use massive max out tactics (do this for the first time,
    then find all vectors where A[longest] = 1 but the results on the integer (index) vector, if vector upperbound is 0(only 1) then you have your max element[or if all have it null or nothing{means you have multible maximums}] [this should be a lot faster])
  • if you do not mind error handling, you can use threading (you might can get even better results)
Hope it helped :D


I'm sorry, but I don't know what "splitter" is. The multi-threaded idea is OK, but it's not the point of the exercise. I don't know what you mean by "massive max out tactics", but I will Google it. So are you saying that your algorithm will take a 2-dimensional (n x n) array a described above and return the index of the 1D array with the most 1s in O(n) time?
Was This Post Helpful? 0
  • +
  • -

#6 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 30 January 2007 - 07:43 AM

From all I'm hearing O(n) is not possible. I asked a friend of mine who has a masters in math (not sure what specialty) and another whop has a degree in advanced combinatorics and they both agreed it was not possible with the given parameters.
Was This Post Helpful? 0
  • +
  • -

#7 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Algorithm analysis help

Posted 30 January 2007 - 08:17 AM

edit: bah, my bad, misread it...
my best bet is O(nlogn), too, although I would look for 1s in the columns with a linear search, but choosing the columns in a "binarysearch way" (starting from the middle one, and choosing the next one from the center of the matching interval...)

This post has been edited by 1lacca: 30 January 2007 - 08:36 AM

Was This Post Helpful? 0
  • +
  • -

#8 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 08 February 2007 - 03:37 PM

Turns out I was right. I feel vindicated. Now to send an e-mail to the book publisher to include this question in their errata.
Was This Post Helpful? 0
  • +
  • -

#9 alwaysthereforyou  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 19-February 07

Re: Algorithm analysis help

Posted 19 February 2007 - 09:57 PM

View Postalcdotcom, on 8 Feb, 2007 - 03:37 PM, said:

Turns out I was right. I feel vindicated. Now to send an e-mail to the book publisher to include this question in their errata.



Sorry for being so late in replying, but i think the question can be done in O(n).
Use divide and conquer,

Consider it as two n * (n/2) martices LEFT and RIGHT (i.e. divide into two halves).
If LEFT has NO 1's in column n/2, then run the same algorithm for LEFT, else run it for RIGHT.
If running for RIGHT, store which rows had 1's in the n/2 th column and we essentially need to worry only about these rows of RIGHT.
Ditto if running for LEFT.

Hope you got the idea.

Complexity T(n) = T(n/2) + O(n)
So,T(n) = O(n)
Was This Post Helpful? 0
  • +
  • -

#10 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 22 February 2007 - 11:19 AM

View Postalwaysthereforyou, on 19 Feb, 2007 - 10:57 PM, said:

View Postalcdotcom, on 8 Feb, 2007 - 03:37 PM, said:

Turns out I was right. I feel vindicated. Now to send an e-mail to the book publisher to include this question in their errata.



Sorry for being so late in replying, but i think the question can be done in O(n).
Use divide and conquer,

Consider it as two n * (n/2) martices LEFT and RIGHT (i.e. divide into two halves).
If LEFT has NO 1's in column n/2, then run the same algorithm for LEFT, else run it for RIGHT.
If running for RIGHT, store which rows had 1's in the n/2 th column and we essentially need to worry only about these rows of RIGHT.
Ditto if running for LEFT.

Hope you got the idea.

Complexity T(n) = T(n/2) + O(n)
So,T(n) = O(n)

I've read what you wrote several times and I still don't quite get it. Would you mind posting some pseudo code so I can get a clearer idea of what you mean? The assignment has already been turned in (I got 100%), so I'm not trying to cheat or anything. :) Thanks.
Was This Post Helpful? 0
  • +
  • -

#11 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Algorithm analysis help

Posted 25 February 2007 - 06:39 AM

View Postalwaysthereforyou, on 19 Feb, 2007 - 09:57 PM, said:

Consider it as two n * (n/2) martices LEFT and RIGHT (i.e. divide into two halves).
If LEFT has NO 1's in column n/2, then run the same algorithm for LEFT, else run it for RIGHT.
If running for RIGHT, store which rows had 1's in the n/2 th column and we essentially need to worry only about these rows of RIGHT.
Ditto if running for LEFT.

Hope you got the idea.

Complexity T(n) = T(n/2) + O(n)
So,T(n) = O(n)


The basic idea is to use a binary search on the columns (not rows) of the array. If we find a 1 in a collumn then we need to move to the right and look at the next half way point if we found no 1 then move to left. The condition we are looking for is a [1][0] that is a row where we found a 1 to the left and a 0 to the right.

The method I thought up was simmilar... search collumn 1/n for a 1, at the first location do a row-wize binary search for the column with the last 1 (note you only need to seach from n/2 to n), then search that column for a 1 (remebering to exclude the row we already know about), If you find a 1, do a binary search of that row (from the current column to the end) for the last column containing a 1 (again remebering to leave out the current row) etc until I find the column with only one 1 in it (that one being the one I already know about).

I don't know the complexity, but I know it is less than O(n log n). Worst case I would do log n row seaches log n times.

This post has been edited by NickDMax: 25 February 2007 - 06:52 AM

Was This Post Helpful? 0
  • +
  • -

#12 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 26 February 2007 - 09:09 AM

Why would we do a binary search on unsorted data? Consider this example:

1 1 1 1 1 0
1 1 1 0 0 0
1 0 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 0
1 1 0 0 0 0

Doing a binary search on the columns will not yield consistent results because they are not ordered. The only information we were given about the data is that any 1s in a row come before any 0s. So, we can do row-wise binary search, but column-wise does not make sense. But this discussion has given me an idea. I'll check it out to see if it's feasible and get back to you.

This post has been edited by alcdotcom: 26 February 2007 - 09:12 AM

Was This Post Helpful? 0
  • +
  • -

#13 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Algorithm analysis help

Posted 26 February 2007 - 10:33 AM

Ok, you are right that the term "binary search" is rather misleading and I think that I may have misspoken once or twice. But here is what I mean. Given the example:

X | 1 2 3 4 5 6 7 8 9
-------------------------
1 | 1 1 1 1 1 1 1 0 0
2 | 1 1 1 0 0 0 0 0 0
3 | 1 1 1 1 0 0 0 0 0
4 | 1 1 1 1 1 1 1 1 0
5 | 1 0 0 0 0 0 0 0 0
6 | 1 1 0 0 0 0 0 0 0
7 | 1 1 1 0 0 0 0 0 0
8 | 1 1 1 1 1 1 1 1 1
8 | 1 1 0 0 0 0 0 0 0

The first thing I do is look at collum n/2 (round down i guess) so collumn 4. and we go down it in a linear manner until we get to the first 1, happens to be in row 1. Now I do a binary search on row 1 (rows are sorted) (from collumn 4 to 9) and I find that the last 1 occurs in collumn 7. So now ignoring row 1, I do a linear search on column 7. That gets me to row 4. A binary seach from 7 to 9 gives me 8 as my max collumn and so I do a linear search on that collumn (ignoring row 4) and I get row 8. Which has a max elemnt at column 9... and a final search of that column ensured that my answer is unique and I have found what I am looking for.

Now I have NO idea how to calculate the Big-O of that (and I really should). I do preform linear searches on the collumns but I will not have to preform very many of them unless the data looks like:

X | 1 2 3 4 5 6 7 8 9
-------------------------
1 | 1 1 1 1 0 0 0 0 0
2 | 1 1 1 1 1 0 0 0 0
3 | 1 1 1 1 1 1 0 0 0
4 | 1 1 1 1 1 1 1 0 0
5 | 1 0 0 0 0 0 0 0 0
6 | 1 1 0 0 0 0 0 0 0
7 | 1 1 1 0 0 0 0 0 0
8 | 1 1 1 1 1 1 1 1 1

then on the binary searches I never need to search more than n/2 (the initial search) but I think that still counts as Log n. Guess I should break out my text book and re-learn recurance relations. Maybe this is just an O(n Log n) search after all, but I don't think so.

[edit]
It just occured to me that this algorithm is not very good in the "worst case" cenerio of the rows being sorted:

X | 1 2 3 4 5 6 7 8 9
-------------------------
1 | 1 0 0 0 0 0 0 0 0
2 | 1 1 0 0 0 0 0 0 0
3 | 1 1 1 0 0 0 0 0 0
4 | 1 1 1 1 0 0 0 0 0
5 | 1 1 1 1 1 0 0 0 0
6 | 1 1 1 1 1 1 0 0 0
7 | 1 1 1 1 1 1 1 0 0
8 | 1 1 1 1 1 1 1 1 0
9 | 1 1 1 1 1 1 1 1 1

in thes case it will preform n/2 linear searches and n/2 worst case binary searches O(log n). So I guess that must be O(n + n Log n). And here I thought I had a really neat algorithm. Well what is kind of neat is that it is faster on unsorted data than sorted.

This post has been edited by NickDMax: 26 February 2007 - 11:16 AM

Was This Post Helpful? 0
  • +
  • -

#14 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 26 February 2007 - 12:05 PM

I was just about to mention worst case, but then I saw you figured it out. Not a "bad" algorithm - just an "interesting" problem. :)
Was This Post Helpful? 0
  • +
  • -

#15 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 06 March 2007 - 04:22 AM

I think this problem is down for the count at O(n log n).
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2