Questions tagged [search]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-3
votes
1answer
34 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 ...
0
votes
0answers
19 views

Traversing/comparing tree structures with only parent references

Consider a tree structure with nodes containing references to only their parent. So, the root node's parent will be null. This tree represents a class hierarchy. The goal is to search such a tree for ...
3
votes
3answers
130 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?
1
vote
0answers
15 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
2answers
60 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 ...
2
votes
1answer
52 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 ...
1
vote
1answer
74 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 ...
3
votes
1answer
65 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
vote
1answer
33 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) $?
1
vote
1answer
357 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 ...
1
vote
0answers
52 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 ...
4
votes
1answer
140 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 ...
1
vote
1answer
449 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 ...
2
votes
0answers
23 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 ...
0
votes
1answer
50 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 ...
2
votes
1answer
69 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 ...
1
vote
1answer
23 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 ...
1
vote
1answer
216 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 ...
1
vote
1answer
35 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
2answers
83 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
1answer
270 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
1answer
1k 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.:/
7
votes
1answer
347 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 ...
0
votes
0answers
99 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, ...
0
votes
1answer
391 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 ...
1
vote
1answer
74 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 ...
5
votes
1answer
912 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 $...
8
votes
1answer
729 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 ...
4
votes
1answer
110 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?
2
votes
3answers
82 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 ...
2
votes
2answers
1k views

Why does an admissible heuristic mean A* is optimal?

An admissible heuristic never overestimates the cost to reach the goal. However, isn't that only the relative difference between heuristics for two different paths matter? Say we have optimal path A ...