The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

4

Your problem is known as Weighted-2-satisfiability, and is known to be NP-complete. The easiest way to see that is by reduction from Vertex Cover (exercise). Note that the link above is about whether there is a satisfying assignment having at most $k$ true variables. This is equivalent to your problem (exercise).

3

Given a CNF with $n$ variables and $m$ clauses, we denote by $A_i$ the set of truth assignments that do not satisfy clause $i$. Then the number of satisfiable assignments is $$2^n-\left|\bigcup_{i=1}^m A_i\right|.$$ Since each assignment makes at most one clause false, $A_i$ and $A_j$ are disjoint for $i\neq j$. Also note $|A_i|=2^{n-n_i}$ where $n_i$ is ...

2

The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to ...

2

So I actually found the answers I was looking for. The case $c \ge 0$ is already handled in the question above. For the case $c < 0$ we have: \begin{align} n_{1/2} &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\ &\le \frac{|b| + \sqrt{b^2 - 4ac}}{a} \\ &\le \frac{|b| + \sqrt{b^2} + \sqrt{-4ac}}{a} \\ &= \frac{2|b| + \sqrt{4a|c|}}{a} \\ &...

1

CLRS is wrong. For example, the function $0n^2+0n+0$ is asymptotically nonnegative but doesn't belong to $\Theta(n^2)$. Changing "nonnegative" to "positive" doesn't help: you can consider $0n^2+0n+1$. Even requiring the function to be nonconstant doesn't help: consider $0n^2+1n+0$. Here is a statement which is correct: if $a > 0$ then \$an^2+bn+c = \Theta(...

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