326 reputation
110
bio website cs.uiuc.edu
location Urbana, IL
age
visits member for 4 years, 4 months
seen 2 days ago

No, I am a meat popsicle.


Mar
15
comment Time complexity of algorithm computing averages
This question was already asked on cstheory.se; it was quickly closed for being off-topic.
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