New answers tagged greedy-algorithms
2
This problem is equivalent to the bipartite b-matching problem on complete bipartite graphs, where you get a complete bipartite graph $G = (V, E)$ as input and an integral function $b : V \rightarrow \mathbb{N}$ that assigns an integer to each vertex. The goal is to find a subset of the edges $S \subseteq E$ such that $S \cap \delta(v) = b(v)$ for all $v\in ...
3
This problem is not easy. The popular website GeeksforGeeks gives an answer that returns the wrong answer, "YES" when row sums are $ [3, 3, 3, 1]$ and column sums are $[4, 4, 1, 1]$.
How can we find a set of necessary and sufficient conditions that is easy to compute? How can we produce a wanted matrix if the conditions are satisfied?
One easy ...
1
To answer your question:
I am not really sure what is the goal behind the question?
If I were to give this assignment to my students, I would expect
An algorithm in pseudo code
Running time analysis
Proof of correctness
You have given neither.
It is always risky to handwave an algorithm, because you always cherry-pick data structures and details when you ...
0
This follows almost immediately from the definition of expectation, when we sample the actions with the distribution that $\pi_t$ (the bandit) defines, and the inherent randomness of the model.
First, let us make sure we use the same terminology:
$\pi_t(x)$ is the probability that the bandit chose action $x\in\text{Actions}$
$R(x,r)$ will be the probability ...
1
Your solution is not optimal. Take for example, the following list of weights: $[1,4,3,2]$. In this example, your algorithm will place only $1$ in the bins, whilst a different solution could place $4,3$ and $2$ instead (which is obviously a better solution).
However, you can create a dynamic programming solution for this problem:
Consider the graph $G$, with ...
Top 50 recent answers are included