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
votes
1answer
22 views

UCS and Dijkstra's algorithm do both of them give the minimal cost between two vertices?

i tried both algorithm to find the shortest path with minimal cost between two vertices,but most of the time Dijkstra gives a different path and the cost is smaller than the cost for the path UCS ...
1
vote
1answer
37 views

Minimal unsatisfiable core algorithm

Wikipedia says that There are several practical methods of computing minimal unsatisfiable cores. but I cannot find any. I suppose that “practical methods” means polynomial algorithms. Be careful, a ...
0
votes
0answers
18 views
0
votes
0answers
27 views

How to modify the following Dijkstra/ Uniform-cost search to return the result for all end points?

I know there is a lot of code out there that does this, but in particular, I'm trying to modify the following code to not just return the goal node/ one end point, but all endpoints. How do I go about ...
0
votes
1answer
15 views

How to split the array into two subarrays with the smallest sum difference?

Given An array of elements, all elements are positive (unsorted, but sorting is not a problem if required) The objective: To create two subarrays, so that ...
0
votes
0answers
12 views

Scheduling Repeating, Flexible Intervals with Restrictions on Overlap

I work in 52:17 work:break intervals, as there's some evidence showing it's an effective way to structure the day. However, meetings or planned breaks often require shifting that schedule, moving, ...
0
votes
1answer
25 views

Search for specific element in sorted array

Given sorted array $A[1..n]$. We want to find an element such that $A[i]=3i+2$ in $O(\log n)$(binary search). I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, ...
0
votes
1answer
24 views

If possible, use binary search to find an element in sorted array

Given sorted array $A[1..n]$, we want to find an element such that, $A[i]=i^2$,Can we use binary search to find such a element? My Attempt: initially, I read this link, but I can't understand the ...
1
vote
0answers
28 views

Cyclic finite scheduling algorithm

I have a scheduling problem with the following specifications: A single machine is used. $n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$. Each job can be executed several ...
0
votes
0answers
18 views

Search algorithm for multidimensional space with custom topology

First, let's start with the description of the problem in dimension 1: Let $T_0$ be a space with $n$ nodes organized in a tree structure, with $m$ of those nodes defined as target nodes. In this space,...
3
votes
1answer
60 views

Why do we use DAG rather than trees to represent search space of a search problem?

I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
1
vote
1answer
30 views

Determine saving moves for a checked king

In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and ...
0
votes
0answers
27 views

Cycles of a multigraph with a property on the edges

Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are ...
4
votes
1answer
45 views

Further papers or code on SMA*+?

I'm interested in the Lovinger and Zhang paper Enhanced Simplified Memory-bounded A Star (SMA*+). Are there any further papers on this algorithm or publicly-visible code (in any language) ...
0
votes
1answer
36 views

Algorithm chalenge: find minimum range to cover all houses with light

N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R? N is an array containing location of each house. K is ...
2
votes
1answer
30 views

Find dominated or subsumed linear inequalities efficiently

Problem statement Given a set of $N$ linear inequalities of the form $a_1x_1 + a_2x_2 + ... + a_Mx_M \geq RHS$, where $a_i$ and $RHS$ are integers. The inequality $A$ dominates or subsumes inequality $...
1
vote
1answer
31 views

How does node expansion work in a graph for AI search?

I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city ...
0
votes
0answers
21 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 ...
1
vote
0answers
57 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
116 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, ...
2
votes
1answer
41 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
18 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
76 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
13 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
78 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
22 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
16 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
32 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. ...
0
votes
0answers
30 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 ...
0
votes
3answers
65 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
38 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
20 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
47 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
39 views

Extending a solution in backtracking

Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm: ...
1
vote
1answer
86 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
30 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
57 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
145 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
42 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
61 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
32 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
33 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
57 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 ...

1
2 3 4 5
12