# Tagged Questions

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

75 views

### Finding a match in two collections

Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a < b = card(B)$. Both collections are sorted in ascending order. There is at ...
21 views

If $h_1, h_2$ and $h_3$ are given as admissible functions, is $h_4$ admissible given that, $h_4 = h_1+h_2+h_3$ ? All I know is that if $h$ is admissible, $h(n) \leq h^*(n)$ where $h^*(n)$ is the ...
79 views

### Given a directed graph and a vertex v, find all cycles that go through v? [duplicate]

Given a set of uniquely numbered items that each has three attributes id, from and two in ...
56 views

### Search String Algorithm in Table

For a given database table: ...
225 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 ...
92 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 ...
251 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 ...
70 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)$ ...
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 ...
26 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 ...
40 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 ...
48 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 ...
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 ...
80 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 ...
45 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 ...
54 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 ...
55 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 ...
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, ...
54 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 ...
35 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 ...
49 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 ...
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: ...
37 views

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 ...
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 ...
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 ...
100 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 ...
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 ...
76 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. ...
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 ...
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 ...
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 ...
75 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?
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 ...
87 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$. ...