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

learn more… | top users | synonyms

1
vote
1answer
22 views

Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. ...
1
vote
0answers
34 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
2
votes
3answers
79 views

How is A* search superior to Dijkstra's algorithm

Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm. How is it ...
0
votes
0answers
15 views

TF-IDF query engine in context of terms weight

I'm looking for public algorithm which gives the engine these abilities: Query by ranked terms Limit outcome by date/time range Basically, i'd like to concentrate articles (generally ...
3
votes
1answer
471 views

Best solutions to 6 degrees of separation

From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check ...
0
votes
1answer
52 views

Optimality of A*

I read in the artificial-intelligence book of Russel and Norvig that The tree-search version of A* is optimal if heuristic function is admissible, while the graph-search version is optimal if ...
0
votes
0answers
41 views

Algorithm for storing polygon edges into grid

Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is? Grid has fixed dimensions and number of cells. Grid is represented by ...
0
votes
0answers
19 views

Uniform Binary Search explanation and lookup table [duplicate]

Please can anyone explain me the worst ,average and best case running time for the Unifrom binary search .. Also how can the lookup table be explained?
4
votes
2answers
187 views

Expected number of updates of minimum

I came across the following problem in a exam. We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ ...
0
votes
1answer
35 views

Are algorithms for searching text vs searching numbers fundamentally different?

I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially. I save a draft in gmail with the content ...
5
votes
1answer
140 views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from ...
6
votes
1answer
113 views

Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
3
votes
4answers
53 views

Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
1
vote
1answer
17 views

Doubt in the correctness of decision tree models for constructing a lower bound

If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$. But with the decision tree model, the number of leafs is ...
5
votes
1answer
191 views

Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors

We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers. The algorithm was: Given an array A of length n: ...
2
votes
1answer
49 views

Time complexity of proximity search in distance matrix

I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same ...
12
votes
2answers
41 views

What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?

Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands ...
1
vote
1answer
34 views

lexicographic depth-first search complexity class

It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be ...
2
votes
1answer
63 views

Find all neighbors at a certain distance, in 3 dimensions

I have two algorithms which I would like to implement: First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, ...
2
votes
1answer
46 views

Why is the PageRank vector also the eigenvector of the web adjacency matrix?

From wikipedia: The PageRank values are the entries of the dominant eigenvector of the modified adjacency matrix. This makes PageRank a particularly elegant metric Can anyone please ...
2
votes
1answer
143 views

Solving AlienTiles with an A* heuristic

Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far. In AlienTiles you have a board with $N ...
1
vote
1answer
218 views

Data Structure For Closest Pair Problem

Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations search, insert, ...
1
vote
1answer
55 views

Efficient Median Algorithm With Very Constrained Operators

What is the most efficient algorithm for finding the median of an array when the available operations are limited to Max(), Min(), Multiply, Add, and no conditionals are allowed. Pivots and sorts are ...
1
vote
2answers
73 views

Decomposing the search problem into several small problems

I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either: Searching through the original graph. or By decomposing it into several ...
5
votes
2answers
241 views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a ...
0
votes
0answers
27 views

Search problems that can also be solved by junction trees and searching cliques

Assume having a graph $G_{variables}=(V,U)$ where $V=\{v_1,v_2,…,v_n\}$ is a set of variables; each variable $v_i\in V$ is associated with a set of possible values (it's domain) $dom(v_i)$. Let $P$ ...
1
vote
1answer
39 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
3
votes
1answer
107 views

Clarification on Tabu Search

I need some help in understanding the 'Tabu Search' Algorithm. (Wikipedia) I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding. ...
4
votes
0answers
168 views

Algorithm : Median of a dynamic array

This question is inspired by this SPOJ problem. That problem asks median of the final array, that can be done in $O(k+n)$, where k is the number of update queries and n is the size of the array. The ...
2
votes
1answer
30 views

finding a an object with constant velocity on an infinite grid in discrete time steps

Assume you have an object moving at a constant velocity(up, down, left, right) in a grid. You have unlimited resources (memory, time). At any given time step in the grid, you can "guess" the location ...
2
votes
2answers
145 views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
1
vote
1answer
91 views

Range majority queries - most freqent element in range

Given N numbers and M range queries (starting and ending points), I need to compute majority (most frequent element, if it exists) in these ranges. I'm looking for an algorithm that would answer ...
2
votes
1answer
43 views

clarification in tf-idf formula

According to the wiki-article, http://en.wikipedia.org/wiki/Tf%E2%80%93idf the term frequency of term $t$ in document $d$ is given as follows: $$ tf(t,d) = 0.5 + \frac{0.5 \times ...
1
vote
1answer
259 views

Why is Iterative-deepening A* optimal, even without monotonicity?

Why is it that Iterative-deepening A* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?
1
vote
1answer
85 views

Any path detecting between A to B

In my world there are nodes and lines, I want to see if there is any path between node A, and node B, that do not cross any line(including the lines of the path itself) and do not go thru the same ...
-1
votes
2answers
722 views

How does an admissible heuristic ensure an optimal solution?

When using A* or any other best path finding algorithm we say that the heuristic used should be admissible i.e. it should never overestimate the actual solution path (moves). Can someone tell me how ...
3
votes
2answers
39 views

Drawbacks of repeating a single pattern matching procedure for many patterns

One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern. There must be some drawbacks in this approach, given the variety ...
1
vote
1answer
18 views

Immediate positions algorithm?

Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?. Given a set $X$ and $z$ not in $X$, indicate ...
1
vote
1answer
33 views

Recover the path to a goal state in A* search algorithm

In the A* search algorithm, we use a priority queue with heuristic function to find optimum result with minimum cost. But, how do we get the path after reaching goal?
1
vote
1answer
94 views

Count elements of a sorted matrix that fall into a given interval

I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$. Each row and each column of M is sorted in the increasing order. I would like to know if there is way I can count the ...
4
votes
1answer
1k views

Find all intervals that overlap with a given interval

Note: I moved this question from stackoverflow.com I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$: I have given a table $T$ of $n$ elements where ...
2
votes
1answer
102 views

Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
3
votes
1answer
144 views

Searching a value in a “piecewise” ordered array

If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have ...
4
votes
3answers
979 views

What is the difference between exhaustive search & combinatorial search?

I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper! What is the difference between exhaustive search & combinatorial search ?
2
votes
1answer
217 views

Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$? [duplicate]

The problem is from CLRS 9.3-1: In the algorithm SELECT, the input elements are divided into groups of $5$. Argue that ...
2
votes
3answers
282 views

Runtime of searching for a number in an array?

Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire ...
2
votes
2answers
1k views

Time complexity of a backtrack algorithm

I've developed the following backtrack algorithm, and I'm trying to find out it time complexity. A set of $K$ integers defines a set of modular distances between all pairs of them. In this algorithm, ...
1
vote
1answer
53 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
1
vote
1answer
98 views

How to perform alphabetically ordered DFS?

I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. ...
3
votes
1answer
92 views

How approximate are “approximate” nearest neighbor (ANN) search algorithms?

Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are. If I have a (more or less) randomly distributed point ...