Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 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
19 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
50 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^\...
0 votes
0 answers
41 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 ...
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 ...
1 vote
0 answers
31 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 ...
0 votes
1 answer
26 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
6 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
43 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
30 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 ...
  • 103
1 vote
2 answers
53 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] >...
0 votes
0 answers
142 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
54 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 ...
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
80 views

Simulated Annealing - Intuition

Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below: ...
  • 111
1 vote
1 answer
65 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
76 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
87 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 ...
1 vote
1 answer
36 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, $\...
1 vote
0 answers
40 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
39 views

Understanding MTD-f

In the MTD-f algorithm: ...
  • 123
2 votes
2 answers
568 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
26 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'...
2 votes
2 answers
251 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
51 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
1 answer
73 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
187 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
62 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 ...
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 ...
2 votes
0 answers
35 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 ...
2 votes
1 answer
64 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,941
0 votes
0 answers
79 views

Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
  • 1,941
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
0 votes
0 answers
11 views

how do I store 3D rectangle geometric data in kd-tree and check closeness?

There are a bunch of 3D rectangle and I plan to store them in KD-tree for neighborhood search. How to construct such tree and how to check if two rectangle are next to each other?
1 vote
1 answer
138 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
128 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
1 vote
0 answers
217 views

Algorithm to find maximum sum over weighted overlapping intervals

Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
  • 121
1 vote
0 answers
1k views

Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
1 vote
1 answer
57 views

Examples of comparison-based algorithms that are not a sort or a search over lists

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
  • 416
4 votes
0 answers
103 views

Searching a bitonic array with roughly $2\log n$ comparisons

I don't know how to search a bitonic array with roughly $2\log n$ comparisons in the worst case. What I am trying now is to find the maximum integer using roughly $\log n$ comparisons (binary search) —...
  • 141
1 vote
1 answer
35 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
1 vote
1 answer
77 views

Design an optimal algorithm that finds 2 array indices in a sorted array such that $A [i] + A [j] = k$

Text: ...
0 votes
1 answer
290 views

True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
0 votes
0 answers
32 views

Data structure for incremental KNN (IKNN) search over high-dimensional vectors

I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
2 votes
0 answers
131 views

Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
  • 21
4 votes
0 answers
102 views

How do search engines implement fuzzy search?

Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses". How is Google able to return near-...

1
2 3 4 5
14