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 ...
Pål GD's user avatar
  • 16.1k
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 ...
Draconis's user avatar
  • 7,138
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 ...
Pål GD's user avatar
  • 16.1k
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) ...
Discrete lizard's user avatar
  • 8,248
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 ...
Yuval Filmus's user avatar
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$.
D.W.'s user avatar
  • 159k
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$
zkutch's user avatar
  • 2,364
13 votes

Can we solve a "very" exponential recurrence?

It depends what you mean by "solve". This is tetration, and it has a number of "closed" forms. For example: $$\begin{eqnarray*}T_0 & = & 1 \\ T_{n+1} & = & 2^{T_n}\...
Pseudonym's user avatar
  • 22.1k
12 votes

Real life examples of *zero* weight edges in graphs

The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players ...
kviiri's user avatar
  • 1,227
10 votes
Accepted

Does Either...Or means Exclusive Or or Inclusive Or?

Don't try to force formal definitions over common english language. "Either… or" means whatever you want it to mean. There is no convention. Just be precise when you want a formal definition....
Nathaniel's user avatar
  • 15.6k
9 votes

Real life examples of *zero* weight edges in graphs

In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we ...
Cort Ammon's user avatar
  • 3,351
8 votes
Accepted

Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

Discrete mathematics, linear algebra, calculus, and probability are all used pretty much everywhere in computer science. Basically, discrete maths is the basis of everything, while linear algebra and ...
nir shahar's user avatar
  • 11.6k
7 votes
Accepted

How to check if a specific ILP problem can be solved in polynomial time or not?

First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a ...
Discrete lizard's user avatar
  • 8,248
7 votes

Real life examples of negative weight edges in graphs

In a social network. Where the source node is a person the target node is another person and the connection represents the preference the source has for the target. The sign representing the direction ...
stam_a's user avatar
  • 91
6 votes
Accepted

Empty intersection of longest path in connected graph

You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a ...
xskxzr's user avatar
  • 7,455
6 votes

Fermat's last theorem: How to (partially) solve by programs

See for example Sophie Germain. Sophie Germain proved that every prime number p with certain properties could be used as an expoonent in Fermat's Last Theorem. She used her theorem to prove that all ...
gnasher729's user avatar
6 votes

Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

In addition to the basic math knowledge, a solid grounding in Logic is necessary for tackling topics such as Automata theory and Formal Languages Computability Theory Complexity Theory While one ...
Acsor's user avatar
  • 342
5 votes

Why does 3 % 5 give 3 in C ? % >(mod )

Notice that with the mod operator ($\%$), you're using integer division, much as you are when you use the division operator ($/$) with two ints (at least in most (...
Luke Mathieson's user avatar
5 votes
Accepted

How to measure the complexity of the discrete logarithm problem?

It doesn't matter whether you choose the size of the group $|G|$ or the size of the integer representing it $n$ as a parameter, since $n \approx \log |G|$. There are two reasons that usually the ...
Yuval Filmus's user avatar
5 votes

Why an ARM processor with 32 bits address bus can address 4 billion different bytes?

While there have been computers built that use bit addressing, notably the Burroughs 1700, 1800, and 1900 mainframes and the Intel iAPX-432, the vast majority of machines use byte addressing. This ...
Peter Camilleri's user avatar
5 votes
Accepted

$A, B$ --- enumerable sets, is $A \times B$ enumerable?

There are many ways you could solve this, so here's a hint. $A$ and $B$ are enumerable, which means that injections $$ f : A \rightarrow \mathbb{N} \quad \text{and} \quad g : B \rightarrow \mathbb{N}$...
ThreeFx's user avatar
  • 433
5 votes
Accepted

Is it possible to denote "any single alphabet symbol" in an FSA state diagram?

The formal representation of an automaton is the tuple giving its state set, alphabet, transition function, start state and set of accepting states. The diagram is not a formal representation: it's ...
David Richerby's user avatar
5 votes

how to calculate $2^{5000}$ mod 10 without calculator in fast way?

Consider the first few powers of 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… Now take all of those mod 10: 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4… Try to solve it yourself, from this, before ...
Draconis's user avatar
  • 7,138
5 votes
Accepted

Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5)

$n^2 + (n + 1)^2 = (n + 2)^2 \Rightarrow n^2 + n^2 + 2n + 1 = n^2 + 4n + 4 \Rightarrow 2n^2 2n + 1 = n^2 + 4n + 4 \Rightarrow n^2 - 2n - 3 = 0 \Rightarrow n = -1, 3$ Therefore, 3 is the only ...
Shade's user avatar
  • 243
5 votes

Proof of the inclusion-exclusion principle

Let me slightly rephrase the argument. Let $N_r$ be the number of elements contained in exactly $r$ of the sets $A_1,\ldots,A_n$. Then the left-hand side is $$ |A_1 \cup \cdots \cup A_n| = \sum_{r=1}^...
Yuval Filmus's user avatar
5 votes
Accepted

What is the meaning of this symbol that looks like an inverted uppercase A?

It's universal quantifier that interpreted as "given any" or "for all". you can check definition of quantifiers.
ErroR's user avatar
  • 1,910
5 votes
Accepted

Solve $T (n) = T (\frac n2) + n(2 - \cos n)$

Since $|\cos n| \leq 1$, we have $1 \leq 2-\cos n \leq 3$, and so $$ T(n) = T(n/2) + \Theta(n). $$ This is something that the master theorem can handle.
Yuval Filmus's user avatar
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:
Inuyasha Yagami's user avatar
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 ...
Sudix's user avatar
  • 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: ...
Shubham Mittal's user avatar

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