New answers tagged computer-science
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$-...
- 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
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 ...
- 4,427
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, ...
- 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 ...
- 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/...
- 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 ...
- 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: ...
- 113k
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.
...
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 ...
- 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 ...
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 ...
- 37.8k
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\...
- 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.
...
- 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 ...
- 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 ...
- 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 ...
- 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
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’...
- 8,805
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$ ...
- 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{...
- 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 $\...
- 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 ...
- 598
Top 50 recent answers are included