Questions tagged [search-problem]

A class of computational problems. Where decision problems call for a yes-or-no answer, search problems are looking for an object satisfying a certain property.

135 questions
Filter by
Sorted by
Tagged with
59 views

Can a Turing machine quickly move to any position of a large string?

Note this question was originally asked on Theoretical CS Stack Exchange, but it is not a research level question so it is being closed, and I am asking here instead. Suppose we simulated a Turing ...
• 119
1 vote
19 views

1 vote
350 views

Graph traversal problem touching every node exactly once

Is there a name for the problem: Suppose you have a connected, undirected graph; find a path that touches every node exactly once. This is basically the complement of the Hamiltonian Path problem, ...
• 143
149 views

Definition and example of search problem

I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me. WIKIPEDIA: In computational complexity theory and computability theory, a search ...
2k views

Algorithm to create dense style crossword puzzles

I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
• 101
31 views

Recover a matrix with minimum number of queries

Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob ...
• 53
27 views

Transits directions search

Data Description : A database consisting of many Transits. Each transit has its own Path (both forward and backward), and each path has a set of Stops. Each stop consists of the position and the ...
284 views

Should a prefix tree (trie) node store only a single character or a string?

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters. Storing strings is for sure more space-efficient and ...
• 2,300
1 vote
33 views

Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)

Gradient descent sometimes works better than simulated annealing and vice versa. Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one ...
• 3,464
1 vote
65 views

Finding lost bottle (algorithm problem)

The question is as follows: A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on ...
68 views

How to maximize $f$ while minimizing $g$ at the same time?

Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly. The problem is as follow: let's assume that we have a set of elements $A$. And, we have two ...
32 views

A data structure for efficiently finding nodes relative to other (ex: if a node is earlier in a list than another node)

Suppose we have N elements, which we'll treat as a simple object. Is there a data structure I can use that will allow me to see which node appears earlier based on ...
• 163
117 views

Finding maximal cardinal independent set given oracle

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the ...
• 23
55 views

• 211
179 views

How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
• 115
1 vote
32 views

fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
• 327
1 vote
668 views

Efficient way to find matching date ranges?

We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate ...
• 121
172 views

String Search - how to find the "most" accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
1 vote