5,478 reputation
52039
bio website
location California
age
visits member for 3 years, 2 months
seen 7 hours ago

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


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
May
1
suggested suggested edit on Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
May
1
comment Decryption Problem
@Brandon: Hah! Ok, you got me. Cryptographers create, cryptanalysts break, and cryptologists do both. The main conference in our field is called Advances in Cryptology, but I rarely use that term it forums like this one because it's not known to lay audiences. But yeah, cryptanalysts was the proper word.
Apr
30
revised Decryption Problem
added 2 characters in body
Apr
30
answered probability of at least one person having a gem of type $n$, etc.
Apr
30
comment Interesting approximations? ($\pi$, $e$, etc.?)
Is there a question here?
Apr
28
answered Simple or maybe not so simple probabilistic question
Apr
28
comment Calculating the highest possible damage achievable using 6 items from a pool of ~25
@Shawn: Yuval used the standard method to count combinations with repetitions. See en.wikipedia.org/wiki/…
Apr
26
revised Calculating the highest possible damage achievable using 6 items from a pool of ~25
added 130 characters in body