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

learn more… | top users | synonyms

0
votes
1answer
44 views
1
vote
1answer
148 views

Finding all soldier wins

Consider the following game (see also this question): 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 ...
2
votes
2answers
90 views

Finding perfect matchings with as few database queries as possible

I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows: There are an equal number of men and women. Each man has a perfect ...
12
votes
2answers
236 views

Is there any study or theory behind combining binary search and interpolation search?

I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files ...
1
vote
2answers
49 views

How is the oracle function for Grover's Search algorithm obtained?

I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ ...
11
votes
2answers
2k views

Can this algorithm still be considered a Binary Search algorithm?

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as ...
1
vote
1answer
24 views

Taking intersection in large search

As I understand, you can build the the word -> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once ...
1
vote
1answer
38 views

What type of an algorithm is being used for directory structure scanning?

So after learning about DFS and BFS yesterday in my class I was curious as to how is scanning on various file system being done. I spent quite a bit of time trying to look for some references on the ...
0
votes
1answer
45 views

An efficient algorithm to find a shortest cycle including a speciic vertex

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$. We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle. This ...
0
votes
0answers
64 views

Misionnaries and cannibals problem (A* algorithm)

"In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if ...
1
vote
1answer
67 views

Bidirectional Dijkstra vs Dijkstra

Are there any kind of graphs where Bidirectional Dijkstra would expand more than Dijkstra? I tried to come up with an argument like this: Let node $n$ be expanded by Bidirectional Dijkstra. Now ...
0
votes
1answer
44 views

Hill Climbing Search - 8 queens [closed]

In that picture, I am having trouble counting why there are 17 pairs of queens. I can only count 14. I counted 10 diagonal pairs and 5 horizontal pairs. Can someone please elaborate on this? I am not ...
1
vote
0answers
47 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
2answers
53 views

Symmetry in Pattern Databases

I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the ...
0
votes
1answer
79 views

Find cell neighbors of a given edge in a 2D grid [closed]

In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, ...
2
votes
1answer
50 views

Hill Climbing Search

With the hill-climbing search algorithm, I do not quite understand how the algorithm can get stuck at "plateaus/ridges." Moving one step back, what exactly denotes a "maximum" or "minimum" in a ...
1
vote
0answers
34 views

Good language for introduction to self-modifying algorithms? [closed]

So I am trying to find a language with which i can write code to build/search through deductive reasoning 'nets', as well as self-modify it's search algorithms based on information learned from these ...
3
votes
0answers
40 views

Heuristic for Rubik's cube [closed]

I am trying to understand Pattern Databases for designing heuristics. I am reading Richard E. Korf's book Heuristic Search. One of its paragraphs says The obvious heuristic for Rubik's Cube is a ...
4
votes
1answer
71 views

Find maximum in array without comparisons between elements

Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$. The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions: ...
-2
votes
1answer
37 views

Best search in Heap Array

Can someone give me the best search algorithm in a max heap? In particular simply implemented as an array. I knew it has complexity of $O(N)$ but it can be done better. For example, if $A[i] < \...
1
vote
2answers
47 views

How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the ...
1
vote
1answer
76 views

Search Heuristics Where the Search Space Has No Gradient

If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the ...
6
votes
2answers
47 views

A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
3
votes
1answer
45 views

3SUM problem solution on the basis of cubic function and a line?

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S. I am trying to understand mathematical solution of the 3SUM problem based on a polynomial ...
2
votes
0answers
38 views

How does the Monte Carlo Tree Search Algorithm Decide When to Expand?

I understand that the MCTS algorithm expands its tree after it has selected the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse ...
0
votes
1answer
30 views

Why to implement Open list in Heuristic search with priority queue

I don't understand why do we need to implement Open list using priority queue? There could be other data structure. I understand the usage of priority queues from this example clearly. The newly ...
3
votes
1answer
138 views

Proof of correctness of A star search algorithm

I've been looking for the proof of correctness for the A star (A*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A* algorithm. I'm ...
0
votes
1answer
44 views

A problem solved by weighted median

Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily in ...
1
vote
1answer
70 views

How do multiple branches from one node occur with the Monte Carlo Tree Search?

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (...
3
votes
2answers
125 views

Minimax algorithm when all the options are the same

tl;dr What does the Minimax algorithm do when all its options are the same? Consider this Minimax tree: (Green means the ends, orange minimize, blue maximize) (Source: Myself) Imagine this is the ...
0
votes
1answer
43 views

Searching through all program of a stack-based language with little memory

I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output. Given a program fragment, I can ...
4
votes
3answers
166 views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
1
vote
0answers
246 views

Moving a set of points in the plane subject to constraints

I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum. Let $X$ denote the disjoint union of $n$ one-point sets. Let $f:X\...
0
votes
0answers
7 views

Insert and search algorithm [duplicate]

My problem is that I have a list of pairs (1,x_1),..(n,x_n). At some point I'll have to add a pair (k,y) to the list where k Do you have any ideas on how to do this? My friend told me his method but ...
3
votes
1answer
112 views

An online algorithm to find the Pareto frontier elements

I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements). For instance. Given the following ...
0
votes
0answers
56 views

DAG, search for cheapest descendants with same color

Let $G=(V,E)$ be a DAG. For each $v\in V$ you have a color $c(v): V \rightarrow \left\{c_1 \ldots c_k \right\}$ where $k$ is a fixed number, and a weight $p(v)$. For every $v \in V$ you have to find ...
1
vote
0answers
99 views

Finding optimal element with two criteria

Let there be a (unsymmetric, directed, weighted) graph ( $\mathbb{G}$, capacity $m$ ) and an array ( $\mathbb{A}$, fixed capacity $n$) of objects ($m>>n$). The array contains references to a ...
24
votes
2answers
1k views

How do I find my wife in a supermarket?

If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using? I think there are some ...
2
votes
1answer
69 views

Difference between heuristic-based searching and optimal path searching

I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material: I understand that with search-methods like e.g. ...
3
votes
1answer
82 views

A string that takes a DFA from any state to a given state?

EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence"). Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition ...
0
votes
0answers
15 views

Look for a pair of elements closest to two start positions in both directions until a condition is met

For a list which contains a set of elements I have two starting positions pos1and pos2 that are selected randomly. Next, I check ...
1
vote
1answer
43 views

maximum distance in between points in taxicab metrics - inserting and deleting points

Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as $$|x_2-x_1| + |y_2-y_1|$$ Initially, there are given empty set of points. I think how to find maximum ...
1
vote
1answer
72 views

Algorithm A vs Algorithm A*: What's the difference?

I can find quite a bit of literature on A* but very little on A. What is the difference between the two search algorithms?
8
votes
1answer
221 views

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates ...
2
votes
1answer
85 views

Algorithm for finding fixed cycles in bipartite graphs in sublinear time

Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K_{3,3}$ graph finding if it contains a cycle $C_4$. ...
0
votes
0answers
28 views

Optimal shortest path: When heuristic overestimates

Is it possible (or does there exists a special case) where the optimal shortest path is guaranteed even where the heuristic function always overestimates? Intentions for such a query : Trying to ...
-1
votes
1answer
48 views

How is this algorithm average case derived?

For a simple linear search on an unsorted list my textbook says the following: To determine the average case, you add the number of iterations required to find the target at each possible position ...
2
votes
0answers
1k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
2
votes
0answers
16 views

A* orientation discretization

I have a space with obstacles I wish to find a path through. What I can do is discretize the space into a grid and use A* (or D* or whatever) to find a path through it. I wish to now add orientation ...
2
votes
2answers
96 views

String matching for wildcard-based records

Let's say that we have a string "1.2.3" and want to find a match for it in the following records: 1.2.9 1.4.5 1.*.3 For each ...