14
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 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few ...
9
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 or not, how many local minima it has, and so on.
There is no good theory to know whether GA will work or not. Ultimately, all you can do is try it and see.
As ...
8
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 check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $...
8
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} = \frac{(b-a)(b+a+1)}{2}. $$
Given a factorization $2n = xy$, we can solve the system $x = b-a$, $y = b+a+1$. The result is $b = (y+x-1)/2$, $a = (y-x-1)/2$. So we ...
8
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 compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an ...
7
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$, and $m$? Now, given $n$, can you determine whether it is expressible as the sum of an odd number of consecutive integers?
7
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
or
The decision problem corresponding to Problem 2.1 is NP-complete, and the search problem is in FNP
Here the search problem is finding a clique of size $k$...
7
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 at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.
7
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 matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result.
If you don't want to assume this theorem, you ...
7
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), (b,-b), (c,-c).
words: (a,b,-c), (-b,c)
Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding ...
7
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 comparing $y$ with the size of the biggest $X$. You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute ...
6
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 Theorem 2.1 in:
Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (...
6
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.) Then you can't do better than to examine every edge. In particular, if there is any edge you have not examined, then an adversary could choose the length of ...
6
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 $b_1,\ldots,b_{n/2}$.
Repeat $k-1$ more times to get the minimum $a_{\min}$.
Let $L$ be the set of all $k$ elements which were compared to $a_{\min}$ and were ...
6
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 the graph explicitly", I mean that you don't necessarily need to create any new data structures. Every time your graph algorithm says "vertex", you can think "...
5
¡Nice question really!
The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because ...
5
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
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 makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and ...
5
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 ratio of sums can be made $\ge c$ if and only if there exists a set $S$ such that $\sum_{j \in S} a_{1j} - c a_{2j} \ge 0$. That's possible iff there exists $j$ ...
5
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 bomb for each clause, the red cables are connected to clauses/bombs that have positive literals belonging to that variable/lever and the green cables are ...
5
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
This can be solved in linear time with dynamic programming. Let $d_i$ denote minimum number of $a_i,\dots,a_n$ that must be cut to produce an alternating ...
4
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 then increment the counter for that particular 5-gram.
4
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}a+\sum_{i=0}^{k-1}i=ka+\frac{k(k-1)}{2}
$$
and so we must have
$$
n=k\left(\frac{2a+k-1}{2}\right)
$$
for some $a$ and $k$. If $k$ is even we require
$$
n=\left(...
4
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 of vertices and edges. We do that by going over all vertices $u$, check whether $u$ is reachable from $v$, and if so, increase the vertex counter by 1 and the ...
4
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 stops early, leaving the beginning part correct (in this case the first two elements) and the rest of the array in whatever partly-sorted state is most convenient....
4
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$-coordinate of the points (so the leaves contain the points, sorted from left to right). Augment the tree, so that in each node $t$ of the tree, you store a pointer ...
4
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 the goal.
Now, when considering the sliding-tile puzzle, the Manhattan distance can be shown to be an admissible heuristic function as it results from a ...
4
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 $x$ that maximizes $f(x)$", then consider the function $f(x) = \max_{y\in Y}g(y)$ such that $\max_{y\in Y}g(y)$ is hard to compute. The optimization problem is ...
4
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 indices.
The algorithm suggested works as follows. Perform a binary search on the array. At each iteration choose a middle element of the array; examine its ...
Only top voted, non community-wiki answers of a minimum length are eligible