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
2
votes
1answer
23 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
35 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
26 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
27 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
31 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
1answer
31 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
23 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
23 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
18 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
33 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
31 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
48 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
27 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
21 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
78 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
24 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
22 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
722 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
31 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
65 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
109 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
14 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
17 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
86 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
74 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
22 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
48 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
41 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
105 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
99 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
23 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 ...
2
votes
1answer
54 views

In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
1
vote
0answers
14 views

Probabilistic switching between breath-first and depth-first

I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and ...
3
votes
1answer
35 views

Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint?

Note: The input file is an excel file. However, I am only looking for help with the algorithm as I can then code it in VBA. I need to scan both columns (shown below) to find any number of column 1 ...
0
votes
1answer
25 views

Tree search returning parents and children

I've a flat structure where a node references its parent instead of children class Node(int Id, Node Parent, string Data); Given a list of all nodes, and a ...
0
votes
1answer
49 views

What are possible uses for cross, back and forward edges after the DFS visit?

The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles. What are other ...
3
votes
1answer
110 views

Search a sorted array that ends with zeros in O(log n) time

I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted. If I make a binary search including the 0's I get $O(\log(m))$. ...
4
votes
1answer
101 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
0
votes
2answers
40 views

Algorithm for searching in BST with only <

How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $<$ on the key type. The ones I can easily also requires $=$.
0
votes
0answers
17 views

best first search (lowest cost first search) time complexity [duplicate]

I'm working on a homework assignment directly related to this question: Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis Anyway it's ...
1
vote
1answer
263 views

Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
1
vote
1answer
153 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
5
votes
1answer
64 views

Word Problem over Finite Groupoids

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...