Skip to main content

Questions tagged [searching]

For questions about various search algorithms.

Filter by
Sorted by
Tagged with
2 votes
1 answer
52 views

Is it possible to find something better than binary search for this problem?

Let's say we have $n$ urns (numbered $1$ through $n$) and the first $k$ urns have a ball in them (for some $k$ unknown to us) and the remaining urns are empty. Our goal is to determine $k$ by looking ...
user23571113's user avatar
  • 1,373
0 votes
0 answers
29 views

best search method in the complex plane

For real number search problems, the binary search algorithm is the go-to method. Yet, the answer becomes not so obvious when considering searching for some number $x$ such that $|x-Z_0|\leq R$. I ...
ironmanaudi's user avatar
0 votes
1 answer
35 views

search for specific value out of data set

I am looking for a function or formula how to determine the data set for a specific value (sum) out of a set of data in a table. The function should be the fastest possible search to achieve the ...
mcantsin's user avatar
  • 101
0 votes
0 answers
79 views

Finding the Pareto frontier when the optimization problem is simple?

I am working on the following problem: Find integer $\vec{x}\geq 0$ within the solution space $\mathbf{A}\cdot \vec{x} \leq -1$ such that none of $(x_1, \ldots, x_n)$ can be made any smaller. In ...
user326210's user avatar
  • 17.6k
0 votes
0 answers
55 views

DFS on disconnected components.

I was given the following graph. Does the DFS stop at c? So: a,b,d,c. or does it continue with the other component as well? I'm not sure on how it works with disconnected graphs but from what I read ...
Ninaaaaa's user avatar
0 votes
0 answers
47 views

Height of a "random" binary search tree

See also this question, but I'd like to know the simpler case which in that question refers to CLRS 12.4 (looked it up - no formula found!). So, assume you have a list $L=\{1,\dots,n\}$ and an ...
Hauke Reddmann's user avatar
0 votes
0 answers
19 views

Compilation of Phenomena Modeled by an Operation Table

It seems like there would be utility in a search engine or database through which the user inputs the operation table of a magma (I think that's the right level of algebraic structural generality) to ...
user10478's user avatar
  • 1,912
0 votes
0 answers
55 views

A mathematical expression/ model for a algorithm

I have created a simple algorithm in Python to create an ensemble deep-learning model to improve the accuracy of prediction. It's similar to a grid search method which I used to find the perfect ...
Navod Neranjan Thilakarathne's user avatar
2 votes
1 answer
205 views

Prune graph to detect cycles: better than DFS?

By pruning a undirected graph G, I mean iteratively removing all leaves (nodes of degree 1) together with the incident edge from a graph until you are left with a single node (G contained no cycle) or ...
johk95's user avatar
  • 123
1 vote
0 answers
224 views

Seeking Proof: Can Rubik's Cube States be Mapped to a Euclidean Space of a Certain Dimension?

I am currently researching a problem that involves mathematics and computer science, and I am hoping to get advice or guidance from experts in the field. My question pertains to finding a mapping that ...
B2GAN's user avatar
  • 11
0 votes
0 answers
51 views

Find upper and/or lower bounds for the least prime $p$ such that $p^n + k$ is the product of $n$ distinct primes

Well, first of all, happy new year to everyone. I am trying to solve the following problem: "Let $k$ be a fixed natural number. Find the least prime $p$ such that there exists a natural number $...
Jan Eerland's user avatar
  • 28.7k
1 vote
1 answer
429 views

Median of medians algorithm [closed]

My question is I don't understand how we determine the constant in T(T(n/3), T(n/5)). For example, we divide elements into 9 groups and get a formula like this T(n) <= T(n/9) + T(7n/9) + O(n) I don'...
Rustam's user avatar
  • 13
0 votes
1 answer
30 views

Need a concise way to query a database with limited filters

I have two observers identifying pets - Sam and Cindy. For each pet, Sam and Cindy have to say what kind of pet they see (dog, cat, leprechaun, etc.). They enter their results into a database and I ...
Baasoti's user avatar
0 votes
0 answers
35 views

Seeking math category for ranking example

I’m searching for the correct math category for a problem so I can hire a developer, but need to know the general approach (I hope math exchange is an appropriate forum for this question) This ...
tom's user avatar
  • 109
2 votes
1 answer
143 views

Do weights of edges affect the shortest path in 2D grid undirected graph

I'm struggling with the shortest path finding problem in a road network in my program: Given a map, the roads are arranged as a 2D grid, and the roads intersect to form a series of nodes. There are ...
Abraham's user avatar
  • 23
1 vote
0 answers
131 views

Probability of linear search with repeated elements.

I am trying to find the probability that a linear search on an array of size n takes j comparisons. We are looking for the element x and there are k x's in the array where 0 < k < n. I tried ...
lados's user avatar
  • 21
1 vote
1 answer
190 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 ...
Salvatore Ambulando's user avatar
0 votes
0 answers
119 views

A root-find algorithm for the first-zero of a discontinuous function?

I'm working on a problem at work that requires me to search for the first date (x) that a financial model returns a value greater than zero (y>0). Our current approach is simple. Start a guess-and-...
GrantG's user avatar
  • 1
1 vote
0 answers
331 views

Calculate all possible paths in graph

I have a number of graphs that look similar to this: Graph In this image, there are 4 levels and 4 node per level: Green is level 1, Blue is level 2, Pink is level 3 and Yellow is level 4. Graph - ...
FlushaCastanho's user avatar
0 votes
1 answer
78 views

Number Of Global Optima in Single Solution Metaheuristics

I am reading the book "Metaheuristics From Design to Implementation" written by El-Ghazali Talbi and on page 91, in the "Single-solution based metaheuristics" section, he says ...
tahasozgen's user avatar
1 vote
0 answers
39 views

Searching a vector space (ish?)

I come from a computer science background so please forgive any math transgressions I make. I will try to describe what I'm looking for as best as I can. I've been looking into methods of searching a ...
Abdullah Hasan's user avatar
0 votes
0 answers
50 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 ...
Grzybojad's user avatar
2 votes
1 answer
140 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 ...
Max's user avatar
  • 1,267
0 votes
0 answers
1k 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 ...
Christian G. Faraone's user avatar
0 votes
2 answers
139 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 ...
Jurian Baas's user avatar
1 vote
1 answer
279 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 ...
curiousCoder's user avatar
6 votes
2 answers
265 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 ...
Hans-Peter Stricker's user avatar
0 votes
0 answers
99 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)$...
tstt's user avatar
  • 341
0 votes
1 answer
242 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 ...
tstt's user avatar
  • 341
0 votes
1 answer
249 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 ...
Claudio P's user avatar
  • 141
0 votes
0 answers
73 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. ...
Sallix's user avatar
  • 1
1 vote
1 answer
228 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 ...
user avatar
1 vote
2 answers
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 ...
zartos's user avatar
  • 105
1 vote
0 answers
396 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 ...
aman's user avatar
  • 111
3 votes
1 answer
649 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{...
user326210's user avatar
  • 17.6k
1 vote
1 answer
73 views

Find all traces satisfying a set of linear temporal logic (LTL) formulas

I want to compute all finite traces up to a given length that satisfy a set of linear temporal logic formulas. Does such an algorithm exist?
llisch's user avatar
  • 11
0 votes
2 answers
794 views

Finding initial lower and upper bounds for bisection search for polynomial's roots

When computing the nth root of a polynomial equation using bisection search, how does one find the upper and lower bounds of where to search? Is there some kind of formula to bound the nth root to a ...
user avatar
5 votes
1 answer
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 ...
Descartes Before the Horse's user avatar
0 votes
0 answers
25 views

Searching with a 1D car?

Consider the task of programming a 1D car starting on point $0$. The car drives 1 km / min ( to both left and right). The task is to find a coin at an unknown integer distance $x$ (in km) from the ...
mick's user avatar
  • 16.1k
1 vote
1 answer
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 ...
thatguyjono's user avatar
1 vote
0 answers
30 views

Is it okay to not provide a whitelist when using the Hill-Climbing algorithm?

So, I'm trying to use Hill-Climbing for a Bayesian learning network. For some reasons, I do not know all of the variables that I'm going to use and hence, I cannot provide a whitelist or a blacklist ...
riyag2805's user avatar
1 vote
0 answers
35 views

Which uniformed search algorithm is the best here?

So I have an exercise like this where I have to choose the best strategy. I wonder here which one is the best: A robotic engineer wants to add movement planning ability to a small mobile robot. ...
Ala Pa's user avatar
  • 11
1 vote
0 answers
141 views

Is this how you calculate the reservation price?

I was wondering if you could help me make sure I have things correct. Weitzman (1979) (Optimal search for the best alternative) considers a decision maker that is facing n boxes, each box has ...
mathlover's user avatar
2 votes
0 answers
109 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 ...
Andrea2333's user avatar
12 votes
1 answer
147 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 ...
Joel Croteau's user avatar
3 votes
3 answers
9k 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 ...
taway0282's user avatar
4 votes
2 answers
995 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 ...
BBSysDyn's user avatar
  • 16.2k
0 votes
1 answer
2k views

Binary Tree mathematical equation for number of internal nodes [closed]

I was wondering how does this equation: $$\frac n2 + \frac n4 + \frac n8 + \dots + 1$$ go to: $$1 + 2 + 4 + \dots + \frac n2$$ and then to: $$\sum_{i=0}^{h-1} 2^i,\; \text{where $h$ is the height ...
fynx's user avatar
  • 13
3 votes
0 answers
102 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$ ...
user avatar
2 votes
1 answer
37 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 ...
Alton Wang's user avatar