Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

learn more… | top users | synonyms

2
votes
1answer
77 views

Do we want largest or smallest priority in the A* algorithm?

On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way The A* algorithm is a problem-solving process where we put the start configuration on the priority ...
0
votes
1answer
36 views

Comparison between IDA* and Recursive best first search

How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity? Both algorithms are intended to be memory-efficient heuristic ...
2
votes
2answers
97 views

Find the number of values between i & j(given as input) in an unsorted array in O(1) time

Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement ...
6
votes
2answers
453 views

Compression type that can be searched

Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
4
votes
1answer
76 views

What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
3
votes
1answer
271 views

Is there a more efficient algorithm than backtracking/dynamic programming?

Consider the following game: One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the first day each ...
0
votes
1answer
25 views

Heuristic function

Is there any way to prove that an admissible heuristic may not be consistent? Most proof I came across are through examples .Is there a generalized proof?
0
votes
1answer
48 views

Karloff's algorithm applied to sparse graphs

I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph. Karloff [1, p.6] has given a map-reduce algorithm called ...
2
votes
2answers
57 views

Finding a segment which has equal number of segments before and after it

I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self: Given a set of n segments $[a_i ,b_i]$ where $i=1,..,n$ and $a_i < b_i$. write an ...
6
votes
1answer
397 views

Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking ...
2
votes
0answers
53 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
13
votes
4answers
510 views

Finding a pair of non-overlapping bit vectors

I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists. For example, if I give you ...
4
votes
1answer
118 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
2
votes
3answers
104 views

Algorithm for finding all the combinations on a boolean array

I have to design an algorithm to do the next task: I have one array of booleans. For example: Array: [0 1 0 0 1 0 1 1] I want to obtain all the existing combinations of 1's, having in mind that ...
1
vote
1answer
32 views

Select the n closest nodes from a starting node in a weighted directed graph

I need to select a given number of nodes from a weighted directed graph such that the nodes selected are the closest to a given starting node. This seems like a common problem to need to solve, but I ...
0
votes
1answer
56 views

Binary tree node value maximization

Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be ...
0
votes
1answer
34 views

Order a list of edges to make the the complexity of searching for an edge O(lg E)

I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related ...
1
vote
0answers
51 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
2
votes
0answers
20 views

Why can't fractional cascading be used on two unrelated arrays?

According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data. The specific question: A fellow student wants to compactly store ...
5
votes
1answer
45 views

Hamiltonian circuit for a family of graphs

For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$. Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$. For ...
3
votes
1answer
142 views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
3
votes
1answer
50 views

Minimum Length Hamiltonian Path Pair in O(n^2) or better

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to ...
0
votes
0answers
93 views

How to apply Alpha-Beta pruning to a game tree? (Algorithms Theory)

I'm studying for an AI exam, and having trouble working out this question on Alpha Beta pruning. I can answer on the effectiveness of the pruning method and the rules involved in the pruning process, ...
2
votes
1answer
50 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
1
vote
1answer
30 views

An n-dimensional index where the search key specifies an exact match on certain dimensions?

I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value ...
0
votes
0answers
14 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
1
vote
0answers
92 views

How can I learn Sunday's string searching algorithm?

How does Sunday's string searching algorithm work? I am highly unskilled in processing mathematical lingo, so I would appreciate a use case/example. A link would be ok. I tried searching the first 6 ...
9
votes
2answers
636 views

What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
0
votes
0answers
121 views

Iterative lengthening search: iterative version of Uniform Cost Search or DFS?

Actually my question has two parts: 1) I wanted to know that whether Iterative Lengthening Search is used in combination with DFS or Uniform Cost Search? Actually, in Russell and Norvig book (on page ...
4
votes
1answer
113 views

Finding all circuits that contain a given edge

Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that ...
0
votes
1answer
74 views

Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators

Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that ...
0
votes
0answers
79 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
5
votes
1answer
303 views

What is the name for this search algorithm?

A colleague came up with the following search algorithm: We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$] We are looking for the index of $i_k$ (for simplicity ...
3
votes
2answers
77 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
1
vote
2answers
176 views

How to find the Branch factor of 8 Puzzle

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that: Suppose,for example we wish to establish the ...
-1
votes
1answer
28 views

Is it possible to make excluded search with for loop in Java? [closed]

I am trying to calculate all pure strategy Nash equilibrium in a mxn game. It requires to check all pure strategy pairs (m.n pairs). Suppose player 1 has m strategies. Algorithm should start with the ...
1
vote
0answers
37 views

Given an algorithm, what are the probabilities for its run-time cases?

I am given this algorithm And I am also given the fact that $1 \leq k \leq n$. If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
2
votes
0answers
39 views

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their ...
0
votes
0answers
5 views

Detecting junctions algorithmically

With route finding algorithms, we get the children of each node. So for example, an A* search on google maps at each point in the search would know which roads can be the successor to the current ...
0
votes
1answer
80 views

Heuristic for sokoban puzzle problem

I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast. My heuristic is to consider ...
0
votes
3answers
50 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
1
vote
3answers
123 views

Fastest possible way to check what of X is in a string

I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings. example: I have the matches "dog", "cat" "apple" and the ...
0
votes
1answer
87 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
0
votes
0answers
36 views

Finding and Grouping like children

I'm working on a dependency managemen solution for a JavaScript. I'm trying to find the best pattern for grouping similar items in a graph into their own 'modules'. Given a dependency tree like ...
1
vote
0answers
47 views

Formulating an arrangement problem with STRIPS

The problem is rearranging furniture in a flat. We are given rectangular rooms of natural width and height with doors between them, (the walls have no width) and rectangular furniture at starting ...
1
vote
1answer
115 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
0
votes
1answer
77 views

Given two heuristic values how do I tell which one is admissible?

I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes. Am I correct in thinking the way to see which one is admissible is add up all the values of ...
1
vote
2answers
453 views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
3
votes
1answer
105 views

Efficient algorithm to find vertex with paths to every other vertex

$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other ...
0
votes
2answers
72 views

Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

Why is it the lower the h(n) cost the more nodes need to be expanded in A*? As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html If h(n) is always lower than (or ...