Skip to main content

Tag Info

Hot answers tagged discrete-mathematics

35 votes

Real life examples of negative weight edges in graphs

Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that ...
• 16.7k
25 votes
Accepted

Double exponentials vs single exponentials

The issue comes down to ambiguous terminology. $(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative. Conventionally, nested exponentials without parentheses ...
• 7,176
25 votes

Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...
• 16.7k
19 votes
Accepted

Why is Integer Linear Programming in NP?

As you have seen in other sources, the proof that there exists a witness with polynomial size does not exactly fit inside the margin, so to speak. The proof I know of (from the book I mention below) ...
• 8,323
16 votes
Accepted

How to solve a recurrence relation with a sum?

Here are several ways to solve your recurrence relation. Guessing Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this ...
• 278k
16 votes

Double exponentials vs single exponentials

$a^{(b^c)}$ is not the same as $(a^b)^c$. When people write $2^{2^k}$, they usually mean $2^{(2^k)}$, not $(2^2)^k$.
• 163k
13 votes

Arrange in increasing order of asymptotic complexity

You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$
• 2,364
13 votes

• 278k
5 votes
Accepted

Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G

Hint 1: Hint 2: Full Solution:
• 6,237
5 votes

Why is Integer Linear Programming in NP?

The paper "On the Complexity of Integer Programming" from Papadimitriou has a very compact (2 and a half pages counting from abstract) proof. It only needs the common knowledge about dual ...
• 709
4 votes
Accepted

Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

I wrote a short example to test the hypothesis and found out that the reverse postorder of a reverse graph is indeed not the same as the postorder of the original graph. Consider the following graph: ...

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