New answers tagged

3 votes

Good Algorithm to Compute all Subgroups of a Finite Group.

For small groups, there are techniques to squeeze out more information. However, in general, I would not expect good algorithms. Here are some reasons why. Wilson exhibits a family of class $2$ $p$-...
user avatar
  • 13.5k
1 vote
Accepted

A confusion on $\beta\eta$-reduction

You basically answered the question yourself. Clearly, the statement is false. More precisely: It is true that if $M =_\eta N$ then $FV(M) = FV(N)$, for the reason you wrote in your post. It is ...
user avatar
0 votes

What makes distributed function computation difficult?

The shape of the decoder-function-of-interest $f$ may make it beneficial for the encoders to transform their inputs using non-trivial structure across time indices. Usual random binning techniques do ...
user avatar
0 votes

The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

There are two obvious methods: One, you calculate $x^1$, $x^2$, $x^4$, $x^8$, $x^{16}$ etc. and then multiply the powers that you need. Two, you calculate in turn $x^k$ where k is the highest 1, 2, 3, ...
user avatar
  • 8,078
1 vote

The rationale behind algorithm for the Modular Exponentiation from the book "Introduction to Algorithms"

The key idea is basically to use rules of exponents and the binary expansion of $b$ to speed things up. Consider $a^{b}$. Now write $b$ in binary. So: $$b = \sum_{i=0}^{\ell} a_{i}2^{i},$$ where $\ell ...
user avatar
  • 13.5k
0 votes

Complexity of testing if a binary operation is a group

It was shown only recently that testing whether a Latin Square is a group takes time $O(n^{2} \log^{c} n) = \tilde{O}(n^2)$ (the $\tilde{O}$ hides the polylogarithmic factor). https://arxiv.org/pdf/...
user avatar
  • 13.5k
7 votes

Why do greedy coloring algorithms mess up?

I like @HallaSurvivor's intuition that coloring isn't a local property. From an Algorithms perspective, there are two properties to consider for when the greedy algorithm works. The first property is ...
user avatar
  • 13.5k
4 votes

Why do greedy coloring algorithms mess up?

The first thing to note is that everything depends on the heuristic you use to order the vertices. On the one hand, if you knew an optimal coloring, you could get the greedy algorithm to produce it: ...
user avatar
1 vote

Standard notation for algorithm (instead of function)?

I would say that the answer depends on the specific case, and the first answer I can think of is that your algorithm probably does have input parameters, even if they might be trivial for your case. ...
user avatar
0 votes

Standard notation for algorithm (instead of function)?

This is too long for a comment. I would perhaps focus less on the algorithm and more on the algorithmic problem you are trying to solve. For instance, subroutines of the form "we can compute x ...
user avatar
  • 13.5k
0 votes

Calculating normals for a polygon mesh (3D computer graphics)

Accumulating the Cross-product of component triangles is one way. Glassner notes that the cross of the diagonals of a quad gives the same answer. Coons pointed out that the vector of the areas of the ...
user avatar
0 votes

Functions in "Introduction to the Theory of Computation 3rd Edition by Sipser"

In standard English mathematical usage "$f$ takes on the value $-1$" means that $-1$ is a possible output for the function $f$. We might say "$f$ takes $-1$ as an input", but we ...
user avatar
0 votes

Which grows faster $n!$ or $n^{\sqrt{n}}$?

A very easy way to see that these kind of limits are true is to use Stirling's Approximation which says $$n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n$$ So, $$\left(\frac{n^{\sqrt{n}}}{n!}\right)\sim\...
user avatar
  • 5,553
0 votes

Are DFS trees unique?

Yes, DFS trees are not unique - your example serves as enough. You can consider some cycle graph and notice there are at least two ways to traverse the cycle using DFS, starting at a given vertex. ...
user avatar
  • 66
0 votes

Binary variable notation

It seems as if you are looking for the boolean operators AND, OR, and NOT, where the first, second, and third types are $FF +1$, $FF \cdot 0$, and $\overline{FF}$. The reason why the first type is $FF ...
user avatar
  • 1,958
0 votes

Proof that Christofides Algorithm is a 3/2-approximation for the TSP

Fact 1: Any spanning tree has weight at least of minimum spanning tree. Fact 2: The best possible Eulerian cycle is of weight OPT, hence the spanning tree it contains is of weight at most OPT. But the ...
user avatar
  • 2,924
0 votes

What's the minimum step size that can be used in Euler's method before it becomes unreliable?

In each step you will have about the same rounding errors, independent of the step size. But for example halving the step size means you need twice as many steps which doubles the rounding errors. If ...
user avatar
  • 8,078
1 vote

Prove that there's no decidable language that separates two other languages.

If $C$ is decidable, then the questions ''$x\in A$'' or ''$x\in B$'' must be decidable since $C$ has the separation property. But these questions are not decidable due to the halting problem.
user avatar
  • 20.2k
6 votes
Accepted

Why doesn’t $T(n) = 2T(\frac{n}{2}) + O(n^2)$ solve to $T(n) = \Theta(n^2)$?

Let’s begin with a simpler problem. Suppose I say “I am at most 1km tall.” What does this statement tell you about how tall I am? The answer is “not much.” I could be 1m tall, or 2m tall, or perhaps I’...
user avatar
0 votes

Proof (More rigorous) for LeetCode: 11. Container With Most Water problem

Consider 2 sequences: $a_0 = 0$ $a_{k+1}$ is the smallest integer s.t. $a_{k+1} > a_{k}$ and $h[a_{k+1}] > h[a_j]$ the last value of $a_{k}$ is the index of the first largest value of $h$. $b$ ...
user avatar
  • 22.2k
2 votes

time complexity condition among merge-sort and bubble-sort?

If $x>0$ then $\log_2(x) \le \sqrt{2x}$. So, if $n \in \mathbb{N}$ is such that $n \ge 2$ and $\frac{n}{2} > \big(\frac{c_2}{c_1}\big)^2$, then $c_2 < c_1\sqrt{\frac{n}{2}}$, yielding \begin{...
user avatar
  • 4,463
0 votes

How to prove that 2SAT $\in$ P

This is more of a comment, but unfortunately too long for a comment. As additional intuition, 2SAT is actually $\textsf{NL}$-complete. The reduction from 2SAT to Path Finding in Directed Graphs is $\...
user avatar
  • 13.5k
2 votes
Accepted

How to prove that 2SAT $\in$ P

Everything prior to the corollary proves that the decision problem 2SAT is in P, namely checking whether or not a 2SAT formula is satisfiable as a yes or no question. The corollary extends this result ...
user avatar

Top 50 recent answers are included