14
votes
Accepted
Algorithm for finding two smallest numbers in an array
If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 ...
- 1,681
9
votes
Should you use Genetic algorithm for an extremly large unstructured search space?
No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying ...
D.W.♦
- 141k
8
votes
Searching through a heap complexity
You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is ...
- 80.2k
8
votes
Accepted
Searching the space of permutations
Consider the following set of $n$ orders, which I give for $n = 6$:
$$
123456 \\
213456 \\
132456 \\
124356 \\
123546 \\
123465
$$
Hopefully the generalization to arbitrary $n$ is clear.
If you never ...
- 270k
8
votes
Accepted
Finding an element in a sorted array with at most three queries to larger elements
If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$
If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can ...
- 251
8
votes
Divide an integer into the sum of consecutive positive numbers
Here's an alternative way of viewing D.W.'s hint. Using the formula $\sum_{i=1}^m i = \frac{(m+1)m}{2}$,
$$ \sum_{i=a+1}^b i = \sum_{i=1}^b i - \sum_{i=1}^a i = \frac{b^2+b}{2} - \frac{a^2+a}{2} = \...
- 270k
7
votes
Divide an integer into the sum of consecutive positive numbers
Here's a hint: if $n$ can be represented as the sum of $2k+1$ consecutive integers, and if the middle of those consecutive integers is $m$, then what can you say about the relationship between $n$, $k$...
D.W.♦
- 141k
7
votes
Accepted
Does NP-completeness require to find the solution?
You are right that NP-completeness applies only to decision problems. What they mean by "Problem 2.1 is NP-complete" can be either
The decision problem corresponding to Problem 2.1 is NP-complete
...
- 270k
7
votes
Accepted
Choosing nonzero entries from an array so no pair in same row or column
The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation ...
- 270k
7
votes
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,376
7
votes
Are there any optimization problems in P whose decision version is hard?
No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves ...
- 80.2k
6
votes
Accepted
Can finding a witness be NP-hard even if we already know there is one?
TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist.
There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see ...
- 278
6
votes
Accepted
Find the central point in a metric-space point set, in less than $O(n^2)$?
No. You can't do better than $\Theta(n^2)$ in the worst case.
Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) ...
D.W.♦
- 141k
6
votes
Algorithm for finding two smallest numbers in an array
The optimal number of comparisons (not necessarily the fastest one) goes like this for $n = 2^k$:
Compare $a_1$ and $a_2$, $a_3$ and $a_4$, and so on. Store only the smallest of each pair in a list $...
- 270k
6
votes
Efficient algorithm to decide if a location is reachable
The problem you're trying to solve is exactly graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem.
By "you don't necessarily need to construct ...
- 80.2k
6
votes
Accepted
Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing
I'll describe two ways you could solve this problem. Either works. In some sense they are basically the same algorithm, just viewed from two different perspectives.
Dynamic programming algorithm
...
D.W.♦
- 141k
5
votes
Algorithm for finding two smallest numbers in an array
No, it's not optimal. Do you know an efficient way of finding the smallest number in an array? Knowing the smallest number, could you adapt that method to find the second smallest?
5
votes
Is there any strategy to brute force search?
The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely ...
- 22.1k
5
votes
Accepted
Maximize ratio of sums
There's a linear-time algorithm for this problem. Find the index $j$ that maximizes the ratio $r_j = a_{1j} / a_{2j}$. This $r_j$ is the maximum possible value of the ratio of sums.
Proof: The ...
D.W.♦
- 141k
5
votes
Accepted
Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?
Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time
We reduce 3-SAT to your problem.
We have a lever for each variable and a ...
- 739
4
votes
Divide an integer into the sum of consecutive positive numbers
Here's a $O(\sqrt n)$ algorithm. We want to find all length-$k$ expressions for which
$$
n=a+(a+1)+(a+2)+\cdots+(a+(k-1))
$$
Rearranging terms, we require
$$
n=\sum_{i=0}^{k-1}(a+i) = \sum_{i=0}^{k-1}...
- 14.6k
4
votes
Accepted
Efficiently count frequency of n-grams at start of words
There is a 11.881.376 times faster method. Instead of for every 5-gram looping over the entire dictionary, loop over the dictionary once, and for every word determine with what 5-gram it starts and ...
4
votes
Solving cycle in undirected graph in log space?
The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number ...
- 270k
4
votes
Algorithm for finding two smallest numbers in an array
Hoare's algorithm, which Wikipedia calls Quickselect, can find the $k$ smallest elements of an array in $O(n)$ time for any fixed $k$.
It is a modified Quicksort algorithm that sorts the array but ...
- 1,517
4
votes
Accepted
Efficiently locating the maximum value in interval over large amounts of data points
This can be solved with a balanced binary tree. Each such query can be answered in $O(\lg n)$ time.
Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-...
D.W.♦
- 141k
4
votes
Heuristics for the $n$-puzzle
First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to ...
- 3,383
4
votes
Accepted
Are there any optimization problems in P whose decision version is hard?
Maybe it depends on what it means by solving an optimization problem. If it is to find "how big is the biggest $f(x)$", then the answer is no (see the answer of @David Richerby). If it is to find "the ...
- 113
4
votes
Finding a local peak in an array in O(log N)?
To reformulate the question, there is the following problem: given an array of numbers, find an index in the array that is a local maximum, meaning the value at that index $\ge$ the values at adjacent ...
- 589
Only top scored, non community-wiki answers of a minimum length are eligible