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
2answers
39 views

Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ...
4
votes
0answers
34 views

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
1
vote
1answer
28 views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
0
votes
0answers
10 views

SMA*+: What if a removed node gets re-generated via another predecessor?

One last question came to me while reading the paper on SMA*+ about setting the $f$-cost of nodes being re-generated. Well, first, it looks like the part of the algorithm where we set the predecessor ...
2
votes
0answers
17 views

SMA*+: Usefulness of culling heuristics

The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost). In the benchmark they use a culling heuristic equal ...
2
votes
0answers
15 views

SMA*+: f-cost estimation of re-generated nodes

I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
1
vote
1answer
22 views

Is this a good way to arrange data in a tree?

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes. As binary search trees have numbers greater than the root node on the ...
0
votes
0answers
43 views

Create a data structure with D-SUCCESSOR running in $O(1)$

Given an integer $d$, I need to devise a data structure $S$ with the following actions: BUILD(S): build the data structure $S$ from $n$ elements in $\Theta(n\lg{n})$ INSERT(S, k): insert a new ...
3
votes
0answers
76 views

Remove a subsequence from a string and append it at the end

Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
0
votes
1answer
34 views

Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$

I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$...
0
votes
1answer
22 views

List the lengths of all the prefix-suffixes in $O(n^{1+\epsilon})$ time

A proper prefix of a string $s$ that is also equal to a suffix of $s$ is called a PS (prefix-suffix). Given a string $s$ of length $n$ is there an algorithm listing the lengths of all the PSs in $O(n^{...
1
vote
1answer
29 views

Parallel algorithm for finding the maximum in $O(\log \log n)$ time

With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is: If $...
1
vote
0answers
29 views

A beginner's question on programs that can search and calculate in very large sets

I am not in the computer science field and was looking for some guidance on books/papers/programs that allow me to learn how to design algorithms for problems that involve very large number of ...
0
votes
0answers
17 views

How to efficiently search a list of data structures with filtering support

I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like: ...
0
votes
1answer
54 views

Average time complexity of linear search

It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear). I have read ...
1
vote
1answer
70 views

How to do binary search on a path in a binary heap

I am trying to solve this question: Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in ...
1
vote
1answer
42 views

How do I solve a search problem on an infinite graph?

I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \...
1
vote
1answer
49 views

Is there a theorem that says when an array of numbers can be searched faster than linearly?

I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, ...
1
vote
2answers
75 views

Should your heuristic for an A* search algorithm be the same scale as your actual weights?

I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the ...
-1
votes
1answer
21 views

A very simple question about Admissible Heurisitcs

Given admissible heuristics f(s), g(s), h(s). It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I ...
1
vote
0answers
20 views

Searching for the underyling affine transformation in a ridge function

Quoting from Wikipedia: A ridge function is any function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ that can be written as the composition of a univariate function with an affine transformation, that is: $...
2
votes
1answer
102 views

Searching in sorted array with $O(\log n)$

Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows: Suppose array $A[1..n]$ consist of $n$ distinct integers that is ...
-1
votes
1answer
34 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
54 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
28 views

Iterative Deepening DFS for DAGs

Does Iterative Deepening DFS only guarantee the shortest path for DAGs, assuming a visited list is used to prevent infinite cycles? I can't seem to find any answers online specifically related to ...
0
votes
0answers
29 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
23 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
15 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
30 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
52 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
41 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
41 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
24 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
64 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
134 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
57 views

How can I get index of combination from element indices

An array of combinations is generated from two arrays, ...
2
votes
1answer
58 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
24 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
19 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
329 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
82 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
29 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 ...

1
2 3 4 5
13