New answers tagged search-algorithms
3
7 is the least number of questions that you can ask to guarantee to find the treasure.
the idea of binary search
Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search.
the binary search on ...
0
That's not entirely correct Tobi. Breadth-First search requires to store in memory only those nodes awaiting for expansion. Thus, it only requires to store in memory $b^d$ nodes in the worst case, i.e., if the solution is found at the rightmost child at depth $d$. That is the number of nodes required to be stored in memory because when the solution is found ...
2
It all depends on what hash function you are using for your strings. The worst case for Rabin-Karp would be a case in which every single substring of the text has an equal hash to the pattern, therefore every single substring would be compared and the algorithm is equivalent to brute force.
The first example would be an example of this since the pattern ...
0
Worst case for Rabin-Karp string search is hash collision, i.e when you look for "ABCD" and other string "XXXX" has the same length and hash, and then the text consists purely of 'X' chars :)
0
I came across these slides where on slide 23 another proof is given, however the idea of this proof is the same as in the slides of my original post.
But this still doesn't show, why $dist(s,v)$ and $dist(w,t)$ need to be less than $top_f$ and $top_b$ respectively.
EDIT: Note that with this proof $dist(s,v) \leq top_f$ and $dist(w,t) \leq top_b$ hold, ...
Top 50 recent answers are included
