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 ...
- 14.3k
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,008
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 ...
- 14.3k
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 ...
- 273k
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.♦
- 150k
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,366
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}\...
- 19.8k
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,219
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.♦
- 150k
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,223
8
votes
Accepted
Variants of the 3-SUM problem
Randomized algorithms
If you'll accept a randomized algorithm, yes, it can be done in linear time. There's a randomized algorithm whose expected running time is $O(n)$, and where the probability ...
D.W.♦
- 150k
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.♦
- 150k
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.4k
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
How to improve my these specific math skills?
I find it surprising and unfortunate that you didn't get to study algorithms and discrete math more in your university studies. As you seem to have realized, a person can know how to code, but without ...
- 3,088
6
votes
Accepted
Recurrence Relation(with Square root)
Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $...
- 13.3k
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.7k
6
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,267
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,325
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 ...
- 27.1k
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
Application of set theory subjects as ordinals, forcing, generic filters in software engineering
The areas of set theory you refer to are generally rather abstract and don't seem to have a lot of applications. Also, the concept of "application" is different in math than in CS. Anyway, though ...
- 10.9k
5
votes
What's wrong with this problem (Inclusion-Exclusion principle)
Let $A$, $B$, and $C$ be the set of pupils that have access to a PC running Windows, Apple, and Linux, respectively.
We know that
\begin{align*}
|A \cup B \cup C| &= 120 \\
|A| &= 80 \\
...
- 828
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.3k
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 (...
- 17.9k
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 ...
- 273k
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}$...
- 435
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 ...
- 81k
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,008
Only top scored, non community-wiki answers of a minimum length are eligible