Questions tagged [search-algorithms]
Algorithms for finding an element in some specified data-structure (most commonly, in a tree).
680
questions
0
votes
0
answers
13
views
Zero Knowledge Protocol for Search Problem
Does anyone know any zero-knowledge protocol that addresses the search problem, i.e. finding the output to a query without revealing the query or any other output?
2
votes
0
answers
38
views
Quantum search with input as a classical circuit
Grover's algorithm assumes $U_f$ computing a function $f$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $f$ is given. So let's assume a reversible circuit, $C ...
- 73
2
votes
1
answer
48
views
Why is this proof that CHESS is in EXPTIME correct?
I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
- 23
3
votes
1
answer
87
views
Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...
Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
- 31
0
votes
0
answers
17
views
Performing fuzzy search queries on a large database of strings
I have a large database of strings (~10 million)
I need to perform fuzzy search queries which would find the best match inside that database.
The best match meaning the one that has the highest 'score'...
- 113
0
votes
0
answers
21
views
What is the difference between Local Beam Search and Stochastic Beam Search?
I know that both of them select K randomly, and then choose the best K, as I understand the ...
user157493
1
vote
1
answer
138
views
Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
- 129
1
vote
2
answers
89
views
Perfect ordered hash function on ordered sequence
I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.:
$(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$
...
- 287
0
votes
0
answers
20
views
CPU limit for bitap algorithm bitmask
We have bitap (shift OR) algorithm that searches for a substring in a text.
Bitap algorithm uses bit masks, so that it can perform bitwise operations very fast with the help of CPU.
For example:
...
- 101
1
vote
2
answers
336
views
Ordered sequence with logarithmic insert and remove
Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity.
<...
- 13
0
votes
3
answers
57
views
Given two sets of coordinates, find out neighboring ones
I have two sets of 2-dimensional coordinates on an integer grid, $A$ and $B$
$A = \{(x_{A1},y_{A1}), (x_{A2}, y_{A2}), (x_{A3}, y_{A3}), \dots\}$
$B = \{(x_{B1},y_{B1}), (x_{B2}, y_{B2}), (x_{B3}, y_{...
- 181
2
votes
1
answer
283
views
Understanding Rabin-Karp's rolling hash computation
Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then ...
- 183
0
votes
1
answer
61
views
How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?
I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.
What ...
- 225
0
votes
0
answers
20
views
How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?
Take this trie as example:
I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
- 1
0
votes
1
answer
18
views
Algorithm to find best order for items on pages with a fixed height
I am looking for an algorithm to find the best order of items to fit on pages.
Consider the following case, we have a page with the height = 300
We have images with the following heights - [150,200,...
1
vote
1
answer
56
views
If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?
I am currently studying the concept of heuristics in search algorithms. I recently asked this question about the so-called "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\...
- 201
0
votes
0
answers
47
views
How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?
I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following:
Greedy search minimises estimated path-cost to goal.
But it's ...
- 201
0
votes
0
answers
75
views
How do these search algorithm diagrams work? How am I supposed to interpret them? And what algorithms do those last three represent?
I was shown these diagrams in the context of search algorithms. The green tile shows the initial state, and the orange tile shows the goal state. I am told that each option shows a path each search ...
- 201
1
vote
0
answers
33
views
Is there a comprehensive list of searching algorithms for sorted (and possibly unsorted) arrays available anywhere?
Classic searching algorithms such as binary searching and dictionary searching search sorted arrays based on a given element and make estimations on their own. What I'm looking for is a list of more ...
- 11
0
votes
1
answer
28
views
Hill climbing method searching special polynomial equations
I have system of two polynomial two variables, second order; monomials are {${1,x,y,x^2,xy,y^2}$}
I want find special systems of polynomials: two or more roots in specified range, two root close to ...
- 141
0
votes
0
answers
7
views
Optimising for many points in a monotone function
I'm trying to optimise (to a certain precision) a monotonic function for many points (100+). I know a-priori that the function is continuous, with some parts zero derivative. I know that all points ...
1
vote
1
answer
53
views
search with inadmissible heuristics
I was told that search algorithm such as IDA* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the ...
- 163
0
votes
0
answers
34
views
Efficient way of to find $k$-shortest paths
I want to (repeatedly) find the $k$-shortest paths between two nodes in a large sparse directed cyclic graph with non-negative edge weights. Is there a more efficient solution for this than Yen's ...
- 181
0
votes
0
answers
34
views
Iterative algorithm for assembly index? [duplicate]
DOI: 10.3390/e24070884 provides pseudocode for computing the assembly index of an object. It is written as recursive algorithm, which might be fine. But I would like to implement an iterative version ...
- 125
1
vote
2
answers
62
views
Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays
Consider an array A[1..n] that first increases up to some point p then it decreases until some point q and then increases again. That is A[k] < A[k + 1] for all k in [1..p] and [q..n] and A[k] >...
- 57
0
votes
0
answers
191
views
Understanding heuristic function (Berkeley AI Project 1)
Cheers, I am playing around with Berkeley's AI Project 1 (Pacman) (link here) and I am trying to find a good heuristic function for the foodHeuristic function (Question 6).
While playing around with ...
1
vote
2
answers
55
views
Existence of some search algorithms
The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$.
The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$
So in order to be able to use a search ...
- 119
0
votes
2
answers
50
views
Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)
I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than
O(N²)
...
0
votes
1
answer
91
views
Simulated Annealing - Intuition
Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below:
...
- 121
1
vote
1
answer
72
views
$O(n \log n)$ Algorithm for first Train Problem
On $n$ parallel rails there are $n$ trains with constant speeds $v_1, ..., v_n$. At time $0$ the trains are at positions $k_1, ..., k_n$. Find an $O(n \log n)$ algorithm that determines which trains ...
- 11
1
vote
1
answer
100
views
A nearest neighbor data structure for meshes
I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
- 177
1
vote
0
answers
46
views
Search algorithm with at most a constant $k$ failed accesses [duplicate]
Let $A$ be an array sorted in non-increasing order. Let $m$ be a natural number. For example, let $m = 10$. We want to find the index $i$ such that $A[:i]$ contain elements less than or equal to $m$, ...
0
votes
1
answer
95
views
Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?
I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
- 101
1
vote
1
answer
56
views
Efficient search of a large set of documents to find documents that only contain a particular set of words
Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language.
Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
- 111
1
vote
0
answers
54
views
Unusual version of a binary search algorithm
For one dimensional, continuous binary search most effective algorithm would remember boundaries.
For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
2
votes
0
answers
47
views
2
votes
2
answers
628
views
How can I apply binary search to find two adjacent increasing elements in an unsorted array?
I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
- 164
3
votes
1
answer
27
views
optimal search algorithm for finding parameters and thresholds
I have the following problem:
There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'...
- 31
2
votes
2
answers
404
views
Decision tree for searching element in sorted-array
Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?
The answer is $ \Omega(\log n) $ ...
- 233
1
vote
1
answer
66
views
Complexity of Nelder-Mead Algorithms
If the objective function contains $n$ variables (e.g. $f(x_1, ..., x_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the ...
- 123
0
votes
2
answers
109
views
O(Log n) Search - Array
So, there's a LeetCode problem that has you find a O(log n) solution to finding a target number in a rotated sorted array.
As an example:
...
-1
votes
1
answer
221
views
Is there an O(m (log n+ log m))-time algorithm that finds k-th smallest element in a row-wise-sorted two dimensional array?
I prepare for entrance exam and try to practice some hard problems.
The following nice problem is problem 1(c) of this problem set.
Suppose we are given a two-dimensional array $A[1...m][1...n]$ in ...
- 7
2
votes
1
answer
68
views
Research project problem on Computational Geometry
(Most fair region) Let $P$ be a set of $n$ points in the two-dimensional plane. Each point in $P$ is either colored red or blue. Given an axis-aligned rectangle $R_{ab}$ of size $a\times b$ , design ...
4
votes
6
answers
2k
views
"Guess the number" Problem on Turing machines
I am currently learning about the concept of Turing Machines and trying to relate it with my knowledge on the application of the Binary Search algorithm.
The problem I am working on is to write an ...
- 61
0
votes
0
answers
9
views
How to do contains-edit-distance match across many strings at once efficiently?
given these strings (one per line)
oaccdefhmhhvoobagqhv
gremqskkhhpipkbwlsgd
jcfonoxymqhnkidrwhup
gijquczafmhygjsiyqxe
abdcegfcnxdmtqqjgpuc
oayapipwinwuzdvcyaxm
hfudoatjkjxpmztpseav
...
- 151
2
votes
0
answers
38
views
Pairwise intersections of segments in a rectangle
Let V be a set of vertical segments, and H be a set of segments parallel to a line (e.g. a line with slope -1). We want to find a data structure for set S = V ∪ H to find all pairs (v,h) of segments ...
- 21
2
votes
1
answer
92
views
How do distributed joins work in a distributed relational database system?
I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
- 1,953
0
votes
1
answer
43
views
How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?
Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one
Eg.
...
- 168
1
vote
1
answer
212
views
what are good data structure algorithm for fast 3D coordinates search?
I want to form data structure for nearby neighbor search for 3D coordinates. What is the best way to do so?
2
votes
1
answer
143
views
Find repeated patterns in a string via lossy compression
Description
The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
- 123