JeffE
Reputation
346
Top tag
Next privilege 500 Rep.
Access review queues
 Mar5 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$. Mar5 comment Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$ Use recursion trees. Then forget the Master Theorem. Mar5 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). Mar3 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".) Feb25 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$"? Feb23 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?"? Feb23 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?) Feb23 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. Feb23 awarded Commentator Feb23 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." Feb23 comment Find a maximum of difference without sorting. The original question specifies that the input array contains real numbers, so hashing is not possible. Feb22 comment Find a maximum of difference without sorting. Why? It directly answers the question, and the answer is "No." Feb22 comment Orthogonal set vs. orthogonal basis Actually, the empty set is also an orthogonal set. Feb22 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$. Feb22 comment Geometric proof of existence of irrational numbers. +1 for the last sentence. Feb22 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? Oct11 comment Is the empty graph connected? In mathematics, a red herring is neither necessarily red nor necessarily a fish. Nov9 awarded Teacher Nov9 answered Expected time of tree search algorithm on random input Aug23 awarded Supporter