32
Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my ...
14
I will use the following simple sorting algorithm as an example:
repeat:
if there are adjacent items in the wrong order:
pick one such pair and swap
else
break
To prove the correctness I use two steps.
First I show that the algorithm always terminates.
Then I show that the solution where it terminates is the one I want.
For the first point,...
11
We first observe the following: There is an optimal cover $C$, and no leaf is in $C$. This is true since in any optimal cover $X$ you can replace all leaves in $X$ with their parents, and you get a vertex cover which is not larger than $X$.
Now take any optimal cover $C$ that does not contain leaves. Since no leave is selected, all parents of the leaves ...
8
It would be nice if you stated the problem. I assume that you have $n$ items $x_i$, each having profit $p_i$ and weight $w_i$. You want to maximize your profit under the constraint that the total weight is at most $W$. For each item $x_i$, you are allowed to put any fraction $\theta \in [0,1]$ of it, which will give you profit $\theta p_i$ and weight $\theta ...
8
The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.
...
8
Your algorithm makes the wrong choice between the following two paths:
5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$.
A single channel with a reliability of 8%, weight ${1 \over 0.08} = 12.5$.
7
The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha < 1$. These lecture notes (Claim 2) show that
$$ p_1 + \cdots + p_{k-1} +...
7
In simple words, an algorithm is normally considered "greedy" if
it builds solutions step by step without backtracking
in each step it picks what's best in the current state.
To learn more about it, check this pdf out.
The animated gif above illustrates a greedy algorithm for finding the path that adds up to the biggest number.
It does so by choosing ...
7
You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\times 2$, $2 \times 5$. Your algorithm first multiplies the first two at a cost of $4$, and then multiplies the remaining matrices at a cost of $20$, to a total of $...
6
Here is some Python code that should implement Greedy Set Cover in linear time:
(Warning, it empties the input sets during the processing!)
from collections import defaultdict
F = [set([1,2,3]),
set([3,4,5,6]),
set([2])]
# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
for a in S:
...
6
The running time of your algorithm is at most $N (N-1) (N-2) \cdots (N-K+1)$, i.e., $N!/(N-K)!$. This is $O(N^K)$, i.e., exponential in $K$.
Justification: There are $N$ possible choices for what you put into the first blank, and in the worst case you might have to explore each. There are $N-1$ choices for the second blank, and so on. You can draw a tree ...
6
There is a simple dynamic programming algorithm. Root the tree at some arbitrary vertex. For each subtree, compute the optimal dominating set (a) with the root, (b) without the root.
6
Greedy algorithm can't help in that case. And it couldn't be compared with both fractional or 0-1 knapsack problems. The first could be resolved by greedy algorithm in O(n) and the second is NP.
The problem you have could be brute-forced in O(2^n). But you could optimize it using dynamic programming.
1) Sort intervals by start time.
2) Initialize int[] ...
6
Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of priority algorithms formalizing the notion of greedy algorithm. Such a theory can be used to analyze what greedy algorithms cannot do.
Sometimes greedy algorithms ...
6
Overview of the problem
If you takes teenagers as vertices of a graph, and have an edge
whenever the two teenagers are compatible. This gives you an
undirected graph, and what you need is a Hamiltonian path in this
graph (a path that contains every node exactly once). Maybe searching
the web on this abstract version of the problem will yield more
...
6
It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic algorithms) being only one of them. That said, I have a positive answer and a negative answer for you.
Positive answer. Consider the problem of maximizing a ...
6
The starting point is the trivial random algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $1/4$ approximation.
We can derandomize this algorithm using the method of conditional expectations. Arrange the points in order: $1,\ldots,n$. At step $i$, we ...
6
If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.
But there is an 8 blocks solution (on the right).
The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.
Repeating the search in different directions will not ...
6
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 ...
6
There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued ...
5
One could implement this in O(nlogn)
Steps:
Sort the intervals based on end time
define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn
define d[i] = max(w(i) + d[p(i)], d[i-1]).
initialize d[0] = 0
The result will be in d[n] n- the number of intervals.
...
5
The idea of the backtracking algorithm is simple, though somewhat cumbersome to express. Perhaps it's easiest to explain it working through the example in the question. We start by putting $T_1$ on chair 1. We then put $T_2$ on chair 2. Then we put $T_3$ on chair 3, and we discover a conflict. So we backtrack, replacing $T_3$ with the next available student. ...
5
Your understanding is completely wrong: what you describe is known as hill climbing or gradient descent in the continuous case, and local search in the discrete case.
The best way to understand what greedy algorithms are is by an example. Consider the following optimization problem:
Given a set $S$ of positive integers and a number $n$, choose a subset ...
5
Greedy algorithms can be used whenever you can think of the solution to the problem being reached in steps. The strategy is then just to choose the next step that looks best in some (usually simple, "local") sense, without ever undoing a step and trying an alternative path.
The classical example is finding a minimal cost spanning tree of a graph. One ...
5
Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use.
There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes ...
5
Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating.
Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ ...
5
Thanks for the edit! This isn't vertex cover; it's something different.
There are simple algorithms for this problem. Decompose the graph into a dag of strongly connected components. (The dag is sometimes called "the metagraph".) Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one ...
5
Suppose that numbers are $x_1, \ldots x_{2n}$, and let us rename them as $a_1, \ldots a_n, b_1, \ldots, b_n$, where $a_i \geq b_j$ for any $i, j$, $a_1 \geq a_2 \geq \ldots \geq a_n$, and $b_1 \leq b_2 \leq \ldots \leq b_n$. In this notation, the suggested optimum solution is $(a_1, b_1), \ldots (a_n, b_n)$.
Given some arbitrary pairing, let us show we can ...
5
You are on the right track.
It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.)
Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths.
Let the ...
5
The greedy algorithm is optimal.
The simple observation is that any optimal $k$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents.
Given an $n$-digit number $A=a_{n-1}a_{n-2}\cdots a_1a_0$, where each $a_i$ is a digit, let $a_t$ be the rightmost digit of $A$ such that $a_n, a_{n-1}, \...
Only top voted, non community-wiki answers of a minimum length are eligible
