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

learn more… | top users | synonyms

-2
votes
0answers
14 views

Alpha Beta Pruning in Special Case [on hold]

I'm so glad that ask my first question on this site. I ran into a question that so nice. it said: we have a Tree (Main Fig) and we know minimum value is 1 and maximum value is 15. in which ordering ...
2
votes
1answer
47 views

Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages? E.g. linear search problem. We have an ordered set of incomparable ...
4
votes
1answer
122 views

Finding an element in a sorted array with at most three queries to larger elements

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.) However there is a constraint. Like in a game you have 3 lives. If ...
1
vote
1answer
42 views

Can you explain this improvement to this frequency distribution algorithm?

I came across the following in a text book: Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from ...
2
votes
0answers
26 views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
1
vote
1answer
29 views

Text search by first order formula

I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates ...
3
votes
2answers
73 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
0
votes
1answer
51 views

Longest Path A*, Admissible Heuristics, and Optimalness

Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path. I have some ...
1
vote
1answer
56 views

Efficient algorithm for iterated find/replace

I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow. Specifically: I have a function, ...
6
votes
0answers
92 views

Approximate nearest neighbour in practice

I have $10^3$ vectors each of dimension $10^4$. Each dimension takes an integer from a limited range. I would like to build a data structure that will answer approximate nearest neighbour queries ...
5
votes
0answers
59 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
-2
votes
1answer
41 views

How do you return the k smallest elements of an array using Mergesort?

I'd like to create a modified mergesort algorithm to return the k smallest elements of an array. The mergesort algorithm below sorts an unordered array of size n. How do I modify the algorithm so that ...
1
vote
2answers
120 views

Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
2
votes
1answer
36 views

Why is the base used to compute hashes in Rabin–Karp always primes?

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$ where $b$ is prime (all computations ...
0
votes
2answers
76 views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
3
votes
3answers
81 views

Minimum number of tests to identify subset of modules that trigger a bug?

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired ...
1
vote
1answer
32 views

What is the algo used for Phonetic Search

I am new to the field of text mining. Could not figure out what to search on google so am here for the same help. When we talk of approximate / fuzzy string match. searching for RAT would give RAAT ...
-4
votes
1answer
35 views

Implement “from” function for AVL Tree java

I posted this same question on stackoverflow but I think it might be better suited here as I am having trouble with coming up with an algorithm with O(log(n)) running time. Question: I am ...
2
votes
1answer
54 views

What is the complexity of depth first traversal that don't label nodes as discovered?

I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before. A / \ B C \ / D | E If run ...
2
votes
0answers
36 views

Searching for multiple elements of an array

Suppose we have two sorted arrays $A$ and $B$, and we want to find the indices in $B$ of all elements of $A$. We can do this in $\mathcal O(|A|\log|B|)$ time by simply binary searching $|A|$ times. We ...
1
vote
1answer
98 views

Shortest path from starting cell to all cells in the grid

I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells. How ...
0
votes
1answer
56 views

Sorted array with odd indexed elements swapped randomly [closed]

A sorted array $\mathcal{A}$ with even number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}_1, \mathcal{A}_2$) contain equal number ...
1
vote
0answers
21 views

Grover algorithm for known number of solutions

I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
4
votes
1answer
67 views

How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
4
votes
1answer
44 views

Placing 1d items in a 2d grid with constraints

I'M looking for an algorithm (preferably polynomial) for the following problem: Input: - an M x N grid, where each square can be either empty or occupied - a list of items - a list of constraints ...
1
vote
0answers
15 views

Steps to implement PageRank Algorithm on a local set of webpages [closed]

I just completed a detailed theoretical mathematical study about the PageRank algorithm, I want to make a sample implementation to make some tests and play with it, supposing that I have a local ...
0
votes
0answers
52 views

How to populate the tabu list in tabu search?

I am trying to implement Tabu search, as shown here, for my problem. I am now stuck on how to generate the tabu list. In algorithm it mentions that if cost of the candidate is better than the best, ...
1
vote
2answers
102 views

Searching for a string of numbers in a large digit sequence [closed]

How would one search for a string of digits in a large digit sequence? For example, I'd like to search for 351814 in Euler's number. I'm not too keen on computer ...
1
vote
1answer
32 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
46 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
112 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
18 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
558 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
62 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
50 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
203 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$ ...
1
vote
1answer
68 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
1k 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
123 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
57 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
22 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 ...
6
votes
1answer
401 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
87 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
72 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
59 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
74 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
68 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
152 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
422 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, ...