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,511
7
votes
Accepted
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
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 ...
- 39.1k
6
votes
A general algorithm for greedy algorithms
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 ...
- 279k
6
votes
Accepted
Split a String Into the Max Number of Unique Substrings: O(n^2) solution explanation (Leetcode 1593)
I see no reason why it should work, and in fact it doesn't: it returns 4 for aabaaabaa, missing a ab aaa b aa. (I found this by ...
- 2,275
5
votes
Accepted
Vertex cover algorithms for directed graphs?
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 ...
D.W.♦
- 166k
5
votes
Accepted
Maximum cut using a 1/2 approximation greedy algorithm
Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the ...
- 279k
5
votes
Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints
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 ...
- 151
5
votes
Accepted
Greedy algorithms: Minimum sum number pairing
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 ...
- 205
5
votes
Accepted
Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal
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....
- 39.1k
5
votes
Accepted
N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm
Can you see why $\max((-2)+5, 3+4) \lt \max(-2+3, 4+5)$?
The reason is simple. Because on the right hand side, the maximum number 5 is not paired with the minimum number.
Let the numbers are $a_1\...
- 39.1k
5
votes
Accepted
Hamiltonian path greedy and anti-greedy algorithms
No.
In fact, we can prove the following stronger proposition.
Claim. Given a complete weighted undirected graph, a run of the greedy algorithm on it and a run of the anti-greedy algorithm on it, the $...
- 39.1k
5
votes
Accepted
Dynamic programming: optimal order to answer questions to score the maximum expected marks
First, if any $p_i=0$, then immediately throw it away since you're guaranteed to lose. If any probability is $1$ then immediately ask it! (after all why risk not getting the reward when you're ...
- 623
4
votes
Coin Change Problem(Greedy Algorithm)
For the set of coins (2,3,11). $\frac{3}{2}<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to ...
- 1,612
4
votes
Accepted
Dynamic Programming vs Greedy - coin change problem
A dynamic approach would say that "x$ can be made out of change using, as the first coin, v1 or v2 or v3 ... or vn" and then build a table so that the second coin would be v1 or v2 or v3 ... or vn + ...
- 56
4
votes
How to prove greedy algorithm is correct
Jeff Ericson in his "Algorithms" states three conditions:
Greedy choice: There is an optimal solution that includes the choice the algorithm makes.
Inductive structure: The smaller ...
- 14.1k
4
votes
Accepted
How does the nearest insertion heuristic for TSP work?
I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works:
We're looking to construct a cycle $C$ containing all the nodes of our problem....
- 146
4
votes
Accepted
Correctness proof for greedy algorithm based on ratio
The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements".
Instead of proving that an algorithm produces the optimal solution, this strategy ...
- 39.1k
4
votes
Accepted
Gas Station problem : Fixed path variation
The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank).
The proof is pretty much the ...
- 2,542
4
votes
Accepted
Why this greedy algorithm fails in rod cutting problem?
Because a local maximum is not always a global maximum.
The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ...
- 3,563
4
votes
Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?
The formalized problem here is selecting the minimum number of points such that for each temperature interval $\ell_i\in L$ we have at least one point that covers it. Let each interval $\ell_i$ be ...
- 1,041
4
votes
Accepted
Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"
The adjective "maximum-weight" should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.
To be fully clear, item (1) should have been the following.
...
- 39.1k
4
votes
Accepted
Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?
In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.
It is obviously ...
- 31.6k
4
votes
Accepted
Expected behavior of an algorithm to minimize rankings
Finding the minimum matching is known as the assignment problem, and it has efficient solutions.
Your exact problem has been considered by Parviainen, Random assignment with integer costs — it's his &...
- 279k
4
votes
How to determine the approximation factor for greedy vertex cover algorithm?
The approximation factor can be $\Omega(\log n)$.
Consider a bipartite graph $G$ with a set $S_L$ with $n$ nodes on the left side. Also consider a collection of sets $S_{R,1},S_{R,2},\dots,S_{R,n}$ on ...
- 1,962
4
votes
Accepted
Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?
Your algorithm is correct. The following is its proof of correctness.
Let $S_1$ and $S_2$ be the optimal partitions of $S$. Let their medians be $m_1$ and $m_2$. Let the maximum element is $M$ that ...
- 6,267
4
votes
Accepted
Greedy filling unit intervals
The greedy algorithm
Let $result$ be an empty set and let $last\_interval$ be none.
For each $num$ in sorted $X$:
If $num$ is not covered by the last interval:
let $last\_interval$ be the interval ...
- 39.1k
4
votes
I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems
I don't think this is entirely a matter of opinion like the other commentor has said (though they are right, that it can be a bit opinionated or subjective, everyone finds different things easier/...
- 330
3
votes
Vertex cover algorithms for directed graphs?
The problem you're describing sounds more like a Dominating Set style problem to me (vertices covering vertices, Vertex Cover is vertices covering edges), but because you allow the dominating vertex ...
- 18.3k
3
votes
Proof that the length of the largest ascending subsequence is the number of decreasing subsequences
You should read up on Patience Sorting first; that's a greedy algorithm to calculate a partition into nonincreasing subsequences (described there as piles of cards). Moreover, the number of ...
- 131
3
votes
Accepted
Minimum difference between two subsets of an array of integers
My algorithm got proven wrong by Ricky Demer in a comment to the OP, with the example [2,2,3,3], for which we have a suboptimal output ({2,2} and {3,3} instead of {2,3} and {2,3}, for those wondering)....
- 201
Only top scored, non community-wiki answers of a minimum length are eligible