Reputation
6,013
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
6 22 44
Impact
~274k people reached

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 approved 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
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
Apr
26
comment Calculating the highest possible damage achievable using 6 items from a pool of ~25
@Shawn: Just test the cost in the inner loop and include the item-set only if the cost is under the budget. By the way, the folks around here are very helpful and friendly, but to be honest I think your question would find a better home on stackoverflow or programmers.SE. Cheers!
Apr
26
revised Calculating the highest possible damage achievable using 6 items from a pool of ~25
Allow duplicate combos in the code example