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
1
vote
0answers
19 views

What is the state of the art of full text searching across languages?

I have looked at a few papers on this such as this, and it basically says that full text search is all about English with few resources for languages without spaces between words (like Chinese or ...
2
votes
0answers
50 views

How to prove that the pseudo-code of thresholded-A* algorithm from my teacher's book is correct?

I have the following DFS2 pseudo-code, which is used in the pseudo-code of IDA*, from my teacher's book, but I cannot understand why it's correct: ...
0
votes
1answer
109 views

Algorithmic challenge: generate a list of random non overlapping squares

For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap. So the challenge is simply: given a two dimensional area $a$ (...
0
votes
2answers
55 views

How can I get index of combination from element indices

An array of combinations is generated from two arrays, ...
-1
votes
0answers
54 views

Race Car Algorithm

I am trying to solve the following question: Your car starts at position 0 and speed +1 on an infinite number line. (Your car ...
2
votes
1answer
27 views

Finding pair of sum in sorted array in time complexity less than $O(n)$

In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. ...
1
vote
1answer
20 views

How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]

I was asked this question today: given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n] IF we ...
1
vote
0answers
16 views

Greedy Best-First Search Performance for Tree and Graph Space

I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being not optimal in Tree Search for Finite and Infinite Spaces that it is ...
0
votes
1answer
38 views

Find amount of elements greater then number k in a BST

I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K. I found it problematic as there are elements which might be greater then K but wont ...
1
vote
1answer
12 views

Does n^(1-1/d) always dominate log^d(n)

Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other. So I found out about k-d-...
2
votes
1answer
69 views

Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can ...
1
vote
0answers
18 views

Intellij string search and highlight algorithm

I'm searching for an alogrithm that takes two strings, a query and a string that is to be searched for the query. The algorithm should result in a 'found' when the string contains the characters of ...
2
votes
0answers
14 views

Smart String search algorithm

I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible. For example, if a query is for the ...
3
votes
1answer
28 views

Optimise the size of union of sets

We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. ...
1
vote
0answers
23 views

How do I calculate the average number of comparisons for linear search?

In a list of 15 entries (city names) if searching for a particular name what is the average number of comparisons using linear search? Worst case it would 15 comparisons and best case it would be 1 ...
1
vote
3answers
60 views

The most efficient algorithm for finding the highest valid number for an API

I have many API endpoints that take IDs that are constantly increasing. I want an algorithm to find the highest number in the least amount of requests. I need to do this without knowing what the ...
1
vote
0answers
34 views

Fastest way to determine constrained sum of an array

I have two $N$-vectors of positive integers, called cost and gain, and I have another integer called ...
1
vote
1answer
19 views

Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
0
votes
0answers
12 views

Are arc inconsistencies predictable?

Are arc consistency algorithms such as AC-3 inevitable for CSP to be solved more efficiently through pruning of inconsistent values? Can't we use the constraints that we have and predict arc ...
0
votes
0answers
43 views

Finding first occurence of all possible matches?

Say you have multiple strings that you're trying to match in a text. And it's possible all these strings have a match in the text. Is there a good way to return out of all the matching strings the ...
0
votes
0answers
46 views

Algorithm for sorting arrays of arrays

I have a problem where I need to sort array of arrays. For A being a array arrays (a1,a2,a3,...an) were each a = {0...d} d=fixed number of elements. *The assumption all sublists will have fixed ...
0
votes
0answers
32 views

Extending a solution in backtracking

Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm: ...
1
vote
1answer
83 views

Minimum number of given operations in order to group letters in a string

Description Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
2
votes
1answer
43 views

Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
0
votes
1answer
29 views

Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats

With my application, I have Collection X: thousands of floating-point numbers with the value range [0, 1], not sorted. Collection Y: 11 floats ranging from [0, 1], sorted. The size of X is known. Let ...
5
votes
1answer
34 views

Isn't this Commentz-Walter algorithm buggy?

I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible ...
0
votes
0answers
40 views

Which advanced data structure to use?

For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
6
votes
1answer
144 views

Binary-ish search through partially ordered set

I have an interesting function. It takes subsets of {1,...,N} to positive integers, i.e. $f:P([N]) \rightarrow Z^+$. I know that if S is a subset of S', $f(S) < f(S')$. Also, if S and S' have the ...
2
votes
1answer
38 views

How do you find all integers in a sorted array of size n that appear n/k times?

I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time? I could only find this question, where O(klogn) ...
1
vote
0answers
57 views

Searching a 2D array of binary Data

I'm working on optimizing the structure of an optical meta device. I have a randomly generated 2D matrix, where 0,1 represents the presence/absence of a hole. Each structure manipulates light ...
0
votes
3answers
29 views

What algorithm should I use to find the closest solution to a given total using a list of integers?

My problem is this: Let's say I have an arbitrary list of integers A[2013, 54, 3, 32 1, 23...] What is the best strategy to find which of those numbers I should add together to have a sum equal or ...
1
vote
0answers
11 views

Batching multiple nearest surface queries: Is it faster? Are there better algorithms?

I'm working on an algorithm that computes lots of "nearest point on a triangulated surface" queries in 3d as a way to resample data sets, and I'm wondering if there is any information out ...
1
vote
0answers
32 views

Set data structure for data too large to fit into memory

I'm trying to solve the following exercise: Given N data items and memory that can hold M/B blocks of size B. Describe a data structure that needs at most N/B blocks of external memory and allows ...
1
vote
2answers
54 views

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Given a sorted array of integers and a target integer, find the number of occurrences of the target integer. It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the ...
2
votes
2answers
73 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
2
votes
1answer
44 views

O(m+n) Algorithm for Linear Interpolation

Problem Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the ...
1
vote
1answer
21 views

Search a number

Given n numbers, design an algorithm to find the smallest $n^{\frac{2}{3}}$numbers, in sorted order. (Assume $n^{\frac{2}{3}}$ is an integer.) I don't understand this question. Can I simply $x = n^{\...
1
vote
2answers
55 views

Algorithm for optimal rule-based arrangements?

I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
0
votes
1answer
34 views

Find Best N Points From a Graph

I've given a task and wonder if there are any better solutions. Inputs of task are: Distance of district pairs Population of pairs Goal is: Find n districts at which its population and districts ...
0
votes
0answers
12 views

Parsing text, then searching it: one entry per position, vs. 1 JSON column per text

I have a Rails application using Postgresql. Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?). The text gets parsed, both ...
0
votes
0answers
24 views

Powells Method for 2 Variables?

I've been studying this YouTube video on Powells method and it looks like when we have a single variable we start at the upper and lower bounds of the variable and then we keep dividing the search ...
0
votes
0answers
28 views

What datastructure does google use to store its search engine indexes?

To the best of my knowledge search engines such as Google index the web using MapReduce amongst many other tools. With my limited experience this would make hash tables the most practical option for ...
1
vote
1answer
33 views

What solution to apply for finding the optimal parameters?

For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
0
votes
1answer
21 views

N 3d integer points in box with maximum average distance

given a 3d cube with a size of m x m x m, is there an efficient algorithm to find N integer points with the average Euclidean distance between each pair maximized? If not, is there any evolutionary ...
0
votes
1answer
17 views

Search Space for Population Metaheuristic Optimization Problem

Given that x objects (repetition allowed) can be arranged into y configurations, and that the population size is N, I am uncertain as to whether the size of the search space is |S| = |(y^x) * N| or |S|...
3
votes
1answer
77 views

Are there graphs for which A* cannot be admissible?

Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed ...
1
vote
0answers
20 views

Rabin Karp algorithm that uses bitwise AND

I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here. Here's the gist of it: ...
2
votes
1answer
42 views

Definition and example of search problem

I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me. WIKIPEDIA: In computational complexity theory and computability theory, a search ...
1
vote
1answer
33 views

Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week. For N ...
0
votes
3answers
52 views

Finding the point with minimum x-ordinate, lying between two y-ordinates

Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as ...

1
2 3 4 5
12