Why does the Gomory-Hu algorithm work? i.e. why does the tree that it outputs have the property that you can do min-cut by removing its smallest edge and returning the connected components? (My hunch is that Fig. 4 has the answer if I stare at it long enough)


( Read more... )

Lately, I've been faced with problems of the following type ( Read more... )

While arguing that CS is more fundamental than Physics, Daniel Lemire gives it the status of a "natural science", since it supposedly makes fundamental predictions about the universe. He claims that both (a) Digital Physics / Strong Church-Turing Thesis (SCTT), and (b) the possibility of AI, are falsifiable predictions ("Yet, these predictions ( Read more... )