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

### How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
Accepted

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

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

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

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 ...

### Correctness of the greedy algorithm

The example provided by Valentin Lorentz can be slightly modified to break your solution for one order of traversal: 1 0 0 1 0 0 0 0 0 0 0 0 You can build a ...

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

ε-greedy is just a way to promote exploration in Reinforcement Learning. I would not classify SARSA or Q-Learning as ε-greedy algorithms. The latter are very common reinforcement learning algorithms ...