Linked Questions

1 vote
0 answers
180 views

how to prove correctness of this greedy algorithm? [duplicate]

I did exercise problem from Pittsburgh university cs department. homework. Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question. ...
박주현's user avatar
0 votes
0 answers
19 views

Proving Optimal Greedy Algorithms [duplicate]

How is the best way to go about proving that a greedy algorithm is optimal, inductive vs contradiction, are there parts in the proof that are key to include. I did not feel that the lesson I was ...
James's user avatar
  • 1
4 votes
1 answer
9k views

How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm?

I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem. On the second page of Cornell's Greedy Stays ...
Gary's user avatar
  • 177
0 votes
3 answers
2k views

Find longest path in graph with N nodes and N edges

We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ ...
someone12321's user avatar
  • 1,428
0 votes
1 answer
4k views

Is my proof of my greedy algorithm to find subsequence correct?

Credit to KleinBerg and Taros Book Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
Sudeep Baniya's user avatar
1 vote
1 answer
3k views

Does a greedy strategy exist for this instance of the Bin Packing Problem?

I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 ...
Henk's user avatar
  • 13
4 votes
4 answers
469 views

How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
Loc Truong's user avatar
1 vote
1 answer
1k 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 ...
zbh2047's user avatar
  • 296
2 votes
0 answers
3k views

Why is it necessary to sort according to the starting time in the interval partitioning problem?

What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample ? Note- (refer here for detailed definition) ...
user1968919's user avatar
3 votes
1 answer
1k views

Using a greedy algorithm to find a cut S which at least half of the edges cut

Let $G$ be an undirected graph. Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut. I tried to think about something like choosing the vertex with the highest degree, ...
EL_9's user avatar
  • 133
2 votes
2 answers
851 views

Select a subset of k intervals which form maximum length if we take union of these k intervals

Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals. Note that there are 2 cases ...
Kitwradr's user avatar
  • 123
0 votes
3 answers
2k views

Optimality of a Greedy Algorithm

If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
Salwa's user avatar
  • 131
1 vote
3 answers
1k views

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
WindBreeze's user avatar
3 votes
1 answer
1k views

How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
DarK_FirefoX's user avatar
0 votes
1 answer
1k views

Vertex Cover special cases

This was from a test from my university: Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum ...
yZaph's user avatar
  • 3

15 30 50 per page
1
2 3 4 5