Re: [algogeeks] Re: Unbounded dictionary lookup
If we take high = MAX_CAPACITY
Here MAX_CAPACITY denotes the maximum no of words dictinary can index.
Actual no of words stored in dictionary could be less than MAX_CAPACITY.
On Wed, Sep 22, 2010 at 1:23 AM, Minotauraus anike...@gmail.com wrote:
high= const.(10^const)
What's const? The point of this isn't that it's a difficult prob to
solve. Point lies in working with the design to make this close to log
n.
Define what value const holds.
On Sep 21, 9:12 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
its dictionary means shorted ordered arry.
let low = 1; and high= const.(10^const)
Boolean isWord(String word)
{ while(low = high)
{ mid = (low+ high)/2;
if(word = getWordAt(mid))
return true;
if( word getWordAt(mid))
{ high = mid-1
}
else
low = mid+1;
}
}
Its a simple Binary Search Algorithm ...
who's complexity is O(log n) times.
--
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.
--
Ramdas Kale
+919983526790
--
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: Unbounded dictionary lookup
In case of a dictionary, can we assume that its a Sorted list of
words?
On Sep 22, 12:42 pm, ramdas kale ramda...@gmail.com wrote:
If we take high = MAX_CAPACITY
Here MAX_CAPACITY denotes the maximum no of words dictinary can index.
Actual no of words stored in dictionary could be less than MAX_CAPACITY.
On Wed, Sep 22, 2010 at 1:23 AM, Minotauraus anike...@gmail.com wrote:
high= const.(10^const)
What's const? The point of this isn't that it's a difficult prob to
solve. Point lies in working with the design to make this close to log
n.
Define what value const holds.
On Sep 21, 9:12 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
its dictionary means shorted ordered arry.
let low = 1; and high= const.(10^const)
Boolean isWord(String word)
{ while(low = high)
{ mid = (low+ high)/2;
if(word = getWordAt(mid))
return true;
if( word getWordAt(mid))
{ high = mid-1
}
else
low = mid+1;
}
}
Its a simple Binary Search Algorithm ...
who's complexity is O(log n) times.
--
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.
--
Ramdas Kale
+919983526790
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Unbounded dictionary lookup
DICTIONARY means sorted order! list!!
On Wed, Sep 22, 2010 at 7:21 AM, Yellow Sapphire pukhraj7...@gmail.comwrote:
In case of a dictionary, can we assume that its a Sorted list of
words?
On Sep 22, 12:42 pm, ramdas kale ramda...@gmail.com wrote:
If we take high = MAX_CAPACITY
Here MAX_CAPACITY denotes the maximum no of words dictinary can index.
Actual no of words stored in dictionary could be less than MAX_CAPACITY.
On Wed, Sep 22, 2010 at 1:23 AM, Minotauraus anike...@gmail.com wrote:
high= const.(10^const)
What's const? The point of this isn't that it's a difficult prob to
solve. Point lies in working with the design to make this close to log
n.
Define what value const holds.
On Sep 21, 9:12 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
its dictionary means shorted ordered arry.
let low = 1; and high= const.(10^const)
Boolean isWord(String word)
{ while(low = high)
{ mid = (low+ high)/2;
if(word = getWordAt(mid))
return true;
if( word getWordAt(mid))
{ high = mid-1
}
else
low = mid+1;
}
}
Its a simple Binary Search Algorithm ...
who's complexity is O(log n) times.
--
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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ramdas Kale
+919983526790
--
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: Unbounded dictionary lookup
we can approach it like
*lets start with index 0
if (found) return index
else
index += INCR_;
*we will try to increment with INCR_ until one of the following
conditions met
index goes out of bounds
found the words which must come after the value eg meet should
occur prior to must
found the word itself
*after above we will get some range to be searched for and we can
apply linear or binary search to find the string
the analysis will depend on the INCR_ and n values
hence worst case complexity will be
gertWordAt complexity multiplied by
O(log INCR_ ) binary search after range selection
O(n/INCR_) searchinh for finding the correct range
Now you might want to have some logic to determine correct INCR_ value
if your dictionary is really changing at high frequency ;)
On Sep 22, 12:53 am, Minotauraus anike...@gmail.com wrote:
high= const.(10^const)
What's const? The point of this isn't that it's a difficult prob to
solve. Point lies in working with the design to make this close to log
n.
Define what value const holds.
On Sep 21, 9:12 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
its dictionary means shorted ordered arry.
let low = 1; and high= const.(10^const)
Boolean isWord(String word)
{ while(low = high)
{ mid = (low+ high)/2;
if(word = getWordAt(mid))
return true;
if( word getWordAt(mid))
{ high = mid-1
}
else
low = mid+1;
}
}
Its a simple Binary Search Algorithm ...
who's complexity is O(log n) times.- 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: Unbounded dictionary lookup
high= const.(10^const)
What's const? The point of this isn't that it's a difficult prob to
solve. Point lies in working with the design to make this close to log
n.
Define what value const holds.
On Sep 21, 9:12 am, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
its dictionary means shorted ordered arry.
let low = 1; and high= const.(10^const)
Boolean isWord(String word)
{ while(low = high)
{ mid = (low+ high)/2;
if(word = getWordAt(mid))
return true;
if( word getWordAt(mid))
{ high = mid-1
}
else
low = mid+1;
}
}
Its a simple Binary Search Algorithm ...
who's complexity is O(log n) times.
--
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.
