Questions tagged [searching]

For questions about various search algorithms.

Filter by
Sorted by
Tagged with
15
votes
3answers
6k 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 ...
14
votes
4answers
18k 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 ...
14
votes
2answers
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. ...
12
votes
1answer
301 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 ...
12
votes
1answer
122 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 ...
6
votes
1answer
1k views

Searching for rock-hard integers.

For integer $k\geq 0$ written $d_jd_{j-1}\dots d_1$, where $d_i$ are single-digit integers, define $$R(k) := \begin{cases} d_j^{d_1}d_{j-1}^{d_2} \dots d_{j/2}^{{d_{j/2 + 1}}}, & j \text{ is ...
6
votes
3answers
3k 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 ...
4
votes
4answers
14k views

Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Update: This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution. http://www.youtube.com/watch?v=VbSwwos4R2E Hi, I want ...
4
votes
3answers
307 views

Minimum number of steps required to visit every corner of a rectangular grid

I am stucked at this problem: Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$ (I.e $G$ is a matrix that have $m$ rows and $n$ colums over the ...
4
votes
2answers
8k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
4
votes
1answer
7k views

Term-document vs document-term matrix [closed]

I am not sure if this is the right website to ask this question but I cant figure out where else to get the answer so, please, dont be mad :-) As my bachelor thesis/project, I am trying to construct ...
4
votes
1answer
95 views

Spacing of fence posts with minimal distance to other fence posts

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ($\...
4
votes
1answer
78 views

Optimal curve to find a lost person in a forest

I read a story about somebody getting lost in a forest, and, apart from sympathy, the following mathematical problem came to my mind. Suppose the lost person is sitting still at an unknown point in a ...
3
votes
2answers
7k views

What is the best strategy for a guess-my-number game?

In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure: Player B decides on a number between a ...
3
votes
1answer
76 views

Can you find an invertible submatrix?

Given an $m\times n$ matrix $\mathbf{A}$ $(m\gneqq n)$, I'm trying to efficiently find all $n\times n$ invertible submatrices using a computer. Equivalently, I'm trying to find which rows of $\mathbf{...
3
votes
1answer
1k views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers $...
3
votes
0answers
69 views

Lost in a Forest Problem 3d Verision: Point and Plane

The lost in a forest problem is famous, specifically see this problem. The problem takes place in the plane. Consider the following 3d version. There is a point $p \in \mathbb{R}^3$ and a plane $P$ ...
2
votes
2answers
242 views

Finding Lowest Elevation Path Between Two Points

Let's say I have a matrix of values that represent heights with function $f(x,y)$ and I am trying to find the "lowest value path" beween two points. So this would be the reverse of hill climbing, as ...
2
votes
1answer
79 views

What is the best way to guess a number in a limited number of guesses?

A random integer is picked from 0 to 100. You can make 5 guesses at what the number is, and after each guess, you are told if your guess was too high or too low. What strategy maximizes your ...
2
votes
1answer
104 views

Searching for a secret, given a non-uniform distribution

Let $s$ be an unknown bit string of length $n$. Let $p(i, b)$ be the probability that $i$-th bit of $s$ is equal to $b \in \{0,1\}$. What's the fastest method to find $s$, given the distribution $p()$?...
2
votes
0answers
46 views

Do “randomized single player problems” always have optimal strategy? How to find one?

What I mean by a "randomized single player problem" is roughly the following: Certain information of the game is derived from a known random distribution (can assume uniform) and is hidden from the ...
2
votes
1answer
29 views

Restricted query problem

I am considering a problem which seems very classic but have no idea where to find the related results. Any help or comment will be appreciated. Given a non-empty set $S$, a set $Q$ of the subsets of ...
2
votes
0answers
115 views

IOI '96 Magic Squares: Reaching Squares Using Transformations

A magic square is $2\times 4$ matrix with entries $1, 2, \dots, 7, 8$ where no entry occurs twice (equivalent to a permutation). As an example, consider the following magic square: $\displaystyle \...
2
votes
1answer
139 views

Find the three closest surrounding neighbors from a data

I have a data of coordinates $x$ and $y$ where we know the range of both variables, e.g. $(x,y)\in[0,1]^2$. So for a given any random point $\theta_0=(x_0~~y_0)^T$ in the range of $x$ and $y$ I would ...
2
votes
0answers
264 views

n-dimensional searching alogrithm

If you want to store various points in a $n$ dimensional (here $n=2$) space. Is there a possibility to do that with a tree (as a binary-tree for $n=1$ is usually used) for efficient and fast finding ...
2
votes
0answers
1k views

A* vs D* vs Dijkstra [closed]

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* ...
2
votes
0answers
230 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where $\...
1
vote
3answers
524 views

Why a binary search algorithm works?

Let $n$ be a positive integer and $f \colon \{1,\dots,n\} \to \mathbb{R}$ be a decreasing function with $f(1) \ge 1$. We are interested in finding the largest number $k\in \{1,\dots,n\}$ such that $f(...
1
vote
1answer
283 views

Counterexample for statement about binary search tree

Let's say, key $k$ was found in a leave of a binary search tree. Let $P$ be the search path from the root of the tree to the node with key $k$. Let set $A$ contain all nodes left from path $P$. Let ...
1
vote
1answer
803 views

Breadth-first search tree

It seems intuitive, and is actually proven in many books, that each path from starting vertex to another one in any search tree of a breadth-first algorithm is the shortest. However, I couldn't find ...
1
vote
1answer
3k views

What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
1
vote
1answer
677 views

Computational complexity of Eulerian and Hamiltonian paths and cycles in (un)directed graphs

Hey Guys I am aware that we can find if there exists a hamilton path in a directed graph in O(V+E) time using topological sorting. I was wondering if hamilton cycles, euler paths and euler cycles can ...
1
vote
2answers
25 views

Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function [closed]

A Boolean function $f(n)$ is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal ...
1
vote
1answer
599 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
1answer
750 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 ...
1
vote
1answer
161 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 ...
1
vote
3answers
2k views

How to apply DFS on a disconnected graph.

I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph. How would I go through it in DFS? My current ...
1
vote
1answer
71 views

Smart enumeration of a subset of graphs obtained from a parent graph

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, ...
1
vote
1answer
521 views

Algorithm to find difference between two array members

I have a question concerning algorithms and time complexity(analysis).So I have a field A,which is sorted and has natural numbers where n is >=2(ascending order).How would you write an algorithm which ...
1
vote
1answer
36 views

How to implement an algorithm for specific kinds of search in a graph

Imagine i have a graph called G. G has some parts. In one part, every node describes a person. I have another part in G which contains interests as nodes. ( Imagine that person A likes music. So, ...
1
vote
1answer
39 views

Does this search method exist and what is it called?

I would like to search some function $f(x)$ "greedily" for a certain condition. Assume the condition $c = f(x_1)$ returned by this function is currently false and I can increase the input $x$ to the ...
1
vote
1answer
60 views

Exploiting geometric invariants via group theory

Let $T$ be the set of all plane triangles. The problem is to find $t \in T$ s.t.h. a predicate $P(t)$ holds. At present, I'm doing this by a form of randomized search procedure (effectively via a ...
1
vote
1answer
36 views

Need help understanding a simplification in a simultaneous search model.

The problem I am trying to solve is $\max_{k \in \mathbb{N}} \int_0^1 u d F(u)^k - ck$, where the associated utility is an iid random variable U following $F(\cdot)$ on [0,1]. $c > 0$ is the ...
1
vote
1answer
724 views

Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%. Two ...
1
vote
2answers
755 views

How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
1
vote
1answer
31 views

Binary search in merged arrays.

Given two arrays, sorted by ascending. Result array is first array and second at the end of first. Example: [1, 4, 7, 11] and [2, 3, 5]. Result array is [1, 4, 7, 11, 2, 3, 5]. How to find element ...
1
vote
1answer
228 views

Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
1
vote
1answer
39 views

Having objects trajctories and directions how to find where objects traverse same path?

I have N objects that travel on some trajectories (unique for each object). At each agent curve point we can get object speed (direction). Having some distance ...
1
vote
1answer
157 views

Is there a simple function which can be used to determine the two “next” search indexes in a binary search?

Edit: question simplified to remove confusion Assuming a sorted list of items with indexes from 1 to N, and given only an index number ...
1
vote
1answer
31 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 ...