  This paper makes three contributions to estimating the number of perfect
matching in bipartite graphs. First, we prove that the popular sequential
importance sampling algorithm works in polynomial time for dense bipartite
graphs. More carefully, our algorithm gives a $(1\pm\epsilon)$-approximation
for the number of perfect matchings of a $\lambda$-dense bipartite graph, using
$O(n^{\frac{1-2\lambda}{\lambda}\epsilon^{-2}})$ samples. With size $n$ on each
side and for $\frac{1}{2}>\lambda>0$, a $\lambda$-dense bipartite graph has all
degrees greater than $(\lambda+\frac{1}{2})n$.
  Second, practical applications of the algorithm require many calls to
matching algorithms. A novel preprocessing step is provided which makes
significant improvements.
  Third, three applications are provided. The first is for counting Latin
squares, the second is a practical way of computing the greedy algorithm for a
card-guessing game with feedback, and the third is for stochastic block models.
In all three examples, sequential importance sampling allows treating practical
problems of reasonably large sizes.
