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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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} = \...
user avatar
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$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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), (...
user avatar
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 ...
user avatar
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 ...
user avatar
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.) ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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$-...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar

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