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
1answer
27 views

Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
2
votes
1answer
49 views

Why is IDA$^*$ faster than A$^*$? Why does IDA$^*$ visit more nodes than A$^*$?

I used IDA$^*$ for optimally solving the 8-puzzle and my friends used A$^*$ for it too (with same manhattan distance heuristic). I calculated the average running time and number of nodes of my ...
1
vote
2answers
44 views

What algorithm to use for this problem?

I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it ...
1
vote
1answer
22 views

Why increasing the beam width does not necessarily improve the beam search solution?

Normally increasing the beam width is a better solution, but I have read that this is not necessarily true, is there any proof of this?
3
votes
3answers
131 views

How to find a path that connects all the dots in the matrix?

I have a matrix that consists of 0, 1, 2. 0 - dot. 1 - block. 2 - start dot (initial position in the path). I have to create a path from the start dot, that connects all the dots in the matrix and ...
0
votes
0answers
17 views

Counting nodes within K distance from set of given nodes in a tree [duplicate]

I was going through this article https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/ The question says: Given an undirected tree with some marked nodes and a positive ...
0
votes
1answer
20 views

Searching for points near given point in a multidimensional space

I want to search many times, not identical elements but similar, for something a similar image or fingerprint without having to search the whole space. When I have a 1D case I sort it first. For 2D I ...
0
votes
1answer
22 views

runtime to a BFS flood-fill with multiple centres?

If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding ...
2
votes
0answers
36 views

Reaching local optimality in simulated annealing

I am currently reading about local search techniques. I understand that local search algorithms tend to get stuck in local optima and therefore usually do not find globally optimal solutions. Thus, ...
2
votes
1answer
78 views

Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is: ...
2
votes
2answers
26 views

Different ways to generate a big number with some small numbers

Imagine we have a set of numbers $\{x_1,x_2,\dots,x_m\}$. We want to compute the different ways to make a big number $P$ by those small numbers. For example, if $P = 5$ and we have $\{1,2,3,4,5\}$ we ...
2
votes
1answer
44 views

Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations

So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station ...
2
votes
1answer
31 views

number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
2
votes
1answer
38 views

reverse string to pattern matching

I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.: Patterns: ...
0
votes
1answer
28 views

Search Algorithm with two areas of solutions [closed]

I need some help with a problem. I have currently an algorithm. This algorithm gives me a true or false for a variable which I need to iterate( e. g. From 0 to 100} . Till now I solved it with a brute ...
2
votes
1answer
33 views

Proof on lower bound of search in unsorted array with information theory?

I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound ...
2
votes
1answer
32 views

Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?

This post and this post indicate that when the dimensionality gets higher, KDTree gets slower. Per scikit-learn doc, the KDTree becomes inefficient as D(dimensions) grows very large (say, $D>20$): ...
0
votes
2answers
57 views

Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...
0
votes
1answer
28 views

Grassfire vs BFS

Expanding on this question : Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm? What are the differences between grassfire and BFS? I'm surprised grassfire (supposedly) ...
0
votes
2answers
31 views

Coefficients in cost function in A-star

I'd like to expand on this question : https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn Dijkstra's algorithm uses cost function $f(n) = g(n)$ whereas A* uses cost ...
0
votes
1answer
23 views

Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more ...
0
votes
1answer
16 views

How do we determine whether a heuristic is better than another in A* search Algorithm?

I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics. Currently, I explored Manhattan and Euclidean distances. ...
0
votes
1answer
49 views

A* algorithm example explained

I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a ...
3
votes
2answers
47 views

Compute highest-scoring segmentation

I have the following problem: There is a "clean" sequence of sequences, say: clean = [ [1, 2], [3], [4, 5] ] And a "noisy" sequence which is not ...
1
vote
0answers
21 views

How to implement a faceted search efficiently

I know Solr and the likes are able to provide faceted search out-of-the-box. But how is faceted search actually implemented technically? How are those engines able to efficiently search for items ...
0
votes
0answers
35 views

Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
0
votes
0answers
38 views

Finding an substring in an infinite sequence

I'm trying to find a substring in an infinite sequence of numbers (Similar to Substring in a infinite sequence of numbers) and am a little stuck on improving my algorithm. I know there is already an ...
2
votes
1answer
21 views

efficiently minimizing quasiconvex function

The problem is as follows: given black box access to a strictly quasiconvex (or unimodal) function $f$ on an interval, say [0, 1], query $f$ repeatedly at various points to find a subinterval ...
1
vote
1answer
81 views

Algorithm to find repeated patterns in a large string

For optimization purposes I'm trying to analyze a large list of executed program commands to find chunks of commands that are executed over and over again. This problem is similar to searching ...
0
votes
2answers
61 views

How to do a reverse topological sort using depth first search?

I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
0
votes
0answers
24 views

Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names. Some ground-rules: we're traversing in ...
2
votes
2answers
177 views

What is the meaning of uniform distribution of elements in an array?

I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
-1
votes
1answer
38 views

Recurrence Relation of Ternary search and the number of comparisons with binary search

i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
0
votes
0answers
25 views

What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other. Also as an aside, if anyone ...
1
vote
1answer
36 views

I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example): Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between ...
9
votes
1answer
735 views

Why say that breadth-first search runs in time $O(|V|+|E|)$?

It's often stated (e.g., in Wikipedia) that the running time of breadth-first search (BFS) on a graph $G=(V,E)$ is $O(|V|+|E|)$. However, any connected graph has $|V|\leq |E|+1$ and, even in a non-...
1
vote
0answers
32 views

Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
0
votes
0answers
86 views

Minimum number of moves to reach a grid point by modified knight in variant chessboard

I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://...
2
votes
1answer
133 views

How to search an almost sorted array faster than O(n) time?

Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1. Develop an efficient ...
0
votes
0answers
16 views

Matching algorithm to find pattern match in rectangles

I am trying to write an algorithm to find the best (if any) match for a pattern of rectangles. Essentially, given a database of three different arrays of rectangles. The color is irrelevant here, it's ...
1
vote
0answers
23 views

Structure Preserving Continuous Hash Function

This question was originally posted on super user, but redirected here based on some suggestions. I am completely new with computer science, and not only recently did I run into the notion of hashing....
5
votes
1answer
88 views

Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the ...
1
vote
1answer
96 views

Space complexity of breadth-first search

I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor. ...
1
vote
0answers
30 views

Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
0
votes
0answers
34 views

Given an array of sum and an array how can to find if all the sums are possible using distinct elements of array?

example: if we have array of int as 1 2 3 and sum array is given 3,3 we can form this sum as {1,2} and {3} if the sum array is 5 3 we can not create the sum array, we can for {2,3} but not enough ...
1
vote
0answers
56 views

Multi Agent Sokoban Solvers state of the art

I am researching into coding a solver for a variant of the Sokoban game with multiple agents, restrictions (eg. colors of stones, goals) and relaxations (push AND pull possible etc.) By researching ...
0
votes
2answers
63 views

Karp-Rabin - what is the input for the worst case time complexity?

I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet: String "AAAAAAAA" ...
1
vote
1answer
131 views

Shortest Path in Layerwise Complete Graph

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
2
votes
1answer
127 views

Understanding Correctness of Bidirectional Dijkstra

I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10: https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%...
0
votes
1answer
25 views

How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step

Consider the following matrix: Input: The entire list of coordinates ranging from (0,0) to (4,4). A list indicating certain coordinates which cannot be used to generate a path reached. So, each ...