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/...
Minko_Minkov's user avatar
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 ...
vonbrand's user avatar
  • 14k
3 votes

Finding optimal sequence of attacks to minimize number of soldiers needed

Okay! In order to (hopefully) prove that your proposed greedy algorithm is correct, we will make an argument that is very common when dealing with greedy algorithms (as you can see from @D.W. 's ...
Highheath's user avatar
  • 1,021
3 votes

On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty

Let $k$ be the smallest integer such that $2^k > n$. Any solution must use at least $k$ moves Suppose towards a contradiction that there exists a winning strategy using at most $k-1$ moves $m_1, ...
Steven's user avatar
  • 29.4k
3 votes
Accepted

Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The idea is to set $K/2$ as the target. If there is any given number that is at least $K/2$, just return it. Otherwise, all given numbers are $<K/2$. If the sum of all given numbers is $\le K$, ...
John L.'s user avatar
  • 38.9k
2 votes

Maximum Independent Set of a Tree using Greedy Algorithm

Yes, it would work for trees (acyclic graphs in general). You need to prove one thing. Let $\ell$ be a leaf in a tree. Then there exists a maximum independent set that contains $\ell$. The proof ...
Pål GD's user avatar
  • 16k
2 votes

How to prove greedy algorithm is correct

There is a very nice theory on when greedy algorithms work in general. It is based on the abstract concept of matroids. A detailed explanation is given by Jeremy Kun.
vonbrand's user avatar
  • 14k
2 votes
Accepted

Visiting all nodes of a directed graph exactly once (not dfs)

You are asking for a Hamiltonian Path (or a Hamiltonian cycle if you need to return to your original starting point). https://en.wikipedia.org/wiki/Hamiltonian_path It is NP-hard to determine whether ...
JimN's user avatar
  • 837
2 votes

I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

For data structures you need to learn - stack, queue, linked list, and binary search tree. These 4 should be enough for interviews. You can google them and you will know how to implement them. There ...
Andrew's user avatar
  • 51
2 votes

What would be an efficient algorithm that finds the maximum number of party people?

Hint: It's actually quite simple. (Yes, that's all the hint you need).
gnasher729's user avatar
  • 29.8k
2 votes

Finding optimal sequence of attacks to minimize number of soldiers needed

@Highheath has given an excellent and concise answer already. I came up (with the help of some friends) with a much longer one, which I still think it's worth posting. Maybe it's because I worked on ...
user2891462's user avatar
2 votes
Accepted

How does additional assumptions increase approximation factor?

I guess that greedy approach should consider edges in weight decreasing order only. Then every edge $e_0$ of greedy matching may block up to two edges $e_1$ and $e_2$ of maximum weight matching. ...
Smylic's user avatar
  • 176
1 vote
Accepted

Number of stops during trip - Dynamic programming algorithm

As it turns out, you don't need any dynamic programming to solve this problem, and a greedy solution works great. The greedy solution is: go as far as possible without taking a break from City $A$ (i....
Misha Ivkov's user avatar
1 vote
Accepted

Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I decided to write a python script that generates all the optimal solutions for all the change. You can literally scroll through the solutions and observe there are no denomination expansions. So, my ...
Gary Drocella's user avatar
1 vote

Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

The greedy algorithm is optimal if it only picks 1c coins. It is optimal if it picks a 5c coin as the highest because the alternative is five 1c. It is optimal if it picks one or two 10c because the ...
gnasher729's user avatar
  • 29.8k
1 vote

Greedy Maximum Bipartite Matching

Here's a counter example on codeforces. However if it's complete bipartite matching, we can use the greedy Nobel winning algorithm in Economics.
Kenneth Kho's user avatar
1 vote

Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Your algorithm is not correct. Consider intervals [1,7], [8, 14], [15, 21], [22,28], [13,16], [2,9], [3,10], [4,11], [17,23], [18,24], [19, 25]. Your algorithm chooses [13,16] first, as it only ...
Bernardo Subercaseaux's user avatar
1 vote
Accepted

Greedy algorithms criterion/ intution

Sometimes it is good to delete the maximum element even when its value is larger than the sum of the two minimum elements. Deleting it allows the algorithm to remove the smaller elements in the next ...
Inuyasha Yagami's user avatar
1 vote
Accepted

First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2

Suppose we have used First-Fit-Decreasing algorithm to open $\ell$ bins. Consider any used bin except the last one. Name it $B$. Consider the moment the total piece size of $B$ became greater than $1$,...
John L.'s user avatar
  • 38.9k
1 vote

Workers with certain strength carrying boxes. (Greedy)

I won’t answer your question but tell you about one thing you need to check: Every time you assign a worker or a worker + pill, you waste some amount. Is it possible to get a better outcome by ...
gnasher729's user avatar
  • 29.8k
1 vote

Why this greedy algorithm does not return the optimal solution to this NP-hard problem?

Let C be even. Take C items where $w_{ij} = 1$ and C items where $w_{ij} = 2$. Your greedy algorithm will put the same C items in each bin, so you find a solution with C items. Instead you can put C ...
gnasher729's user avatar
  • 29.8k

Only top scored, non community-wiki answers of a minimum length are eligible