# Questions tagged [searching]

For questions about various search algorithms.

125 questions
Filter by
Sorted by
Tagged with
35 views

### Finding an optimal solution in a tile painting game

images are posted as links because I don't have enough points, sorry The Problem Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal ...
9 views

### Is discrete quasiconvexity just as good as discrete convexity?

(I will frame the discussion below in terms of concavity because it suits the examples I have on hand, but the same arguments apply to convexity, too.) Consider a function $p(h)$ defined for $h$ on a ...
34 views

### What are some real life examples of UCS (Uniform Cost Search)

Studying search algorithms I've been fascinated by UCS and its similarity to the Djikstra algorithm in some cases. Has anyone any real life example of a possible use of this UCS algorithm to solve ...
47 views

### All possible triangles in terms of edges in RCCP

NB: This question was first posted in Stack Overflow, it has been moved here on suggestion. I'm stuck on finding an efficient algorithm to the following problem: Given a complete undirected graph G ...
71 views

### How can I generate a pruning table for tetrads?

I'm currently creating a Rubik's Cube Solver and am having some difficulty generating pruning tables. Pruning tables contain information that is used to prune search tree branches, exponentially ...
118 views

### Graph puzzles: Constructing graphs from tiles

There is a vast literature on the reconstruction conjecture which says that two graphs with the same deck $D$ are isomorphic. The deck is the multi-set of vertex-deleted subgraphs of a graph (which ...
66 views

### Prove we can't Finding an element $A[i]=i^2$ in sorted array with $\log n$ time.

We are given a sorted array$A[1..n]$, we are searching to find an element that $A[i]=i^2$ in array. How we can prove that we can't do it in $O(\log n)$? My idea: do a linear search in array in $O(n)$...
79 views

### Find an element that repeated $\frac{n}{5}$ times in sorted array

We are given a sorted array$A[1..n]$, we are searching to find an element that repeated $\frac{n}{5}$ times in array.How we can do it in $logn$? I find an solution in $O(n)$,with checking each ...
56 views

### Maximum matching for general graph

I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
53 views

### Binary Search average time complexity

I'm looking for explanations for this solution. I have tried and found the solution in book Art of Computer Programming. Volume 3. Sorting and Searching. Second Edition but this didn't help me at all. ...
65 views

### Efficient directional nearest-neighbor search among rectangles

I have a large set of rectangles with random orientation and size. Say up to $10000$ rectangles, which are non-overlapping. For every rectangle, I need to find the nearest compatible neighbor. Two ...
36 views

### Searching/Sorting Algorithm

I just started studying algorithms and data structures and came across this problem: Given $x \in \mathbb{N}$ and two integer Arrays $A_1$ and $A_2$ each of the length $n$. Write an algorithm in ...
71 views

### Binary Search, probability of element being found

What is the probability of an element being found? What would the math probability formula look like for an element being found? What is the probabilistic analysis of an element being found? I have ...
I apologize in advance if this sounds vague but I am trying to find directions as to what to look for. All the sets in this problem are finite. Suppose I have two functions $f_1:X_1\times Y_1->X_1$ ...