5,672 reputation
52142
bio website
location California
age
visits member for 3 years, 9 months
seen Nov 11 at 1:50

A mediocre professor at a top-notch university making mediocre contributions to this top-notch community


May
8
revised Where did the word “logarithm” come from?
added historical note
May
8
answered Where did the word “logarithm” come from?
May
7
answered Can this number theory MCQ be solved in 4 minutes?
May
7
comment Factorize $x^3-3x+2$
@cardano: since Jim didn't answer, I will: often you can notice small roots just from examination. For example, any polynomial with no constant term will have 0 as a root. If the sum of the coefficients sum to zero (as they do in your question) then 1 is a root. It's usually worth trying -1 as well. Most "real" polynomials won't have nice roots like this, but contrived homework problems and textbook problems will.
May
6
comment Infinity = -1 paradox
A similarly wrong (but simpler) proof would go like this: $\infty+1$ is still $\infty$ since you can't make it any larger. But then we have $\infty = \infty+1$ and we subtract infinity from both sides proving $0=1$.
May
6
awarded  Nice Answer
May
5
comment Factorize $x^3-3x+2$
I don't understand the animosity toward the asker here. What is wrong with asking how to factorize a polynomial?
May
4
answered Recommended Math knowledge for programming
May
3
comment Need a result of Euler that is simple enough for a child to understand
@user9325: Only this [citation needed] wikipedia entry: en.wikipedia.org/wiki/Carl_Friedrich_Gauss#Family (The relevant portion of this entry is repeated hundreds of times in web searches, but none has a citation.)
May
3
awarded  Nice Question
May
3
asked Need a result of Euler that is simple enough for a child to understand
May
3
awarded  Enthusiast
May
2
awarded  Self-Learner
May
2
answered Modulo arithmetic with big numbers?
May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: I highly doubt that this level of detail was intended by the instructor who assigned this problem. Even in the case that $G$ is an adjacency list and $F$ is an unsort edge list, you can still get within the time bounds: simply convert the adjacency list to an adjacency matrix using $O(|V|+|E|)$ time (but $O(|V|^2)$ space!). Then your lookups are $O(1)$.
May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: This depends now on how the problem is given to you: if $F$ is given as a set of markings on $E$, then you're already done! If $F$ is given as a list of pointers to $E$, then you can do lookups in $O(1)$. If $F$ is given as a separate list of edges, then you have to search through $E$ for a match; how long this takes depends on the data structures for $E$ and $F$. If $G$ is given as an adjacency matrix, you can look up edges in $O(1)$. If given as an adjacency list, then it takes longer and we run into problems. Did your homework specify any of these details?
May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: Also, there is no need to remove any edges from $E$. First, mark each edge that is in $F$. Now run Kosaraju's algorithm and each time an edge is found in an SCC, check to see if it has the $F$ label. If it does, you know some cycle uses an edge from $F$.
May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: Kosaraju's algorithm, cited in my answer above, gives a way label each edge in $E$ with a component number telling you what SCC each edge lives in. This immediately gives you the number of components (and more). Now, if any edge of $F$ belongs in an SCC, then you know that there exists a cycle with at least one edge from $F$. Wasn't that your question? Or do you need to find a cycle composed entirely from edges in $F$?
May
1
answered Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
May
1
revised Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
Clarifications