Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Why are search problems assumed to have the structure of "find a path in a graph"?

You are completely right: The problems we call search problems are typically problems that can be modeled as a graph problem. The general gist of it is that there are "states", "...
• 16.4k

### Why are search problems assumed to have the structure of "find a path in a graph"?

There are at least two meanings of the word "search problem". In one context, we use the phrase "search problem" to refer to searching for paths in a graph, or making a sequence of ...
• 160k
Accepted

### Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word. e.g. 3 SAT: (a,b,-c) && (-b,c) => pairs: (a,-a), (...
• 2,521
Accepted

### What is a search problem?

A problem is a search problem if there's an algorithmic way to verify the answer. In particular, let $V$ be any algorithm that takes two inputs and always terminates. Then the following is a search ...
• 160k

### Does White never lose in Chess if Chess is solved?

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed). Now it's obvious that White has a strategy ...
• 30.4k
Accepted

### Difference between cost and the heuristic function in A* search

Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image. But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "...
• 103
Accepted

### Does White never lose in Chess if Chess is solved?

This is unknown at the time of writing. Further, according to solving chess on Wikipedia, no resolution is expected in the near future.
• 22.6k

### Non-quadratic search for specific difference between elements in sorted array

I know of two. Sort the numbers, then walk 2 pointers from opposite ends towards each other, moving the left pointer rightward whenever the difference of the pointed-to elements is too small, and the ...
• 5,479
Accepted

### 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?

The google indexing and search is run in parallel using a map-reduce algorithm. As the number of pages to index expands, so does the number of computers that google uses for the task. Currently ...
• 1,080

### Extend binary search

Your problem is known as group testing. An essentially optimal algorithm for your problem is Generalized binary splitting. There are also pretty good non-adaptive algorithms (such algorithms fix all ...
• 277k

### Better algorithm for aggregating data from various LDAP systems

Your algorithms seem fine. I don't think you need better algorithms; I suspect what would help most is more on the engineering and implementation side. At a high level, I would say that your design ...
• 160k

### Black-box combinatorial optimization problem over permutations

In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force. If f has no structure, no properties, no regularities, ...
• 160k
Accepted

### Is graph search of shortest (optimal) path an instance of optimisation?

Although I'm not sure what you're calling 'optimisation', I can tell you that both Dijkstra's algorithm and BFS are not some form of searching a solution space. If they were, they would start with an ...
• 8,248
Accepted

### Search vs planning in artificial intelligence

Short answer is "Yes". Long answer is "No": As far as I am concerned the difference is limited to a specific author/lecture: (to the best of my understanding of the slides) The author of the linked ...
• 151

### Does White never lose in Chess if Chess is solved?

Maybe it is worth mentioning why some kind of reasoning like White has a winning strategy because everything black does, white could have done before. does not work. You might already be familiar ...
• 1,623

### $O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

A two-stage binary search works. First, for the purposes of this search define $0$ to be greater than any positive integer. Then, let $l = 1$ and $h = 2$ and: While $A_h \leq x$ let $l \leftarrow h$ ...
• 13.6k

Yes. Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$. Here is a corresponding decision problem: given $x$ and $... • 160k 2 votes ### How to find long trails in a multidigraph Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that a cycle of edges can be traversed a number of times equal to the minimum multiplicity of ... • 5,479 2 votes Accepted ### Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)? Graph canonization is well-studied, and there are sophisticated algorithms for it; see https://en.wikipedia.org/wiki/Graph_canonization. The standard answer is to use existing, well-tuned software, ... • 160k 2 votes ### How to find time complexity of Breadth First Search for this tree? It's true, time complexity for a single tree doesn't make sense. Aysmptotic notations are used to get bounds of how the algorithm scales in terms of its input size. The usual time complexity for BFS ... • 1,024 1 vote ### Why is a regex search less efficient than a normal search? "Linear scan" probably means the search can't backtrack. This guarantuees an O(n) complexity for the search. With backtracking it's possibly to get cases of exponential complexity. You might ... • 462 1 vote ### Question regarding the assumptions of the No-Free-Lunch-Theorem for Search I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point$x \in \mathcal{X}$through$f$would implicitly add$(x,f(x))$to the histogram$d$. For ... • 156 1 vote ### The best approach to search for closest object in hash map holding arraylist without changing data structure If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree ... • 764 1 vote ### Need help with adding elements to hashtable with linear probing It is the hash function h(k) that determines the position. They don't specify the hash function, but instead they give the value to which h(k) evaluates for both tables. The hash function is usually a ... • 111 1 vote Accepted ### Is Google search personalized? I asked Google about that, and the second result was: Google personalizes search results even when youâ€™re logged out, new study claims From there: Google says it still personalizes for location ... • 138 1 vote ### Fastest algorithm to find whether a list contains a word? If you are given an unordered list and asked to test whether just one item is in the list then a sequential check of each item in the list is the best you can do. If you want to carry out multiple ... • 1,589 1 vote ### Finding$k$-th element in prefix of size$i\$

I misunderstood the original premise that A does not need to change. If you want a solution for that, a good one is to just apply the worst-case linear time ...
• 235
1 vote
Accepted

### Kth smallest element in an arra

You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.
• 22.6k
1 vote

### Heuristics vs meta-heuristics vs hyper-heuristics?

Defining meta-heuristics as "heuristics designed to find, generate, or select a heuristic" seems too broad. A meta-heuristic is commonly understood as an algorithmic template that defines how ...
• 610

Only top scored, non community-wiki answers of a minimum length are eligible