JeffE
Reputation
346
Top tag
Next privilege 500 Rep.
Access review queues
 Jun9 comment maximum flow ford-fulkerson analysis No, if (a,b) is in E, then both (a,b) and (b,a) are in E'. In particular, E' is always a superset of E. On the other hand, $|E'| \le 2|E|$, so $O(E') = O(E)$. May31 comment How does one give a mathematical talk? It. Is. Not. Possible. To. Speak. Too. Slowly. May29 comment Where/What are good sources to learn about the history of computation? That said, I think the question is much too broad. Do you mean computing devices (starting with Stone Age tally sticks, or even fingers), or algorithms (starting perhaps with techniques that were already centuries old when they were described in the Rhind Papryus), or applications (starting perhaps with agriculture)? May29 comment Where/What are good sources to learn about the history of computation? @Gigili: Cross-posting is generally discouraged; migration might be a better option if the question doesn't get good answers here. See this discussion at meta.cstheory. May24 awarded Organizer May24 revised Determining position at some point in time add computational-geometry tag May24 suggested approved edit on Determining position at some point in time May24 comment Determining position at some point in time Hint: This should have the computational-geometry tag. May21 comment Variety vs. Manifold Even in French, a red herring is neither necessarily red nor necessarily a fish. (And no, @Galoisfan, the phrases "algebraic variety" and "algebraic manifold" are not synonyms, even in English; read the answer again!) May20 comment Expected Number of Convex Layers and the expected size of a layer for different distributions Well, that's just a back of the envelope estimate. It might be good for intuition, but I wouldn't trust it to give a precise bound, especially after several iterations. May19 awarded Yearling May19 comment Expected Number of Convex Layers and the expected size of a layer for different distributions But $P_1$ is not uniformly distributed in a square; it's uniformly distributed in $conv(P)$, which has $\Theta(\log n)$ sides in expectation. So the right back-of-the-envelope estimate for the complexity of the convex hull of $P_1$ is $\Theta(\log^2 n)$. More generally, deeper layers are "rounder", and boundary effects matter less. May19 answered Given a victory condition and a set strategy, what are the chances of winning on a given turn in a game of Magic: The Gathering? May17 comment Can every nonsingular $n\times n$ matrix with real entries be made singular by changing exactly one entry? @ZevChonoles: Yes, much better. (You can't make the identity matrix singular by changing an off-diagonal entry, for precisely this reason.) May17 comment Can every nonsingular $n\times n$ matrix with real entries be made singular by changing exactly one entry? But what if the coefficient of $a_{k\ell}$ is zero? Equivalently, what if the function $f$ such that $\det(A) = f(a_{k\ell})$ is actually constant? May17 answered Applications of parity formula on connected planar graph May17 comment Applications of parity formula on connected planar graph "Proof: 3 ≠ 19." May15 comment Examples of mathematical induction @OldPro: Induction proofs are just proofs by contradiction where you prove that the smallest counterexample doesn't exist. May14 comment Mathematical toys? Also the Towers of Hanoi. May13 comment How to evaluate Θ, or O and Ω from function J.D.'s comment proves the upper bounds ($O(\cdots)$) but ignores the matching lower bounds ($\Omega(\cdots)$). Half the terms in the sum are at least $n/2$, so the sum is at least $n^2/4 = \Omega(n^2)$. Since we already know the sum is $O(n^2)$, we conclude that it is also $\Theta(n^2)$. Similarly, half the terms in the sum $\ln n + \ln (n-1) + \cdots + \ln 1$ are at least $\ln (n/2) = \ln n - \ln 2$, so $\ln n! \ge (n/2)\ln (n/2) = (n\ln n)/2 - n (\ln 2)/2 = \Omega(n\log n)$. Since we already know that $\ln n! = O(n\log n)$, we conclude that $\ln n! = \Theta(n\log n)$.