# Questions tagged [searching]

For questions about various search algorithms.

143 questions
Filter by
Sorted by
Tagged with
9k views

### Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time. Given a set of ...
• 293
23k views

### Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n - 1$. This is so because the set ...
2k views

### Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
• 1,445
327 views

### The "find my car" problem: proper interpretation and solution?

This has been asked at least twice here, but both questions have accepted answers which are wrong. I don't really know any good way to draw attention to the question besides asking again and being a ...
• 5,414
152 views

### Searching for a point on the real line

A pin is dropped at a random point $p$ on the real line, with $p$ determined from a normal distribution with mean $0$ and standard deviation $\sigma$. You are dropped on the real line at $x=0$ and ...
• 259
5k views

### In what sense is “Uniform-cost search” uniform?

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the ...
• 201
268 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 ...
• 18.3k
1k views

1 vote
2k views

### Prove that a connected undirected graph G is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for G

My question is in the title but to restate: Prove that a connected undirected graph $G$ is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for $G$. (BFS ...
1 vote
966 views

### Weakly unimodal function using Golden Section Search

I was going through the Golden Section Search https://en.wikipedia.org/wiki/Golden_section_search and as I understand it should work for every unimodal function. Here, the definition of unimodal ...
• 543
1 vote
185 views

### How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
• 115
1 vote
194 views

### Algorithim to choose comparison pairs for topological sorting

I'm trying to find or create an algorithm to roughly sort arbitrary objects using pairwise comparison where the only concern is minimizing the number of comparisons. So my question is essentially is ...
1 vote
284 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 ...
1 vote
231 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 ...
1 vote
41 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 ...
• 105
1 vote
50 views

### Difficulty understanding the relation between the representation of a number and the time complexity of searching for (0, N - 1)?

Please refer here to the direct resource that I don't understand. Let's take the number $X = 245436$, we can represent the following as X = 2 \times 10^5 + 4 \times 10^4 + 5 \times 10^3 + 4 \times ...
• 271
1 vote
Suppose i have a graph $G$ of $n$ nodes. For each node someone has given us a recipe $R$ how to replace the node with a graph. So for node $i$, i have $m_i$ choices of graphs to replace it with. Thus, ...