# Tag Info

### 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$-...
• 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 ...
• 15.4k

### 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 ...
• 4,427

### 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, ...
• 8,078
1 vote

• 1,958

### 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 ...
• 2,924

### 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 ...
• 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.
• 20.2k
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’...
• 8,805

### 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$ ...
• 22.2k

### 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{...
• 4,463