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 ...
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$.
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 (...
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 ...
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 ...
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 ...
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