Algorithms for finding an element in some specified data-structure (most commonly, in a tree).
1
vote
1answer
29 views
Approximate time for selection operation using index when equality is on nonkey
In database query processing, the approximate time for selection operation using primary index when equality is on key is $2(b_s + b_t)$ where $b_s$ is disk seek time and $b_t$ is disk transfer time ...
1
vote
1answer
35 views
Finding the element that occurs more often than the other
I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.
Example : $aaaaaabbb$
Here ...
2
votes
1answer
51 views
Comparing variations of A*
I am running some experiments with a maze, and trying different variations of A*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better ...
0
votes
0answers
13 views
Multi-Criteria Vehicule Routing Problem Using Dijkstra [closed]
Say that we're having a Network defined by edges and nodes. The $(i,j)$ edges is defined by the pair $(cost(i,j),weight(i,j))$ where $risk=\sum_{(i,j)\in \space same\space pathway \space from \space ...
1
vote
1answer
50 views
Are genetic algorithms special instances of random search done in an unexpectedly short run-time? [closed]
I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?
Ever since I finished my ...
5
votes
1answer
91 views
All paths of less than a given length in a directed graph between couple of nodes
Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, ...
1
vote
1answer
39 views
While proving optimality of the A* algorithm, why can we change graphs?
In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105.
However, I cannot ...
3
votes
3answers
182 views
Find a vertex that is equidistant to a set of vertices?
I need help with the following problem:
Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.
Question:
Find a vertex $v$ of $V$ such that the distance ...
3
votes
1answer
49 views
Difference between pattern matching and pattern searching in terms of DFA/Regex
E.g.
Matching Problem The DFA of regex good is like a chain.
...
0
votes
0answers
21 views
Is this alphabeta search code correct? [closed]
This code was adapted from this alphabeta pseudocode. AlphaBeta search is often mentioned but the complete code is never presented.
IGame is an interface with two methods:
getScore() - evaluates the ...
1
vote
1answer
40 views
iterative lengthening search example
I am looking for an example of the "iterative lengthening search". I have searched and I was only able to find definitions like
iterative lengthening search an iterative analog to uniform cost
...
4
votes
2answers
61 views
Local Search vs Classical Search
I have some questions regarding local search / optimization as explained in chapter 4 of the book : http://aima.cs.berkeley.edu/
In classical search (Chap 3), the search starts from an initial node, ...
3
votes
1answer
102 views
Time Complexity of Rabin-Karp matching algorithm
I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..
After reading few para of the section on ...
0
votes
1answer
56 views
How do we find the optimal modulus q in Rabin-Karp algorithm?
I asked a similar question here on Rabin Karp algorithm. My present question is, how do we find the best $q$ (i.e modulus)? What is the criterion? We need to choose a $q$ which will be quick to ...
1
vote
0answers
47 views
Problem with Cormen's treatment of the Rabin-Karp algorithm
I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. ...
1
vote
2answers
39 views
A* optimality of the expanded node
Suppose I have a admissible and consistent heuristic.
Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?
Look at this pseudocode from wikipedia:
...
4
votes
1answer
65 views
Why can the state space of the 15 puzzle be divided into two separate parts?
I am trying to understand the proof here of why the state space in 15 puzzle is divided into two separate parts, but the explanation is complicated for me.
Could someone please explain it in simpler ...
2
votes
1answer
63 views
What is Harrison hashing, its applications in web search engines?
What is Harrison hashing and what are its applications in web searching?
Can some one give me some relevant information?
Update:
I found it here , and is a part of M.Tech syllabus of a friend ...
2
votes
1answer
79 views
Is search a binary heap operation?
According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right).
Why not? Binary heaps may not be sorted, but they are ordered, and a full graph ...
1
vote
1answer
42 views
Using tree search
I have some questions regarding tree search and graph search (Uninformed search) as explained in chapter 3 of the book : http://aima.cs.berkeley.edu/
As I see, the only difference between the two is ...
2
votes
1answer
50 views
Finding a '1' cell with a '0' to its right in a binary array
Given an array of size n that holds ones and zeros I need to find an index of a 1 cell that has 0 to his right (in then next ...
1
vote
3answers
93 views
The purpose of grey node in graph depth-first search
In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex ...
1
vote
1answer
68 views
Dfs algorithm and cycles question
Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?
Looks to me likes its true ,is it?
4
votes
2answers
104 views
Uniform-cost Search Problem
Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?
Definitions: ...
2
votes
1answer
38 views
How to rank search results of short string lists
I have a tree of foods, which I'd like to search to find relevant nodes. What's the best way to rank the results?
Here's an example sub-set after a search for "apple":
...
0
votes
0answers
22 views
Struct Memory Management [closed]
I'm currently working on an implementation to solve a wooden puzzle in which blocks of varying sizes can be slid around to create a "winning" configuration. I'm using breadth first search as each ...
7
votes
1answer
176 views
Directed union-find
Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries.
Example: disjoint-set forest
Consider the following set of queries:
...
4
votes
1answer
162 views
Smallest string length to contain all types of beads
I read this question somewhere, and could not come up with an efficient answer.
A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ ...
0
votes
1answer
122 views
Breadth First Search with cost
Looking for some tutorials / references that discuss Breadth First Search that takes into consideration the cost of paths, but could not find much information.
Could someone refer a tutorial?
2
votes
0answers
51 views
What limits the implementation of proximity operators for text indexing and searching?
I was asking on academia.se, if anyone knows scientific search engines offering a proximity operator like Google Web Search does, while Google Scholar Search does not. That's sad, because this ...
