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 ...
- 15.5k
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,038
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 ...
- 15.5k
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 ...
- 275k
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.♦
- 156k
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
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}\...
- 21.6k
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 ...
- 1,227
10
votes
Accepted
1-to-1 cryptographically secure bit shuffling
This is known as a one-way permutation. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate ...
D.W.♦
- 156k
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 ...
- 3,241
8
votes
Is it feasible to generate every possible RGB image?
The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not ...
D.W.♦
- 156k
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 ...
- 11.5k
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 ...
- 7,768
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 ...
- 91
6
votes
Accepted
Determining if (infinite) binary language DFAs contain at least 1 prime?
It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, ...
- 14.8k
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 ...
- 7,395
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 ...
- 28.3k
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 ...
- 342
5
votes
Accepted
Examples of maximal paths in undirected graphs
We can say a path is maximal if you cannot add any new vertices to it to make it longer. You can contrast this with a path of maximum length: it is the longest path in a graph (so it is also maximal, ...
- 22.5k
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 (...
- 18k
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 ...
- 275k
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 ...
- 741
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}$...
- 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 ...
- 81.4k
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 ...
- 7,038
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 ...
- 233
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}^...
- 275k
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.
- 1,564
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.
- 275k
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:
- 5,793
Only top scored, non community-wiki answers of a minimum length are eligible