Questions tagged [search]
The search tag has no usage guidance.
51
questions
0
votes
1
answer
128
views
How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?
I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.
What ...
- 225
0
votes
1
answer
42
views
maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$
Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(...
- 101
0
votes
0
answers
89
views
Find a range of values to subset the rows to maximize the objective function
I have searched around for some time but couldn't find a similar example to my problem.
It looks common enough that I would expect it to be solved. It lies between search and optimization/regression.
...
0
votes
2
answers
110
views
Efficient search in a permutation
Let $S$ be an array of length $n$ containing a random permutation of numbers from $0$ to $n-1$. What is the most efficient (in expectation) algorithm for finding the location of a given number $k$ in $...
2
votes
1
answer
566
views
Difference between cost and the heuristic function in A* search
Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
- 123
0
votes
0
answers
129
views
Frontier steps for greedy best first search
I've been asked to list the frontier steps for greedy best-first search for the graph in the picture below.
I've attempted to recreate the algorithm in Golang, as shown below:
...
- 123
1
vote
0
answers
65
views
Unusual version of a binary search algorithm
For one dimensional, continuous binary search most effective algorithm would remember boundaries.
For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
2
votes
1
answer
132
views
Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking
I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article.
...
- 131
-1
votes
1
answer
484
views
How to find time complexity of Breadth First Search for this tree?
This is what I got from another forum, but honestly doesn't make much sense to me.
Time complexity for a single tree doesn't make a lot of sense, since the function in the big O notation might be ...
1
vote
1
answer
66
views
Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?
Let suppose we order the nodes first by degree (in + out), to get a list of node structures:
...
- 495
2
votes
2
answers
455
views
Searching through an unsorted array with a better than O(n) complexity?
This question kind of puzzled me, it was presented as a homework assignment for 2nd year undergrads and one of them approached me in case I could give him some pointers, but the problem is I couldn't ...
Kao
0
votes
1
answer
238
views
Why is a regex search less efficient than a normal search?
On a lot of messaging applications, regex search isn't enabled due to a "linear scan". I'm not sure why this is the case. Can someone explain?
- 161
2
votes
1
answer
202
views
How to find long trails in a multidigraph
I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
- 201
1
vote
0
answers
45
views
Given consumer grade hardware,what is a reasonable upper bound for size of search space?
There's a gacha RPG I'm trying to get better at.
I estimate there are about 10^15 states for the 3 opening rounds of a match for which I am trying to evaluate damage output.
The equations themselves ...
0
votes
1
answer
32
views
Question regarding the assumptions of the No-Free-Lunch-Theorem for Search
I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the ...
- 156
0
votes
0
answers
10
views
Finding the point with smallest x-ordinate between two given y-ordinates [duplicate]
Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the ...
- 131
0
votes
2
answers
235
views
$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right
Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it.
All remaining cells on right are filled with zeros.
For example, $m=10, n=4$:
$$A = \{...
- 1
1
vote
1
answer
229
views
Can all types of computational problems be modeled as decision problems?
Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
- 345
0
votes
2
answers
597
views
The best approach to search for closest object in hash map holding arraylist without changing data structure
Imagine the game handled server sided, don't think of a visual problem.
Given a game 2D map, with size of n * n.
The game contains objects (such as door, wall, a table).
Each tile position (x,y) can ...
- 1
0
votes
1
answer
163
views
Need help with adding elements to hashtable with linear probing
Here is an example problem which I have having trouble figuring out. The red text is the answer.
I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
0
votes
1
answer
50
views
Pagination of results from different sources merged by a unified scoring function
Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\...
- 227
-3
votes
1
answer
43
views
Is Google search personalized? [closed]
Pardon me if this is a very naive question.
Suppose I search for something on Google and my next-door neighbour searches for the same thing (on Google) at the same time. Do we get the same or ...
- 117
3
votes
3
answers
405
views
Does White never lose in Chess if Chess is solved?
If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
- 27
1
vote
0
answers
17
views
Is there a high-level framework from which all known search and optimization algorithms can be derived?
The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations.
I'm mainly talking about ...
0
votes
2
answers
2k
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 ...
- 131
2
votes
1
answer
84
views
Extend binary search
There is a way for finding K entries of N given entries using a binary search?
I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint.
The ...
- 121
2
votes
1
answer
1k
views
Search vs planning in artificial intelligence
I'm studying artificial intelligence following the Russell & Norvig book.
We did a search and planning part that for me is the same (at least on the representation).
I'd like to know what is the ...
- 262
3
votes
1
answer
79
views
Finding $k$-th element in prefix of size $i$
Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
- 1,408
1
vote
1
answer
82
views
Kth smallest element in an arra [duplicate]
What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
- 529
1
vote
1
answer
4k
views
What is a search problem?
I'm looking for a formal and broad definition.
Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a ...
- 127
1
vote
0
answers
63
views
An algorithm for getting the position index
Consider these two equation.
$$
m_1+m_2+m_3+m_4 = M_m\\
|m_1|+|m_2|+|m_3|+|m_4| = N_m
$$
where $\{m_i,M_m,N_m\}\in \mathbb{Z}$.
Given the value of $(N_m,M_m)$ we can find the different solutions ...
- 111
4
votes
1
answer
833
views
Heuristics vs meta-heuristics vs hyper-heuristics?
The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic".
The wikipedia page on hyper-heuristics states that they are "heuristic ...
- 165
2
votes
1
answer
2k
views
A* Search Algorithm Implementation with Priority Queue
I've got a question regarding the A* search algorithm's implementation.
According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
- 23
2
votes
0
answers
51
views
B/B+ trees without leftmost pointers
In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers:
node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ]
Now suppose that I ...
- 121
0
votes
1
answer
195
views
Steps to create a heuristic for solving a problem
I am completely new to AI and doing self-learning to acquire this knowledge.
I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a ...
- 3
2
votes
1
answer
77
views
How does topic or tag suggestion algorithms work?
I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings.
For ...
- 121
1
vote
1
answer
37
views
Better algorithm for aggregating data from various LDAP systems
I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like ...
- 215
1
vote
1
answer
300
views
Black-box combinatorial optimization problem over permutations
I am solving general black-box optimization problems like:
x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
- 103
1
vote
1
answer
44
views
Is graph search of shortest (optimal) path an instance of optimisation?
I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm.
I am not too familiar with graphs / trees ...
2
votes
2
answers
133
views
Non-quadratic search for specific difference between elements in sorted array
New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either ...
6
votes
1
answer
317
views
Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?
Definitions:
An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
1
vote
1
answer
2k
views
special case of best first search algorithms
I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/
- 11
7
votes
1
answer
424
views
What is the most recent comparison of signature files and inverted indices?
Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers ...
- 529
0
votes
0
answers
105
views
Algorithmic complexity of Sub-array with sum = target algorithm
Question: Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X
E.g: If array is [1, 3, 5, 18] and X = 8 Output: True, if X = 10, ...
- 390
0
votes
1
answer
709
views
Ski design usaco problem alternative solution
problem statement for SKICOURSE is this
Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow ...
- 111
1
vote
1
answer
118
views
Taking intersection in large search
As I understand, you can build the the word -> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once
...
6
votes
2
answers
3k
views
Understanding Levin's Universal Search
I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $...
- 91
10
votes
1
answer
944
views
Why Is KD-Tree-based Nearest Neighbor Exponential in K?
I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why.
What I'm looking for is a solid runtime-complexity ...
- 200
4
votes
1
answer
118
views
How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank?
I heard Google creates indexes of pages. Even then, the number of indexes goes with time. Why wouldn't this slow down the search?
- 43
2
votes
3
answers
120
views
Fast comparison with a tolerance
I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.
I want to do this by ...
user16034