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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$.
user avatar
  • 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 ...
user avatar
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$
user avatar
  • 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}\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 +\...
user avatar
  • 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)...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 \\ ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar

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