34
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 ...
- 13.2k
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 ...
- 6,920
24
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 ...
- 13.2k
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.♦
- 140k
15
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 ...
- 268k
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,281
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}\...
- 18.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 ...
- 966
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.♦
- 140k
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,025
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.♦
- 140k
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.♦
- 140k
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 ...
- 10.7k
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
Not able to simplify a sum over reciprocals of $\log i$
The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$:
$$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$
In ...
- 268k
6
votes
What do queues and stacks correspond to in math?
As a practical matter, how you treat data structures mathematically largely depends what you're trying to do.
For example, suppose that you're trying to reason about the correctness of programs that ...
- 18.8k
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,058
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.1k
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.5k
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 ...
- 6,978
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,249
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 ...
- 24.9k
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 ...
- 322
5
votes
Accepted
How to find upper and lower bound without using formula
Another approach:
$n^2/4=(n/2)^2= \underbrace{n/2 + n/2 +\cdots + n/2}_{n/2 \text{ times}} \le 1+2+\cdots + n \le \underbrace{n + n +\cdots + n}_{n \text{ times}} = n^2 $
$n^2= \underbrace{n + n +\...
- 11.9k
5
votes
Proving that $2^n$ does not divide $n!$
Idea: Count explicitly how many factors $2$ the numbers in $[1..n]$ contribute to $n!$.
Observe that every other number adds one (the even numbers), every fourth adds another (those divisible by four)...
- 70.8k
5
votes
How to simplify the sum over 1/i?
If you consider the last term in general, $\sum_{[1\leq i \leq \log n -1]} \frac{1}{i} $ as
$$ \sum_{[1\leq i\leq k]} \frac{1}{i} $$
In this way, you can establish a bound using a integral ...
- 2,141
5
votes
Accepted
Finite representations and programming languages Countably inifite
Here is a simpler situation highlighting the difference. The set of finite binary strings is countable. The set of infinite binary strings is uncountable.
Another example: the set of numbers with ...
- 268k
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 \\
...
- 808
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.8k
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.7k
Only top scored, non community-wiki answers of a minimum length are eligible