Recent Publications

Recent Posts

Problem link: Counting Road Networks | HackerRank. You are supposed to count the number of connected undirected labeled graphs with $n$ vertices. Algorithms with $O(n \log^2 n)$ time complexity are preferable. A Dynamic-Programming Algorithm Let $f(n)$ be the answer for $n$. The first idea to compute $f(n)$ is subtracting the number of disconnected graphs from the total number. The total number of size-$n$ graphs is $g(n) := 2^{\binom{n}{2}}$. How to count the disconnected graphs?


Suppose you have a toy specification with built-in nondeterminism, and you want to generate answers with respect to the specification: type exp = EInt of int | EPair of exp * exp | ENdet of exp * exp type ans = VInt of int | VPair of ans * ans For example, from the following specification EPair (ENdet (EInt 5) (EInt 6)) (ENdet (EInt 7) (EInt 8)) you might want to generate a bunch of possible answers: