[algogeeks] Re: Find the number of islands/connected components
Let's take the worst case, where the matrix is filled with ones.
Say that it takes S nanoseconds to scan one location, and D
nanoseconds to visit a location with DFS.
We have to scan all locations in the matrix. That is row*col scans,
which takes S*row*col ns.
At the first location we will start a DFS which will visit all of the
matrix locations. In the process it will mark them all as visited.
That will take D*row*col ns.
From then on, all of the locations are marked as visited, so we don't
do any more DFS.
Total time: S*row*col + D*row*col = (S+D)*(row*col)
But S and D are constants, so the complexity is O(row*col).
Don
On Apr 26, 8:19 am, rahul sharma rahul23111...@gmail.com wrote:
got the islands...but first we scan each element then also dfs for them if
all are 1..then how it can be o(row*col)...plz explain me complexity ofr
this
On Fri, Apr 26, 2013 at 2:07 PM, atul anand atul.87fri...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*
},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is used
to find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don dondod...@gmail.com wrote:
The complexity is still O(ROWS*COLS) because each location in the
matrix will be visited once by the loop and once by DFS. Once a
location has been visited by DFS, it is marked as visited and can't be
visited again.
Don
On Apr 25, 5:11 pm, rahul sharma rahul23111...@gmail.com wrote:
What will be complexity if all elements in matrix are 1..
when first dfs will call then all matrix will be scanned setting each
element to visited...
then again loop contiues to scan all the elements..plz explain
On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.com
wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visithttps://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visithttps://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is
used to find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don dondod...@gmail.com wrote:
The complexity is still O(ROWS*COLS) because each location in the
matrix will be visited once by the loop and once by DFS. Once a
location has been visited by DFS, it is marked as visited and can't be
visited again.
Don
On Apr 25, 5:11 pm, rahul sharma rahul23111...@gmail.com wrote:
What will be complexity if all elements in matrix are 1..
when first dfs will call then all matrix will be scanned setting each
element to visited...
then again loop contiues to scan all the elements..plz explain
On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.com
wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
got the islands...but first we scan each element then also dfs for them if
all are 1..then how it can be o(row*col)...plz explain me complexity ofr
this
On Fri, Apr 26, 2013 at 2:07 PM, atul anand atul.87fri...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*
},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
above different set of color represent different island.Simple DFS is used to
find all the island
On Fri, Apr 26, 2013 at 3:11 AM, Don dondod...@gmail.com wrote:
The complexity is still O(ROWS*COLS) because each location in the
matrix will be visited once by the loop and once by DFS. Once a
location has been visited by DFS, it is marked as visited and can't be
visited again.
Don
On Apr 25, 5:11 pm, rahul sharma rahul23111...@gmail.com wrote:
What will be complexity if all elements in matrix are 1..
when first dfs will call then all matrix will be scanned setting each
element to visited...
then again loop contiues to scan all the elements..plz explain
On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.com
wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Find the number of islands/connected components
@don..can u plz tell me how the complexity of this
http://www.geeksforgeeks.org/find-number-of-islands/ is ROW*COL?
On Thu, Apr 11, 2013 at 4:35 PM, rahul sharma rahul23111...@gmail.comwrote:
M not getting matrix..is it adjacencyif simple 1 means connected
components then first wehave 3 ones..then in second line 3 ones form 1 more
island..hw in last row 3 islands are formed..these are 3 1 means three
independent nodes...m I ryt?
On Thursday, April 11, 2013, Arpit Sood soodfi...@gmail.com wrote:
islands are five as for each cell we assume all surrounding positions to
be connected... so if coordinates are (x,y) then it is connected to (x+1,
y), (x-1, y), (x+1, y+1), (x-1, y+1), (x+1, y-1), (x-1, y-1), (x, y-1), (x,
y+1
On Thu, Apr 11, 2013 at 9:35 AM, rahul sharma rahul23111...@gmail.com
wrote:
I didnt get..plz explain more...thnx
On Thursday, April 11, 2013, Don dondod...@gmail.com wrote:
Reformatting to make it easier to see:
11000
01001
10011
0
10101
In this case an island is any set of 1's which are connected
vertically, horizontally, or diagonally.
So the five islands are
11000
01002
10022
0
30405
Don
On Apr 10, 4:34 pm, rahul sharma rahul23111...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Regards,
Arpit Sood
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Find the number of islands/connected components
What will be complexity if all elements in matrix are 1..
when first dfs will call then all matrix will be scanned setting each
element to visited...
then again loop contiues to scan all the elements..plz explain
On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.comwrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find the number of islands/connected components
islands are five as for each cell we assume all surrounding positions to be
connected... so if coordinates are (x,y) then it is connected to (x+1, y),
(x-1, y), (x+1, y+1), (x-1, y+1), (x+1, y-1), (x-1, y-1), (x, y-1), (x, y+1)
On Thu, Apr 11, 2013 at 9:35 AM, rahul sharma rahul23111...@gmail.comwrote:
I didnt get..plz explain more...thnx
On Thursday, April 11, 2013, Don dondod...@gmail.com wrote:
Reformatting to make it easier to see:
11000
01001
10011
0
10101
In this case an island is any set of 1's which are connected
vertically, horizontally, or diagonally.
So the five islands are
11000
01002
10022
0
30405
Don
On Apr 10, 4:34 pm, rahul sharma rahul23111...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Regards,
Arpit Sood
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Find the number of islands/connected components
M not getting matrix..is it adjacencyif simple 1 means connected
components then first wehave 3 ones..then in second line 3 ones form 1 more
island..hw in last row 3 islands are formed..these are 3 1 means three
independent nodes...m I ryt?
On Thursday, April 11, 2013, Arpit Sood soodfi...@gmail.com wrote:
islands are five as for each cell we assume all surrounding positions to
be connected... so if coordinates are (x,y) then it is connected to (x+1,
y), (x-1, y), (x+1, y+1), (x-1, y+1), (x+1, y-1), (x-1, y-1), (x, y-1), (x,
y+1
On Thu, Apr 11, 2013 at 9:35 AM, rahul sharma rahul23111...@gmail.com
wrote:
I didnt get..plz explain more...thnx
On Thursday, April 11, 2013, Don dondod...@gmail.com wrote:
Reformatting to make it easier to see:
11000
01001
10011
0
10101
In this case an island is any set of 1's which are connected
vertically, horizontally, or diagonally.
So the five islands are
11000
01002
10022
0
30405
Don
On Apr 10, 4:34 pm, rahul sharma rahul23111...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Regards,
Arpit Sood
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Find the number of islands/connected components
Reformatting to make it easier to see:
11000
01001
10011
0
10101
In this case an island is any set of 1's which are connected
vertically, horizontally, or diagonally.
So the five islands are
11000
01002
10022
0
30405
Don
On Apr 10, 4:34 pm, rahul sharma rahul23111...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Find the number of islands/connected components
I didnt get..plz explain more...thnx
On Thursday, April 11, 2013, Don dondod...@gmail.com wrote:
Reformatting to make it easier to see:
11000
01001
10011
0
10101
In this case an island is any set of 1's which are connected
vertically, horizontally, or diagonally.
So the five islands are
11000
01002
10022
0
30405
Don
On Apr 10, 4:34 pm, rahul sharma rahul23111...@gmail.com wrote:
{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}
Can anybody eplain how there are 5 islands in above matrix..thnx in
advance
source:-http://www.geeksforgeeks.org/find-number-of-islands/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Find Largest number in log(n)
Thanks Dave, Don and all others for this clarification. On Mon, Dec 12, 2011 at 11:23 PM, Prakash D cegprak...@gmail.com wrote: only the number of comparisons is log(n) On Mon, Dec 12, 2011 at 11:04 PM, Ankur Garg ankurga...@gmail.com wrote: Agree with dave..Its still O(n) On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote: @Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first round, involving n/2 comparisons, is O(n). Dave On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote: Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Largest number in log(n)
I think... First round of tournament sort. :D On Mon, Dec 12, 2011 at 8:02 AM, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Largest number in log(n)
@Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first round, involving n/2 comparisons, is O(n). Dave On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote: Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
Agree with dave..Its still O(n) On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote: @Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first round, involving n/2 comparisons, is O(n). Dave On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote: Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
apply MAXHEAPIFY on root ode and extract the root node -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
Max Heapify is O(n). On Mon, Dec 12, 2011 at 11:43 PM, ankit gupta ankit.itc...@gmail.comwrote: apply MAXHEAPIFY on root ode and extract the root node -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
maxheapify is lg(n)..check coremen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sorting/heapSort/heapSort.html for reference -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
^it cant get better than O(n) apparently. Just applying max-heapify once would not yield the max element. You need to construct a heap for it, which is no less than O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find Largest number in log(n)
Exactly. Really you should see this with almost no thought. It's called an adversary argument and goes like this. Since you don't know the order of elements in A, envision them as being put in order by an adversary that always knows in advance what element you're going to examine next. Now no matter which element you choose to examine, the adversary will have placed the searched-for element at a different place that's still unseen (of course he doesn't get to put it in an element you've already looked at; the adversary can't cheat). In all, he is going to do that N-1 times before you will finally beat his shell game. So unordered search is Omega(N) time. The adversary won't let you get away with fewer probes in the array. Another example: Proving that sorting is Omega(N log N) is also an adversary argument. There are N! possible orders of the elements. Sorting is equivalent to learning which of the N! orders the elements are in, because if you know which it is, you can easily unscramble them in the O(N) time it takes to move them to their correct locations and vice versa. Well by asking the adversary a yes/no question, you can eliminate at most half of the remaining orders with each question. After all, if you split the remaining set into other than 50-50 parts, say 70-30, betting that the right answer is in the smaller 30% part, the adversary will beat you with his perfect knowledge, ensuring the order you want is in the bigger 70% part. This will only slow you down, so you might as well use the 50-50 partition. Eliminating half the orders with each question means you need log_2(N!) = Omega(N log N) yes/no questions to finally beat the adversary. Since comparisons are binary decisions, the same bound must apply for comparison sorting. The point is that the adversary way of thinking is very powerful. On Dec 12, 5:16 pm, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
By Max Heapify I thought u meant to say u are making a Max Heap .. In case you use Coreman Definition Of max Heapify it just heapifies assuming the heap has been formed, But u need to make a max Heap first dude :) P.S- Clarify your concepts before posting the link :( On Tue, Dec 13, 2011 at 12:11 AM, Dipit Grover dipitgro...@gmail.comwrote: ^it cant get better than O(n) apparently. Just applying max-heapify once would not yield the max element. You need to construct a heap for it, which is no less than O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
@all..Well I am no expert but my logic says its impossible to pick the best unless and untill you look at each and every individual.Isn't this logic enough? On Tue, Dec 13, 2011 at 12:32 AM, Ankur Garg ankurga...@gmail.com wrote: By Max Heapify I thought u meant to say u are making a Max Heap .. In case you use Coreman Definition Of max Heapify it just heapifies assuming the heap has been formed, But u need to make a max Heap first dude :) P.S- Clarify your concepts before posting the link :( On Tue, Dec 13, 2011 at 12:11 AM, Dipit Grover dipitgro...@gmail.comwrote: ^it cant get better than O(n) apparently. Just applying max-heapify once would not yield the max element. You need to construct a heap for it, which is no less than O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Largest number in log(n)
only the number of comparisons is log(n) On Mon, Dec 12, 2011 at 11:04 PM, Ankur Garg ankurga...@gmail.com wrote: Agree with dave..Its still O(n) On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote: @Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first round, involving n/2 comparisons, is O(n). Dave On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote: Yes Mr. DoN First round of Tournament sort results in log(n) time for finding largest no. n/2+n/4+n/8 results n/(2^i) where ^ = power On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find the number.
@Dave :but it will take more time. any other solution O(n^2).?
On Sat, Dec 11, 2010 at 7:48 PM, Dave dave_and_da...@juno.com wrote:
@Naresh: The sequence of numbers generated by this rule for any given
starting number is called a Collatz Sequence. Try googling it.
Here is a list of the number of iterations required for n between 1
and 10,000: http://oeis.org/A006577/b006577.txt. Maybe that will help.
Dave
On Dec 11, 7:20 am, Naresh A suryanar...@gmail.com wrote:
Given range of numbers between A and B (A= B)
Find the number within given range which has more number of iterations as
per the following
n { stop ; return iteration number } if n=1;
n = 3n+1 if n is odd
n = n/2 if n is even
for eg :
n=3 odd
n=10;
n=5;
n=16;
n=8;
n=4;
n=2;
n=1;
iterations : 7
--
*
Time complexity= (n^2)
*
*NARESH ,A*
**
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Shoban babu.B
M.E.,CSA,
IISc.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find the number.
@Naresh: The sequence of numbers generated by this rule for any given
starting number is called a Collatz Sequence. Try googling it.
Here is a list of the number of iterations required for n between 1
and 10,000: http://oeis.org/A006577/b006577.txt. Maybe that will help.
Dave
On Dec 11, 7:20 am, Naresh A suryanar...@gmail.com wrote:
Given range of numbers between A and B (A= B)
Find the number within given range which has more number of iterations as
per the following
n { stop ; return iteration number } if n=1;
n = 3n+1 if n is odd
n = n/2 if n is even
for eg :
n=3 odd
n=10;
n=5;
n=16;
n=8;
n=4;
n=2;
n=1;
iterations : 7
--
*
Time complexity= (n^2)
*
*NARESH ,A*
**
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Number of Elephants
I am sorry for the link if it caused any confusion. It was just a part of the signature. Kindly disregard the link in this context. Anurag Sharma On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote: I think you can do this in O(n) time. Feel free to correct me where I'm wrong. Create a 2D array with years on one side and elephant's time alive on the other. example: 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 E1 1 1 1 11 1 1 1 1 E2 1 11 1 1 1 1 11 E3 1 1 1 1 Now for every years add vertical indices example 2006 = 3, 2007 = 3, 2008 = 3 and so on. This will give you the year with max elephant population. The array can be init with 0 or a static array can be used. @Anurag: How will you approach this problem by using LCA algorithm that your link leads to? On Jun 5, 6:16 am, amit amitjaspal...@gmail.com wrote: Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Number of Elephants
1. have an array of N years. starting with first year and ending at last year. O(N) space here. initialise all elements to zero. 2. Take array of E and birthyear first. Whenever you encounter new birthyear, do array[year]++. 3. Take array of E and deathyear now. Whenever you encounter new deathyear, do array[year]--. 4. Parse this array of year. sum_for_given_year += array[year] To me, it looks like O(N). Correct me if I am wrong. On Sun, Jun 6, 2010 at 7:56 PM, Anurag Sharma anuragvic...@gmail.com wrote: I am sorry for the link if it caused any confusion. It was just a part of the signature. Kindly disregard the link in this context. Anurag Sharma On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote: I think you can do this in O(n) time. Feel free to correct me where I'm wrong. Create a 2D array with years on one side and elephant's time alive on the other. example: 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 E1 1 1 1 1 1 1 1 1 1 E2 1 1 1 1 1 1 1 1 1 E3 1 1 1 1 Now for every years add vertical indices example 2006 = 3, 2007 = 3, 2008 = 3 and so on. This will give you the year with max elephant population. The array can be init with 0 or a static array can be used. @Anurag: How will you approach this problem by using LCA algorithm that your link leads to? On Jun 5, 6:16 am, amit amitjaspal...@gmail.com wrote: Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
Hi Janak Thanks for your reply and good that we are exited. But if you see the problem, this approach is already known which has space complexity of O(n). But this if you are lucky that the array has numbers which are not more than n itself. If the given array is say 1000 size and it has numbers which can be anything, say a very large number 14556543 (lets forget max storage of int/long in various programing languages). Then it will be a tough job to keep insertion in your hash table O(1). There will be lots of hash classes and if you do not chose a good hash function (which can be better found by knowing the nature of the numbers in the aray and we done know about them) you may end up with O(n) insertion time. So lets think a less space expensive method. Tanks, Veer On Jun 1, 9:57 am, janak chandarana jac...@gmail.com wrote: On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. You don't need to scan hash table again. Keep track of max while inserting. Update max when ever freq of some character is more than max. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find minimum number of races
Answered recently: see http://groups.google.com/group/algogeeks/msg/077bdb6a282a1184 Dave On Sep 11, 9:32 am, dinesh bansal bansal...@gmail.com wrote: Hi All, I got a question: I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all. I have a race course of 5 tracks. That means I can run 5 horses at a time. What are the minimum number of races required for this. Thanks, -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find minimum number of races
7 On Fri, Sep 11, 2009 at 8:02 PM, dinesh bansal bansal...@gmail.com wrote: Hi All, I got a question: I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all. I have a race course of 5 tracks. That means I can run 5 horses at a time. What are the minimum number of races required for this. Thanks, -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find minimum number of races
boss search the forums related t o soring million nummbers in finite memory.i have given the result and explained i On Fri, Sep 11, 2009 at 8:10 PM, sharad kumar aryansmit3...@gmail.comwrote: 7 On Fri, Sep 11, 2009 at 8:02 PM, dinesh bansal bansal...@gmail.comwrote: Hi All, I got a question: I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all. I have a race course of 5 tracks. That means I can run 5 horses at a time. What are the minimum number of races required for this. Thanks, -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find minimum number of races
7 On Fri, Sep 11, 2009 at 8:14 PM, Dave dave_and_da...@juno.com wrote: Answered recently: see http://groups.google.com/group/algogeeks/msg/077bdb6a282a1184 Dave On Sep 11, 9:32 am, dinesh bansal bansal...@gmail.com wrote: Hi All, I got a question: I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all. I have a race course of 5 tracks. That means I can run 5 horses at a time. What are the minimum number of races required for this. Thanks, -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
missed the m*n in the last fnxn call in recursion area...PLZ CORRECT
No, it's definitely not going the right way..
i wonder if this can be done using that formula...
here's this algo i just thought.
Suppose u've gotm horizontal lines and n vertical and ugive each of them an index value. i.e. a 3x2 grid would be like...
___!_(1)_! (2)___
___!_(3)_! (4)___
___!_(5)_! (6)___
!!
we start from node x to node y and the nodes we have traversed are stored in an array named TRAVERSED..the fnxn uses recursion and the algo can be said as a backtracking algo since it checks all the nodes in a particular path if already travelled it returns from that very node
ways = 0 ; // initially
Start( x,y, TRAVERSED)
{
if(x is an element of TRAVERSED) // can be found using a loop
return;
store x in TRAVERSED
if(x==y)
{
ways++; // ways is the variable thatcounts the valid path found
return;
}
if (x-1=0) // moving left from current node
start(x-1,y,TRAVERSED);
if (x+1=m*n) // movingright from current node
start(x+1,y,TRAVERSED);
if (x-n=0) // movingup from current node
start(x-n,y,TRAVERSED);
if (x+n=m*n) // movingdown from current node
start(x+n,y,TRAVERSED);
}
-- Smile, it's the second best thing you can do with your lips..By the way...the First thing is ur KISS :-)Prashant Bhargava--
www.excogitation.tkor
www.hemantdesign.com/prashant -- Smile, it's the second best thing you can do with your lips..
By the way...the First thing is ur KISS :-)Prashant Bhargava-- www.excogitation.tkor www.hemantdesign.com/prashant
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
There's a small error in my formula. The formula holds for a NxM grid (N horizontal and M vertical lines) where N= n+1 and M = m+1, which essentially boils down to C(N+M-2, N-1) = C(N+M-2,M-1). This should work fine. -Shishir --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
Can't understand man!!! can u explain and also does your formula take into account the position of starting and ending points or is it just about the corner points that u r talking abt -- Smile, it's the second best thing you can do with your lips.. By the way...the First thing is ur KISS :-)Prashant Bhargava-- www.excogitation.tkor www.hemantdesign.com/prashant --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
This works only if you assume that you do not go backwards i.e. your max path length is N+M-2. If you can go backwards, then I think that there are more paths than just these. e.g. in 3x3 grid you can have path length more than 4 (1,1) - (1,2) - (2,2) - (2,1) - (3,1) - (3,2) - (3,3) I havent given much thought on how to count all possible paths ... maybe some variation of Floyd-Warshalls ... -Dhyanesh On 4/6/06, shishir [EMAIL PROTECTED] wrote: There's a small error in my formula. The formula holds for a NxM grid (N horizontal and M vertical lines) where N= n+1 and M = m+1, which essentially boils down to C(N+M-2, N-1) = C(N+M-2,M-1). This should work fine. -Shishir --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
Well the formula works only for the corner end points as starting and ending node and that too on the diagonal ends. Its not a general formula for any set of starting/ending nodes. @Dhyanesh I think the problem clearly states that the nodes can only be traversed once i.e. no repetition. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
Shishir , have a look at my example ... there is no repetition of points in it. Your formula wont work for it. -Dhyanesh On 4/6/06, shishir [EMAIL PROTECTED] wrote: Well the formula works only for the corner end points as starting and ending node and that too on the diagonal ends. Its not a general formula for any set of starting/ending nodes. @Dhyanesh I think the problem clearly states that the nodes can only be traversed once i.e. no repetition. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
i don't understand, i am pretty new at programming. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
