# Tag Info

### How to prove greedy algorithm is correct

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 ...
• 164k
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
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

### 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 ...
• 278k
Accepted

### set with maximum sum consisting of mutually co-prime numbers

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-...
• 31.4k

### 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 ...
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 ...
• 164k
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 ...
• 278k
Accepted

• 39.1k
Accepted

• 56

### 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
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
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
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,553

### 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 ...
• 996
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
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.4k
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 &...
• 278k

### 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
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,237
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

### 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
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
Accepted

### How is Dijkstra's algorithm related to breadth first search(BFS)?

Yes the shortest path trees produced by djikstra's and BFS are identical in the case where the graph edge weights are represented by hop counts or in other words all the edge weights are 1 . Multiple ...