# Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

26 questions
Filter by
Sorted by
Tagged with
23k views

### How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
5k views

### Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
1k views

### How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-...
85 views

### What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
454 views

### Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
1k views

### Minimal Spanning tree and Prim's Algorithm

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
26k views

### When can a greedy algorithm solve the coin change problem?

Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v. E.g. for the coinset 1,5,10,20 this gives 2 ...
10k views

### Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover). For each ...
523 views

### Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
408 views

### Greedy algorithm correctness proof for “Elegant Permuted Sum” (UVa 11158)

Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized. I found many ...
927 views

### Greedy algorithms: Minimum sum number pairing

Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair. I think the optimal pairing is obtained by sorting the original set, pairing the first element ...
2k views

### Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
146 views

### Greedy algorithm proof

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}. When we buy the products in pairs we get the product with lower ...
100 views

### Selecting optimal order of questions to minimize total time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
138 views

### Proof for This Greedy Strategy for Equalizing An Array

Recently the following problem was posed in a private coding competition at my workplace: An array $A$ is given that has only positive integers in it. The objective is to equalize the array in ...
353 views

### Proof of a greedy algorithm concerning “Buy and Resell Problem”

"Buy and Resell Problem" can be described in the following way: There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
750 views

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

Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have. Example. Let $n=10$, ...
4k views

### Matrix Chain Multiplication Greedy Approach

In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic ...
2k views

### Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some ...
109 views

### Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
316 views

### A greedy algorithm for the bottle filling problem

(There’s no need to write the algorithm, I just need help with the greedy choice). Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
40 views