[algogeeks] Re: Search an element in a sorted and pivoted array
1.) Find the pivot point. to find pivot – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it. 2.) divide the array into two subarray and apply binary search. for calling binary search in two subarray - if the element is greater than the first element : search (binary seach) in left subarray else in right subarray. example array : 123456 pivoted array : 345612 complexity :O(logn) where n are the number of elements On Tuesday, August 28, 2012 11:26:03 PM UTC+5:30, rahul sharma wrote: plz provide me algo for this,thnx -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oPmnJQ8tEGwJ. 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: Search an element in a sorted and pivoted array
@Rahul: Please tell us what you mean by a pivoted array. Dave On Tuesday, August 28, 2012 12:56:03 PM UTC-5, rahul sharma wrote: plz provide me algo for this,thnx -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/iomheqkDEd0J. 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: search in O(logn)
smthng like this...
*if*(arr[mid] arr[mid + 1])
return mid;
if(arr[low] arr[mid])
return findPoint(arr, low, mid-1);
else
return findPoint(arr, mid + 1, high);
On Sat, Jun 9, 2012 at 12:36 AM, Hassan Monfared hmonfa...@gmail.comwrote:
Hi pharta :
find the point where it is rotated to get 14-1 O(log(n)) how can
you find rotation point in log(n) ?
On Fri, Jun 8, 2012 at 6:57 PM, partha sarathi Mohanty
partha.mohanty2...@gmail.com wrote:
It is easy.. find the point where it is rotated to get 14-1 O(log(n))
since 214 that means u have to find it in subarray [123].. do a binary
search here o(long(n))
final 2*O(log(n))...
On Fri, Jun 8, 2012 at 7:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] a[0] and
a[k] a[0]. Then if x a[k], do a binary search to find x in {a[k] ...
a[n-1]}; otherwise do a binary search to find x in {a[0] ... a[k]}.
Dave
On Friday, June 8, 2012 8:41:47 AM UTC-5, Hassan Monfared wrote:
A sorted array of integers is rotated unknown times. find an item in
O(logn) time and O(1) space complexity.
for example : 1,2,3,7,10,14 ---rotated 3 times-- 7,10,14,1,2,3
find 2 in O(logn) time in O(1) space complexity
Regards
Hassan H. Monfared
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/KD9Hz01ZIJ8J.
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.
--
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: search in O(logn)
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] a[0] and
a[k] a[0]. Then if x a[k], do a binary search to find x in {a[k] ...
a[n-1]}; otherwise do a binary search to find x in {a[0] ... a[k]}.
Dave
On Friday, June 8, 2012 8:41:47 AM UTC-5, Hassan Monfared wrote:
A sorted array of integers is rotated unknown times. find an item in
O(logn) time and O(1) space complexity.
for example : 1,2,3,7,10,14 ---rotated 3 times-- 7,10,14,1,2,3
find 2 in O(logn) time in O(1) space complexity
Regards
Hassan H. Monfared
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/KD9Hz01ZIJ8J.
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: search in O(logn)
Yes,
Thanks Dave. for non-distinct items It's not possible.
On Fri, Jun 8, 2012 at 6:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] a[0] and
a[k] a[0]. Then if x a[k], do a binary search to find x in {a[k] ...
a[n-1]}; otherwise do a binary search to find x in {a[0] ... a[k]}.
Dave
On Friday, June 8, 2012 8:41:47 AM UTC-5, Hassan Monfared wrote:
A sorted array of integers is rotated unknown times. find an item in
O(logn) time and O(1) space complexity.
for example : 1,2,3,7,10,14 ---rotated 3 times-- 7,10,14,1,2,3
find 2 in O(logn) time in O(1) space complexity
Regards
Hassan H. Monfared
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/KD9Hz01ZIJ8J.
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: search in O(logn)
It is easy.. find the point where it is rotated to get 14-1 O(log(n))
since 214 that means u have to find it in subarray [123].. do a binary
search here o(long(n))
final 2*O(log(n))...
On Fri, Jun 8, 2012 at 7:44 PM, Dave dave_and_da...@juno.com wrote:
@Hassan: This is not possible without additional conditions. E.g., you
cannot find the 1 in the array {0,0,0,...,0,1,0,0,...,0} in less than O(n)
time.
But with the condition that the elements of the array are pairwise
distinct, you can use a binary search to find k such that a[k-1] a[0] and
a[k] a[0]. Then if x a[k], do a binary search to find x in {a[k] ...
a[n-1]}; otherwise do a binary search to find x in {a[0] ... a[k]}.
Dave
On Friday, June 8, 2012 8:41:47 AM UTC-5, Hassan Monfared wrote:
A sorted array of integers is rotated unknown times. find an item in
O(logn) time and O(1) space complexity.
for example : 1,2,3,7,10,14 ---rotated 3 times-- 7,10,14,1,2,3
find 2 in O(logn) time in O(1) space complexity
Regards
Hassan H. Monfared
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/KD9Hz01ZIJ8J.
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] binary search tree over btree
In BST the height can be made as bad as u can but in case of btree the height can not be more than log n base 2 because for each internal node it is necessary to have at least 2 child and here all the leaf nodes must be at the same label. On Sun, Apr 1, 2012 at 8:34 PM, arun kumar kumar0...@gmail.com wrote: hi i just like to know when you will go for binary search tree over btree. advantage and disadvantage, application of both of them. thank you in advance Regards, Arun kumar -- 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 Sanjiv Yadav MobNo.- 8050142693 Email Id- sanjiv2009...@gmail.com -- 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] binary search tree over btree
hi i just like to know when you will go for binary search tree over btree. advantage and disadvantage, application of both of them. thank you in advance Regards, Arun kumar -- 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] Binary Search Tree Question
What does this function do?
void function(Node **node){
if(*node!=NULL){
function((*node)-Left);
Node *temp;
temp = (*node)-Left;
(*node)-Left= (*node)-Right;
(*node)-Right = temp;
function((*node)-Right);
}
}
--
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] Binary Search Problem
These may be of interest as well: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 https://webcache.googleusercontent.com/search?q=cache:onpOivQX668J:googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html+cd=1hl=enct=clnkclient=ubuntu On Sunday, January 8, 2012 5:52:40 PM UTC+5:30, Sanjay Rajpal wrote: @Atul : got it. thanx :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qrVfUNev674J. 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] Binary Search Problem
In binary search, mid = start + (end-start)/2 is used to avoid overflow, as said by a book. why can't we use mid = (start + end)/2, it says this statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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] Binary Search Problem
not clear what you are trying to ask...can you quote exactly from the book? Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Jan 8, 2012 at 4:34 PM, Sanjay Rajpal srn...@gmail.com wrote: In binary search, mid = start + (end-start)/2 is used to avoid overflow, as said by a book. why can't we use mid = (start + end)/2, it says this statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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] Binary Search Problem
actually book pages are images. My question is why second statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286, +91-9729683720 * On Sun, Jan 8, 2012 at 3:07 AM, saurabh singh saurab...@gmail.com wrote: not clear what you are trying to ask...can you quote exactly from the book? Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Jan 8, 2012 at 4:34 PM, Sanjay Rajpal srn...@gmail.com wrote: In binary search, mid = start + (end-start)/2 is used to avoid overflow, as said by a book. why can't we use mid = (start + end)/2, it says this statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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] Binary Search Problem
@Sanjay: suppose Max_INT range is 300 now suppose end=300 and start =2 now using (start+end)/2 i.e *302*/2 but 302 goes out of range for and interger type as assumed... but if we use start + (end-start)/2 THEN 2 + (300-2)/2 , i.e 2+ *298*/2 here 298 300 hence it within int_Max range which was assumed 300.. On Sun, Jan 8, 2012 at 4:41 PM, Sanjay Rajpal sanjay.raj...@live.in wrote: actually book pages are images. My question is why second statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286, +91-9729683720 * On Sun, Jan 8, 2012 at 3:07 AM, saurabh singh saurab...@gmail.com wrote: not clear what you are trying to ask...can you quote exactly from the book? Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Jan 8, 2012 at 4:34 PM, Sanjay Rajpal srn...@gmail.com wrote: In binary search, mid = start + (end-start)/2 is used to avoid overflow, as said by a book. why can't we use mid = (start + end)/2, it says this statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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. -- 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] Binary Search Problem
@Atul : got it. thanx :) * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Sun, Jan 8, 2012 at 3:27 AM, atul anand atul.87fri...@gmail.com wrote: @Sanjay: suppose Max_INT range is 300 now suppose end=300 and start =2 now using (start+end)/2 i.e *302*/2 but 302 goes out of range for and interger type as assumed... but if we use start + (end-start)/2 THEN 2 + (300-2)/2 , i.e 2+ *298*/2 here 298 300 hence it within int_Max range which was assumed 300.. On Sun, Jan 8, 2012 at 4:41 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: actually book pages are images. My question is why second statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286, +91-9729683720 * On Sun, Jan 8, 2012 at 3:07 AM, saurabh singh saurab...@gmail.comwrote: not clear what you are trying to ask...can you quote exactly from the book? Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Jan 8, 2012 at 4:34 PM, Sanjay Rajpal srn...@gmail.com wrote: In binary search, mid = start + (end-start)/2 is used to avoid overflow, as said by a book. why can't we use mid = (start + end)/2, it says this statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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. -- 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] Binary Search Problem
@atul: +1, i too thought the same this comes handly esp, when the derived datatypes are used with a range limitations. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_4SiQzGadwkJ. 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: Search an element in an Infinite array
What is the logic on choosing power of two as search indexes ? On Oct 24, 12:56 am, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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.
[algogeeks] Re: Search an array of unknown length
nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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: Search an array of unknown length
@saurabh u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second one is integer...both's size is 4 do it without passing http://www.ideone.com/8olTP On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.com wrote: nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- **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: Search an array of unknown length
Well sir I am fully aware why this is hapening.Kindly reread what I wrote .*what if we are given only the address of the array.* I personaly feel anyone who asked the question never expected this to be the answer.(using sizeof). On Tue, Aug 23, 2011 at 2:42 PM, sagar pareek sagarpar...@gmail.com wrote: @saurabh u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second one is integer...both's size is 4 do it without passing http://www.ideone.com/8olTP On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.comwrote: nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- ** 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. -- 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: Search an array of unknown length
hmm ok my mistake of reading On Tue, Aug 23, 2011 at 6:56 PM, saurabh singh saurab...@gmail.com wrote: Well sir I am fully aware why this is hapening.Kindly reread what I wrote .*what if we are given only the address of the array.* I personaly feel anyone who asked the question never expected this to be the answer.(using sizeof). On Tue, Aug 23, 2011 at 2:42 PM, sagar pareek sagarpar...@gmail.comwrote: @saurabh u are getting sizeof(a)/sizeofa[0] =1 coz fiest one is pointer and second one is integer...both's size is 4 do it without passing http://www.ideone.com/8olTP On Tue, Aug 23, 2011 at 1:28 PM, vikas vikas.rastogi2...@gmail.comwrote: nopes, you need to know where the hell it ends even if this is a string , it ends with convention of ending 0. in case it is stream , we know the data length. in case of array, above mentioned approach should work. sizeof(arr)/sizeof(arr[0]) if you are given only a pointer and no length, you can address until there is another page starts in memory , not belonging to the process. On Aug 23, 7:07 am, saurabh singh saurab...@gmail.com wrote: Just a small code to back up my point...http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- ** 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. -- 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. -- **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
Re: [algogeeks] Re: Search an array of unknown length
@dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
[algogeeks] Re: Search an array of unknown length
If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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: Search an array of unknown length
That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- 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: Search an array of unknown length
Just a small code to back up my point... http://www.ideone.com/woRiT On Tue, Aug 23, 2011 at 7:33 AM, saurabh singh saurab...@gmail.com wrote: That would take all the fun awaywhat if you are given only the address of the array?This wont work in that case On Mon, Aug 22, 2011 at 10:39 PM, asdqwe ayushgoel...@gmail.com wrote: If i am not wrong, the only possible solution can be len=sizeof(arr)/sizeof(arr[0]) i.e. find the length from the array itself. On Aug 22, 9:01 pm, saurabh singh saurab...@gmail.com wrote: @dave or anyone??? response please On Sun, Aug 21, 2011 at 12:43 PM, saurabh singh saurab...@gmail.com wrote: kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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: Search an array of unknown length
kkk...not sure assume no number is greater than 1000(I mentioned There has to be some additional constraints to make the problem solvable) Now check 1st element if not the desired element keep multiplying with 2 the previous range till either one of these condition is satisfied *1.An exception is caught* *2.Number greater than 1000 occurs.* suppose this happens for *1024 *for the given example. then we will check out for (512+1024)/2 th element for the above condition. If true than again branch like binary search.This way can element which on left side doesn't gives any exception and maintains the constraints while on the right it violates the same.So we may land up with the desired index and can then perform binary search... PS:There are lots of assumption in this approach and the more I write the more I get convinced that its a plain stupid idea... -- 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: Search an array of unknown length
@dave may be its a bit offtopic,(and may be stupid) but if the numbers are in a small range (say 1 to 1000) isn't the probability that the absolute garbage value would be greater than the array elements(assuming garbage to be bits of random 0's and 1's)?Assuming we have not entered into some other valid memory area.Can't this fact be used to produce a solution that's valid for most of the cases? On Sat, Aug 20, 2011 at 12:21 AM, sagar pareek sagarpar...@gmail.comwrote: thanks for pointing it out On Sat, Aug 20, 2011 at 12:16 AM, Dave dave_and_da...@juno.com wrote: @Sagar: So far so good, but you are not guaranteed to get an exception. Example, int a[987] is followed in memory by char b[1000], which is a dictionary. You won't detect an exception until you get to at least a[262144] (2 to the 18th). But you will pick up plenty of garbage which may throw off your binary search. Dave On Aug 19, 1:26 pm, sagar pareek sagarpar...@gmail.com wrote: Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **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. -- **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. -- 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.
[algogeeks] Re: Search an array of unknown length
@Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **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: Search an array of unknown length
Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **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: Search an array of unknown length
Well in that case additive approach will work. Sanju :) -- 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: Search an array of unknown length
@Sagar: So far so good, but you are not guaranteed to get an exception. Example, int a[987] is followed in memory by char b[1000], which is a dictionary. You won't detect an exception until you get to at least a[262144] (2 to the 18th). But you will pick up plenty of garbage which may throw off your binary search. Dave On Aug 19, 1:26 pm, sagar pareek sagarpar...@gmail.com wrote: Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **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: Search an array of unknown length
thanks for pointing it out On Sat, Aug 20, 2011 at 12:16 AM, Dave dave_and_da...@juno.com wrote: @Sagar: So far so good, but you are not guaranteed to get an exception. Example, int a[987] is followed in memory by char b[1000], which is a dictionary. You won't detect an exception until you get to at least a[262144] (2 to the 18th). But you will pick up plenty of garbage which may throw off your binary search. Dave On Aug 19, 1:26 pm, sagar pareek sagarpar...@gmail.com wrote: Well sorry but i forget to mention exceptions in the solution. Here is the complete solution :- The key idea here is to simultaneously do a binary search for the end of the array as well as the key. We try to look for A[2k ] in the k-th step and catch exceptions for successive values of k till either we hit an exception or we hit a number greater than or equal to b. Then we do a binary search for b between indices 2k - 1 and 2k . The runtime of the search algorithm is 0 (l og 叫. On Fri, Aug 19, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: @Everyone: The problem says that the array is of UNKNOWN length, but all of the solutions presented assume that the array is of INFINITE length. Suppose, e.g., that the length is 987, but you don't know that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the array. An address violation may occur, or arbitrary data, unrelated to the data in the array may be used. I think the problem as stated is unsolvable. Dave On Aug 19, 12:48 pm, sagar pareek sagarpar...@gmail.com wrote: HI, I have encountered a problem :- You have an array of *UNKNOWN *length . And you have to find an element in O(log(n)) time without using any extra space. -- **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. -- **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] binary search
How to optimise binary search so dat it makes only one comparison instead of 2 dat it generally does?? -- 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] binary search
int Modified_BinarySearch(int A[], int N, int value) {
int low = 0;
int high = N;
while (low high) {
int mid = (low + high)/2;
if (A[mid] value)
low = mid + 1;
else
high = mid;
}
if ((low N) (A[low] == value))
return low;
else
return -1;
}
Regards
Anurag Atri
--
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] binary search tree question!!!!
Please tell the solution of this question Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can’t pass the value k to any function also -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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: Search node in a binary tree
Guys i always have this doubt.Please tell me whether stack frames allocated
for each recursive call will be cleared if we return in the middle of a
recursive call?
On Tue, Jul 12, 2011 at 10:22 PM, Don dondod...@gmail.com wrote:
// Similar to other suggestions, but without tail recursion.
ptr search(ptr root, int value)
{
ptr result = 0;
while(root !result)
{
result = (root-tag == value) ? root : search(root-left,
value);
root = root-right;
}
return result;
}
On Jul 12, 8:28 am, anonymous procrastination opamp1...@gmail.com
wrote:
Hello,
Suppose you have to search a particular node in a binary tree.
The code is quite simple. Pick up any traversal and see if any node
matches the value.
Doubt I have is that how to pull out of the recursive function at the
instant node is found.
In iterative algos we use a break.
Here I can use a global flag variable. But any other bettr way of
doing this?
--
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: Search node in a binary tree
On Wed, Jul 13, 2011 at 1:40 PM, sameer.mut...@gmail.com sameer.mut...@gmail.com wrote: Guys i always have this doubt.Please tell me whether stack frames allocated for each recursive call will be cleared if we return in the middle of a recursive call? In normal condition, the return statement will take the control to the functions's caller, which might be the function itself if its a recursive call. There is no way to return to the original caller, who called your recursive function, without skipping the stack. I think the only way to skip to the original caller, is by throwing an exception from the recursive function, which is caught by the original caller. The exception will unwind the stack till someone catches it. -- -- 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: Search node in a binary tree
There is no reason to use recursion to search a binary tree. Don On Jul 12, 8:28 am, anonymous procrastination opamp1...@gmail.com wrote: Hello, Suppose you have to search a particular node in a binary tree. The code is quite simple. Pick up any traversal and see if any node matches the value. Doubt I have is that how to pull out of the recursive function at the instant node is found. In iterative algos we use a break. Here I can use a global flag variable. But any other bettr way of doing this? -- 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: Search node in a binary tree
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
return search(root-left,node)||search(root-right,node);
}
TC O(N)
notify me via mail if anything wrong.?
Thanks
Shashank
CSE,BIT Mesra
--
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: Search node in a binary tree
@bittu
On 7/12/11, Aniket Dutta aniketdutt...@gmail.com wrote:
what will happen if node is not found?.
you are not checking it
On 7/12/11, bittu shashank7andr...@gmail.com wrote:
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
return search(root-left,node)||search(root-right,node);
}
TC O(N)
notify me via mail if anything wrong.?
Thanks
Shashank
CSE,BIT Mesra
--
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: Search node in a binary tree
what will happen if node is not found?.
you are not checking it
On 7/12/11, bittu shashank7andr...@gmail.com wrote:
whats the problem with this
bool search(root,node)
{
if(root==node)
return 1;
else
return search(root-left,node)||search(root-right,node);
}
TC O(N)
notify me via mail if anything wrong.?
Thanks
Shashank
CSE,BIT Mesra
--
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: Search node in a binary tree
@Aniket: Just add a condition at the begining: if(root == NULL) return 0; -- 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: Search node in a binary tree
@yeah right On Tue, Jul 12, 2011 at 7:36 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Aniket: Just add a condition at the begining: if(root == NULL) return 0; -- 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: Search node in a binary tree
@bittu On Tue, Jul 12, 2011 at 8:09 PM, Aniket Dutta aniketdutt...@gmail.comwrote: @yeah right On Tue, Jul 12, 2011 at 7:36 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Aniket: Just add a condition at the begining: if(root == NULL) return 0; -- 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: Search node in a binary tree
sorry @ankit On Tue, Jul 12, 2011 at 8:10 PM, Aniket Dutta aniketdutt...@gmail.comwrote: @bittu On Tue, Jul 12, 2011 at 8:09 PM, Aniket Dutta aniketdutt...@gmail.comwrote: @yeah right On Tue, Jul 12, 2011 at 7:36 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Aniket: Just add a condition at the begining: if(root == NULL) return 0; -- 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.
[algogeeks] Re: Search node in a binary tree
// Similar to other suggestions, but without tail recursion.
ptr search(ptr root, int value)
{
ptr result = 0;
while(root !result)
{
result = (root-tag == value) ? root : search(root-left,
value);
root = root-right;
}
return result;
}
On Jul 12, 8:28 am, anonymous procrastination opamp1...@gmail.com
wrote:
Hello,
Suppose you have to search a particular node in a binary tree.
The code is quite simple. Pick up any traversal and see if any node
matches the value.
Doubt I have is that how to pull out of the recursive function at the
instant node is found.
In iterative algos we use a break.
Here I can use a global flag variable. But any other bettr way of
doing this?
--
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] Google Search by Image
An idea which strikes to mind is, 1.Initially to form a map based on the text and all related text to it.[text,images]map 2.Also make a bitwise manipulation of every image and relate the texts to it.[imagebitwise,texts] map 3.If a image is put forth for search, check the texts from [imagebitwise,texts] map based on its bitwise calculation 4.Render all the images from the [text,images]map matching to the texts from step-3 What do you feel about this? On Sat, Jun 18, 2011 at 9:29 PM, DIPANKAR DUTTA dutta.dipanka...@gmail.comwrote: I think all of us use Google Search by Imagehttp://www.youtube.com/watch?v=t99BfDnBZcI . If you donot know plz ref the following link: http://www.youtube.com/watch?v=t99BfDnBZcI can you give the efficient algorithm to design this? * *-- Thanks and Regards, -- *DIPANKAR DUTTA* Visiting Research Scholar Dept of Computing, Macquarie University, Sydney, Australia ph.no-+61 2 98509079 ( Mon-Fri 10:15-7:00) Sydney time email: dipankar.du...@mq.edu.au -- 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. -- Thanks and regards, Raghavan.K.L http://in.linkedin.com/in/raghavankl -- 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] Google Search by Image
There are specific algorithms for image matching. One of the more famous ones is to use Wavelet coefficients. Wavelet Coefficients are resolution independent ways of representing image content (The image data is mapped into a 0-1 2D space). You can perform a 2D difference analysis of the searched image's wavelet representation with the Wavelet representation of the images in your index and then rank the results based on the degree of matching pruning the results based on thresholds. The challenge here is to scale the algorithm to the scale of the Google Index data. I'll leave that discussion for another thread. (For more info start here on wikipedia: http://en.wikipedia.org/wiki/Wavelet_transforms). Note: a course in Image Processing is helpful. Also, this method works even if the image is resized. (Side Note: Rotational changes don't affect the first few coefficients, but affect the later ones) ^ This answer is only for the Search by Images feature. For the image search by text features, you use the standard Google way of associating images with their nearby textual content and then search based on those tags. -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/3a_k2ON4CJ0J. 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] A* search
Hi All, A* search with consistent heuristics is supposed to ensure that an optimal path to a repeated state is always the first path generated, but consider the following example: /---4---A(h=15)--30--\ S(h=18)G (h=0) \ ---5---B(h=17)--20--/ where S and G are the start and goal nodes respectively, in this case G is a repeated state which is also the goal state, but carry out A* on the above graph, we get: Expand S: get children A (f = 4 + 15 = 19) and B (f = 5 + 17 = 22), and A has a smaller f value, we next expand A Expand A: get child G (f = 34 + 0 = 34) at this point we obviously have a sub-optimal path to G with cost 34 the optimal cost of 5 + 20 = 25? Is this just a special case where the goal is also a repeated state or am I missing something here? Thanks in advance. e. -- 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] binary search for Linked List?
use skip list:) On Thu, Mar 10, 2011 at 2:31 PM, ravi teja ravitejal...@gmail.com wrote: @Utkarsh : Yeah , that is when you can access any element in O(1) time and the elements are sorted.This happens in a sorted array where you get an overall complexisty of O(logn). -- 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] binary search for Linked List?
what is skip list On Fri, Mar 11, 2011 at 5:58 AM, priya mehta priya.mehta...@gmail.comwrote: use skip list:) On Thu, Mar 10, 2011 at 2:31 PM, ravi teja ravitejal...@gmail.com wrote: @Utkarsh : Yeah , that is when you can access any element in O(1) time and the elements are sorted.This happens in a sorted array where you get an overall complexisty of O(logn). -- 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. -- UTKARSH SRIVATAV CSE-3 B-TECH 2nd YEAR 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] binary search for Linked List?
but as far as i know binary search takes O(logn)time tosearch an element On Tue, Mar 8, 2011 at 9:35 PM, ravi teja ravitejal...@gmail.com wrote: Yes , it is possible . But it does not make sense . The thing that matters while doing binary search for arrays is that we can access any element in O(1) time . But , for a linked list it becomes an average of O(n) . And on average we have an O(nlogn) algorithm with highly confusing code and messy pointers . -- 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. -- UTKARSH SRIVATAV CSE-3 B-TECH 2nd YEAR 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.
[algogeeks] binary search for Linked List?
Is it possible to implement -- 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] binary search for Linked List?
Yes , it is possible . But it does not make sense . The thing that matters while doing binary search for arrays is that we can access any element in O(1) time . But , for a linked list it becomes an average of O(n) . And on average we have an O(nlogn) algorithm with highly confusing code and messy pointers . -- 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] top search queries
please give your ideas for this On Fri, Jan 21, 2011 at 2:28 PM, snehal jain learner@gmail.com wrote: Magy! receives a huge amount of queries everyday. They don’t want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don’t want to store all the queries. Hint: split the stream into windows and accept some error in estimation. -- 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.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 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] top search queries
First Approach, 0) the queries can be considered as an infinite stream. maintain a global count of the number of queries coming from the stream (used for calc the frequency %). 1) maintain a min-heap (has just top 100 queries by frequency) + hash table (where we store frequency for each word in heap). the element at the top of the heap is the query having min-frequency. 2) once we get a query. we check if it is present in the hashtable. if yes then update this query frequency reorder the heap. if no then do nothing. here I assume we want top 100 most queries. this can be easily extended to include all queries having 0.1% frequency. Complexity: time: O(logn) + O(n) [for heap hashtable construction] here n=100 space: 2O(n) Will come up with something better. If extend n to say 1,00,000, the space complexity is going to be a problem. Second Approach, 0) We could use only one min-heap. Each node has the (query, frequency %). 1) get the query from the stream. Traverse the heap to see if this query is already present. If yes then re-calculate the frequency if needed reorder the heap. if query not present in the heap, then calc it's frequency see if the frequency of the node at min-heap is the current query freq. if (curr_query_freq min-heap node freq.) then swap the min-heap node reorder the heap. else continue. Time: O(logn) n=number of queries we want to consider. space: O(n) Srikar On Mon, Jan 31, 2011 at 6:57 PM, snehal jain learner@gmail.com wrote: please give your ideas for this On Fri, Jan 21, 2011 at 2:28 PM, snehal jain learner@gmail.comwrote: Magy! receives a huge amount of queries everyday. They don’t want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don’t want to store all the queries. Hint: split the stream into windows and accept some error in estimation. -- 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.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 algogeeks@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 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] top search queries
@above in your second approach, in the worst case you need to traverse the heap in O(n) time. -- 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] top search queries
Magy! receives a huge amount of queries everyday. They don’t want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don’t want to store all the queries. Hint: split the stream into windows and accept some error in estimation. -- 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] Strings search problem
Distance is measured on number of words. what is your meaning ? can you explain it? 2010/12/29 Davin dkthar...@googlemail.com Given set of words, find an area of the text where these words are as close to each other as possible. Distance is measured on number of words. e.g. for words [rat”, “jat”, “pat”] and text “rat stop the pat blah blah jat by pat jat tra la la” such area is “cat by mat bat” -- 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] Strings search problem
Given set of words, find an area of the text where these words are as close to each other as possible. Distance is measured on number of words. e.g. for words [rat”, “jat”, “pat”] and text “rat stop the pat blah blah jat by pat jat tra la la” such area is “cat by mat bat” -- 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] binary search tree
WAP to create a binary search tree and search a node in it using linked list representation -- 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] binary search tree
I guess this list is not to get your home works done. Please use google before throwing anything and everything here. On Wed, Oct 6, 2010 at 1:57 PM, addicted2abhishesh abhishesh.srivast...@gmail.com wrote: WAP to create a binary search tree and search a node in it using linked list representation -- 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. -- Thanks Regards, Gaurav Gupta Associate Software Engineer IBM Software Lab |India Email: gauravgu...@in.ibm.com Ph No. : +91-7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- 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: search a 2d sorted array in less than O(n)
Actual complexity of above algorithm = O(n^1.6)
On Sep 27, 8:19 am, Gene gene.ress...@gmail.com wrote:
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything right and downward from
a[m/2][n/2] (including row m/2 and column n/2) because these elements
are all larger than the middle one.
3) The element you're looking for is larger. In this case you can
again throw out about 1/4 of the array: everything left and upward
from a[m/2][n/2] inclusive.
Then you can search the remaining 3/4 of the array recursively.
By throwing away 1/4 of mn elements at each step, you can easily work
out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
performance.
Here is code and a very quick unit test:
#include stdio.h
#include stdlib.h
typedef int SORTED_ARRAY[100][100];
/* Look for x in row- and column-sorted a[i0..i1][j0..j1].
Put indices in *i and *j and return 1 if found,
else return 0.
*/
int search(SORTED_ARRAY a, int x,
int i0, int i1,
int j0, int j1,
int *i, int *j)
{
if (i0 = i1 j0 = j1) {
int mi = (i0 + i1) / 2;
int mj = (j0 + j1) / 2;
if (x == a[mi][mj]) {
*i = mi; *j = mj;
return 1;
}
return (x a[mi][mj]) ?
search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
search(a, x, i0, mi - 1, mj, j1, i, j) ||
search(a, x, mi, i1, j0, mj - 1, i, j)
:
search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
search(a, x, i0, mi, mj + 1, j1, i, j) ||
search(a, x, mi + 1, i1, j0, mj, i, j);
}
return 0;
}
int max(int x, int y) { return x y ? x : y; }
int main(void)
{
int i, j, m, n, ri, rj;
SORTED_ARRAY a;
// A small unit test. Build a m x n
// sorted array with random differences.
m = 100; n = 100;
a[0][0] = 0;
for (i = 1; i m; i++)
a[i][0] = a[i - 1][0] + rand() % 1000;
for (j = 1; j n; j++) {
a[0][j] = a[0][j - 1] + rand() % 1000;
for (i = 1; i m; i++)
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
}
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
printf(%8d, a[i][j]);
}
printf(\n);
}
for (i = 0; i m; i++) {
for (j = 32; j n; j++) {
int r = search(a, a[i][j], 0, m - 1, 0, n - 1, ri, rj);
if (!r) {
printf(failed at a[%d][%d]\n, i, j, a[i][j]);
return 1;
}
else if (a[ri][rj] != a[i][j]) {
printf(mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n,
i, j, a[i][j], ri, rj, a[ri][rj]);
return 1;
}
}
}
printf(pass!\n);
return 0;
}
On Sep 21, 7:40 am, jagadish jagadish1...@gmail.com wrote:
Hi all,
Given a 2d array which is sorted row wise and column wise as well,
find a specific element in it in LESS THAN O(n).
PS: an O(n) solution would involve skipping a column or a row each
time from the search and moving accordingly.
Solution less than O(n) is desirable!
--
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: search a 2d sorted array in less than O(n)
I feel the binary search approach as given by Saurabh Singh or like
moving from top right row, doing binary search in the row 0, find the
element being searched (say x) or one less than that (say y), followed
by binary search in the column below 'y' and proceeding in this way
can give a less than O(n) solution.
Please provide your comments in any
Thanks
Sourav
On Sep 27, 11:09 am, prodigy 1abhishekshu...@gmail.com wrote:
Actual complexity of above algorithm = O(n^1.6)
On Sep 27, 8:19 am, Gene gene.ress...@gmail.com wrote:
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything right and downward from
a[m/2][n/2] (including row m/2 and column n/2) because these elements
are all larger than the middle one.
3) The element you're looking for is larger. In this case you can
again throw out about 1/4 of the array: everything left and upward
from a[m/2][n/2] inclusive.
Then you can search the remaining 3/4 of the array recursively.
By throwing away 1/4 of mn elements at each step, you can easily work
out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
performance.
Here is code and a very quick unit test:
#include stdio.h
#include stdlib.h
typedef int SORTED_ARRAY[100][100];
/* Look for x in row- and column-sorted a[i0..i1][j0..j1].
Put indices in *i and *j and return 1 if found,
else return 0.
*/
int search(SORTED_ARRAY a, int x,
int i0, int i1,
int j0, int j1,
int *i, int *j)
{
if (i0 = i1 j0 = j1) {
int mi = (i0 + i1) / 2;
int mj = (j0 + j1) / 2;
if (x == a[mi][mj]) {
*i = mi; *j = mj;
return 1;
}
return (x a[mi][mj]) ?
search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
search(a, x, i0, mi - 1, mj, j1, i, j) ||
search(a, x, mi, i1, j0, mj - 1, i, j)
:
search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
search(a, x, i0, mi, mj + 1, j1, i, j) ||
search(a, x, mi + 1, i1, j0, mj, i, j);
}
return 0;
}
int max(int x, int y) { return x y ? x : y; }
int main(void)
{
int i, j, m, n, ri, rj;
SORTED_ARRAY a;
// A small unit test. Build a m x n
// sorted array with random differences.
m = 100; n = 100;
a[0][0] = 0;
for (i = 1; i m; i++)
a[i][0] = a[i - 1][0] + rand() % 1000;
for (j = 1; j n; j++) {
a[0][j] = a[0][j - 1] + rand() % 1000;
for (i = 1; i m; i++)
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
}
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
printf(%8d, a[i][j]);
}
printf(\n);
}
for (i = 0; i m; i++) {
for (j = 32; j n; j++) {
int r = search(a, a[i][j], 0, m - 1, 0, n - 1, ri, rj);
if (!r) {
printf(failed at a[%d][%d]\n, i, j, a[i][j]);
return 1;
}
else if (a[ri][rj] != a[i][j]) {
printf(mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n,
i, j, a[i][j], ri, rj, a[ri][rj]);
return 1;
}
}
}
printf(pass!\n);
return 0;
}
On Sep 21, 7:40 am, jagadish jagadish1...@gmail.com wrote:
Hi all,
Given a 2d array which is sorted row wise and column wise as well,
find a specific element in it in LESS THAN O(n).
PS: an O(n) solution would involve skipping a column or a row each
time from the search and moving accordingly.
Solution less than O(n) is desirable!
--
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: search a 2d sorted array in less than O(n)
Well, friend, we're both wrong. The algorithm will find 6 just fine. It will choose 3 as the middle element. Since 6 is bigger, it will throw away the subarray 1 2 2 3 and check the other 3 subarrays. When it checks 6 7 7 8 It will find the 6 on the first try. I just verified this by running the code. Second, I should have solved the recurrence. You're right that it's ~ n^1.6 . Throwing away a quarter of the _elements_ isn't good enough because that number is n^2. The algorithm is only sublinear in the number of elements, which of course is worse than the standard algorithm that starts at the lower left corner and steps along a jagged path of max length ~2n. But I should have seen that you can split the L-shaped remaining piece of each subarray into only TWO pieces rather than 3. So the recursive calls should have been: return (x a[mi][mj]) ? search(a, x, i0, mi - 1, j0, j1, i, j) || search(a, x, mi, i1, j0, mj - 1, i, j) : search(a, x, i0, mi, mj + 1, j1, i, j) || search(a, x, mi + 1, i1, j0, j1, i, j); With this change the recurrence is more complicated, but it should be faster than n^1.6 . I'm not going to try it tonight... On Sep 27, 8:19 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: @saurabh.nsit: Consider the following array: 1 2 6 7 2 3 7 8 4 5 8 9 5 7 9 10 And the item to be searched is 6. As I understand it, using your approach you will search 6 in only the second and third row, which will not give the correct solution. Hope this clears a few doubts. @Gene: Analysing the complexity of ur algo: T(n) = 3*T(n/2) + O(1) which is n^(log_2(3)) = n^1.6. Cheers Nikhil Jindal On Sun, Sep 26, 2010 at 11:14 PM, saurabh singh saurabh.n...@gmail.comwrote: As you mentioned ultimately element to be searched should either be in row 'i' (ahead of [i,i] element) or in row i+1 (before [i+1,i+1] element). Since each row contain numbers in sorted order so u can do binary search on these two rows and ultimately the complexity will be O(logn) only On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh saurabh.n...@gmail.comwrote: solution 1: use concept of quad-tree and do binary search in that tree solution 2: do binary search on major diagonal. ultimately u will narrow down to search for element in 2 rows. in these two rows again do binary search. How do you narrow down to two rows? Please explain. By searching on the diagonal, you get two elements such that one is lesser than the number being searched for and the next is greater. let them be i,i, and i+1,i+1. So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But the number could be anywhere in the rest of the array any solution will lead you to O(log(n)) time On Tue, Sep 21, 2010 at 5:10 PM, jagadish jagadish1...@gmail.comwrote: Hi all, Given a 2d array which is sorted row wise and column wise as well, find a specific element in it in LESS THAN O(n). PS: an O(n) solution would involve skipping a column or a row each time from the search and moving accordingly. Solution less than O(n) is desirable! -- 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. -- Thanks Regards, Saurabh -- 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. Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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 algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- 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,
[algogeeks] Re: search a 2d sorted array in less than O(n)
If the array is m by n, pick the element a[m/2][n/2], i.e. the one in
the middle. There are now 3 possibilities:
1) The middle element is the one you're looking for, so you're done.
2) The element you're looking for is smaller. In this case you can
throw out about 1/4 of the array: everything right and downward from
a[m/2][n/2] (including row m/2 and column n/2) because these elements
are all larger than the middle one.
3) The element you're looking for is larger. In this case you can
again throw out about 1/4 of the array: everything left and upward
from a[m/2][n/2] inclusive.
Then you can search the remaining 3/4 of the array recursively.
By throwing away 1/4 of mn elements at each step, you can easily work
out the recurrence to see you'll get O(log mn) = O(log(max(m, n)))
performance.
Here is code and a very quick unit test:
#include stdio.h
#include stdlib.h
typedef int SORTED_ARRAY[100][100];
/* Look for x in row- and column-sorted a[i0..i1][j0..j1].
Put indices in *i and *j and return 1 if found,
else return 0.
*/
int search(SORTED_ARRAY a, int x,
int i0, int i1,
int j0, int j1,
int *i, int *j)
{
if (i0 = i1 j0 = j1) {
int mi = (i0 + i1) / 2;
int mj = (j0 + j1) / 2;
if (x == a[mi][mj]) {
*i = mi; *j = mj;
return 1;
}
return (x a[mi][mj]) ?
search(a, x, i0, mi - 1, j0, mj - 1, i, j) ||
search(a, x, i0, mi - 1, mj, j1, i, j) ||
search(a, x, mi, i1, j0, mj - 1, i, j)
:
search(a, x, mi + 1, i1, mj + 1, j1, i, j) ||
search(a, x, i0, mi, mj + 1, j1, i, j) ||
search(a, x, mi + 1, i1, j0, mj, i, j);
}
return 0;
}
int max(int x, int y) { return x y ? x : y; }
int main(void)
{
int i, j, m, n, ri, rj;
SORTED_ARRAY a;
// A small unit test. Build a m x n
// sorted array with random differences.
m = 100; n = 100;
a[0][0] = 0;
for (i = 1; i m; i++)
a[i][0] = a[i - 1][0] + rand() % 1000;
for (j = 1; j n; j++) {
a[0][j] = a[0][j - 1] + rand() % 1000;
for (i = 1; i m; i++)
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + rand() % 1000;
}
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
printf(%8d, a[i][j]);
}
printf(\n);
}
for (i = 0; i m; i++) {
for (j = 32; j n; j++) {
int r = search(a, a[i][j], 0, m - 1, 0, n - 1, ri, rj);
if (!r) {
printf(failed at a[%d][%d]\n, i, j, a[i][j]);
return 1;
}
else if (a[ri][rj] != a[i][j]) {
printf(mistake at a[%d][%d]=%d: found a[%d][%d]=%d\n,
i, j, a[i][j], ri, rj, a[ri][rj]);
return 1;
}
}
}
printf(pass!\n);
return 0;
}
On Sep 21, 7:40 am, jagadish jagadish1...@gmail.com wrote:
Hi all,
Given a 2d array which is sorted row wise and column wise as well,
find a specific element in it in LESS THAN O(n).
PS: an O(n) solution would involve skipping a column or a row each
time from the search and moving accordingly.
Solution less than O(n) is desirable!
--
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] Ternary Search Trees
Hi , I was reading TST from this http://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/technical_artile/ternary_search_tree/terstree.htm But I could not understand its two applications i.e the nearest neighbourhood search and Pattern Matching Search... If anyone of you know about it please let me know...and if there are any good tutorials then plz give the links... -- 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]Numbers search in an array
take one pointer to start n another to the end say a n b now if a +b X shift b towards left n so on On Fri, Jun 18, 2010 at 9:03 AM, sharad kumar aryansmit3...@gmail.comwrote: @arun:find out the difference x-arr[i] for all i=0..n hash it ...next search for a number with difference .u can get it in O(n) On Fri, Jun 18, 2010 at 8:05 AM, Arunkumar Sreenivasan thegame.a...@gmail.com wrote: Hi, You are given a set of numbers and another number 'x'. You have to find if there exists any two numbers, whose sum is equal to 'x'. I have done this is o(n)log n. Need a more optimized solution. regards, Arun kumar S -- 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. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. -- Thanking You Ashish Mishra -- 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]Numbers search in an array
Hi, You are given a set of numbers and another number 'x'. You have to find if there exists any two numbers, whose sum is equal to 'x'. I have done this is o(n)log n. Need a more optimized solution. regards, Arun kumar S -- 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]Numbers search in an array
Its a repeated question. I would suggest you checking the archives of this groups for its solution. Anurag Sharma On Fri, Jun 18, 2010 at 8:05 AM, Arunkumar Sreenivasan thegame.a...@gmail.com wrote: Hi, You are given a set of numbers and another number 'x'. You have to find if there exists any two numbers, whose sum is equal to 'x'. I have done this is o(n)log n. Need a more optimized solution. regards, Arun kumar S -- 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: Search in a sorted NxN matrix
Not a bad start, it can eliminate areas. n n n n ?? ?? ?? ?? n n n n ?? ?? ?? ?? n n n n ?? ?? ?? ?? n n n n ?? ?? ?? ?? ?? ?? ?? ?? n n n n ?? ?? ?? ?? n n n n ?? ?? ?? ?? n n n n So it would involve searching in the two remaing blocks, recursively until you get an 1xN or Mx1 then a binary search on the row or column. -- Geoff On Nov 25, 3:46 am, Bharath bharath1...@gmail.com wrote: You can actually do it in O(logn) complexity. Binary Search on diagonal and then on a row. On Tue, Nov 24, 2009 at 10:33 PM, chitta koushik koushik.infin...@gmail.com wrote: Start from top right or bottom left corner and move according if the element to be searched is lesser or greater than current. --Koushik C Pablo Picassohttp://www.brainyquote.com/quotes/authors/p/pablo_picasso.html - Computers are useless. They can only give you answers. On Tue, Nov 24, 2009 at 7:27 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: A nice problem that i encountered : In O(n) search for a value x in a sorted NxN matrix. Definition of sorted matrix: All rows and all columns are sorted in ascending order. So thought of sharing .. Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Bharath- 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 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: Search in a sorted NxN matrix
Hmmm. Same idea, much more analysis. I feel good, I spent a lot less time thinking about it. Splitting the search areas into squares is a great idea. -- Geoff On Nov 25, 8:43 am, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: A research article on this question.. Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay sdarticle.pdf 964KViewDownload -- 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] Binairy Search Algoritm
while(a.[mid].equals('city1') a[mid+1].equals('city2') ){
mid = low+high/2;
if(a[mid]=='city1' a[mid+1]=='city1')
low=mid;
else if (a[mid]=='city2' a[mid+1]=='city2')
high=mid;
}
On Thu, Nov 12, 2009 at 3:39 PM, Dennis tyra...@gmail.com wrote:
Hello, here's the deal...
I have an ordered array containing 'Person' objects. The array is
ordered by the city the person lives in.
My array contains people from 2 different cities.
Now i need to find the highest index of the first city in the array
using a binairy search algoritm, i have had several tries but i can't
seem to figure it out, so i was hoping some of you could help me
out...
The programming language is Java, but i guess that doesn't realy
matter much.
Thanks in advance,
Dennis
--
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=.
--
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=.
[algogeeks] Re: search your friend
Wouldn't it be better to replace step 5 with Travel 2^(n+1) distance on the fourth road. If you find your friend DONE else return back to the crossing ? After you have exhausted the first three roads to a distance 2^n, there is no point to going only 2^n on the fourth road and then returning to the crossing so that you go 2^(n+1) on the first road. You can save 2^(n+1) by continuing down the fourth road for an additional 2^n before turning around. Dave On Oct 9, 9:56 am, anilkumarmyla anilkumarm...@gmail.com wrote: This is a simple extension of finding a friend on a single road without knowing his position. 1) n=0 2) Travel 2^n distance on the first road. If you find your friend DONE else return back to the crossing 3) Travel 2^n distance on the second road. If you find your friend DONE else return back to the crossing 4) Travel 2^n distance on the third road. If you find your friend DONE else return back to the crossing 5) Travel 2^n distance on the fourth road. If you find your friend DONE else return back to the crossing 6) n = n+1 GOTO STEP 2 Lets analyze the algo Assume d can be written as 2^a for some a ( can be extended to cases when d is not the form of 2^a) Assume the worst case of your friend being in the fourth road. Then the total distance travelled by you till you find your friend is = 4 * 2 * ( 2^0 + 2^1 + 2^2 + ... + 2^a) // The factor of 2 at the beginning is for your returning back = 8 * (2^a+1 - 1) = 8 * (2d-1) which is O(d) --~--~-~--~~~---~--~~ 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: search your friend
Anyway the solution is O(d) [:)] which is asked to be proved. --~--~-~--~~~---~--~~ 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: search your friend
yes anil your approach is rite.. --~--~-~--~~~---~--~~ 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] Element search in a matrix
Given a matrix all whose columns and rows are individually sorted, how do you search a number in it? --~--~-~--~~~---~--~~ 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] prority search tree
Hi i want to construct a priority search tree but i don't know the algorithm for construct and implement it can anyone help me please? --~--~-~--~~~---~--~~ 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-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
