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/...
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 ...
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 ...
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, ...
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$, ...
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 ...
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.
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 ...
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 ...
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).
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 ...
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. ...
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....
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 ...
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 ...
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.
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 ...
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 ...
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$,...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
greedy-algorithms × 436algorithms × 256
dynamic-programming × 69
optimization × 63
graphs × 61
correctness-proof × 47
algorithm-analysis × 37
approximation × 31
scheduling × 24
intervals × 20
knapsack-problems × 17
proof-techniques × 16
time-complexity × 15
sorting × 11
combinatorics × 11
arrays × 9
minimum-spanning-tree × 9
trees × 8
set-cover × 8
matroids × 8
data-structures × 7
np-complete × 7
np-hard × 6
search-algorithms × 6
shortest-path × 6