JeffE
Reputation
346
Top tag
Next privilege 500 Rep.
Access review queues
 Mar 6 comment Particular Use of Big O Notation Perhaps "for all sufficiently large $j$ and sufficiently small $\epsilon>0$". Mar 5 comment Voronoi average number of vertices $< 6$ Easier: Let $\deg(f)$ be the number of edges of face $f$. Then $\sum_f \deg(f) = 2e \le 6n-12$ by Euler's formula. The pigeonhole principle now implies that at least one face $f$ has $\deg(f) < 6$. Mar 5 comment Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$ Use recursion trees. Then forget the Master Theorem. Mar 5 comment Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$ There are standard ways to prove that floors and ceilings in recursive arguments can be ignored, if you only want an asymptotic solution. See Section 6 of these notes. Once the floors and ceilings are gone, the recurrence falls immediately to recursion trees (or the Master theorem). Mar 3 comment $\aleph_1\leq A$ for an uncountable set $A$ How is it possible to use Axiom X in a proof without using any consequences of Axiom X? (At least the instructor should have written "proper consequences".) Feb 25 comment Algorithm using the cases of Master Theorem Is "1-C(n) = ..." pronounced "one minus see of en equals..."? Or do you mean "Question (1): $C(n) = 3C(n/2)+n$"? Feb 23 comment How to discuss the maximum Area of Internal rectangular in an irregular region? Do you mean "How does one find the largest rectangle in the interior of an irregular region?"? Feb 23 comment Min cut Max flow - Finding the cut with least vertices @Shmoopy: Do you mean minimum (s,t)-cut, or global minimum cut? (Must the cut separate s and t?) Feb 23 comment Min cut Max flow - Finding the cut with least vertices @aelguindy: You're counting minimum (s,t)-cuts; yes, there can be exponentially many. David is counting global minimum cuts, with no fixed terminals s and t; there can be only O(n^2) of these. In your example graph, there are exactly 2n minimum cuts, none of which is an (s,t)-cut. Feb 23 awarded Commentator Feb 23 comment Can anyone tell me what is this sequence: 4, 14,23, 34, 42,50,59,66, 72,79,86, 96,103,110,116,125 The source PDF file has a really big clue: "Boxed values are “express” stops; others are normal stops." Feb 23 comment Find a maximum of difference without sorting. The original question specifies that the input array contains real numbers, so hashing is not possible. Feb 22 comment Find a maximum of difference without sorting. Why? It directly answers the question, and the answer is "No." Feb 22 comment Orthogonal set vs. orthogonal basis Actually, the empty set is also an orthogonal set. Feb 22 comment Orthogonal set vs. orthogonal basis $\{(1,0,0) , (0,1,0)\}$ is an orthogonal set of vectors in $\mathbb{R}^3$, but it is not an orthogonal basis of $\mathbb{R}^3$. Feb 22 comment Geometric proof of existence of irrational numbers. +1 for the last sentence. Feb 22 comment Find a maximum of difference without sorting. Wait, what is $n$ here? The size of the array, or just an index into the array? If the former, then what is the max over? If the latter, then what is the running time in terms of? Are you just looking for the difference between the largest and second largest elements? Oct 11 comment Is the empty graph connected? In mathematics, a red herring is neither necessarily red nor necessarily a fish. Nov 9 awarded Teacher Nov 9 answered Expected time of tree search algorithm on random input