After teaching a basic course on data structures and algorithms many times, I grew weary of saying the same things each semester, yet never quite saying them right. So I spent (too) many hours in the studio and editing on my laptop, to produce some short (mostly 15-25 minute) video lectures, available on my Youtube channel. They are posted under a CC-BY licence, so feel free to use them but give me appropriate credit. Feedback from students using them the last time I taught the material (where I tried with mixed success to replace traditional lectures with more active learning) was clearly positive.
Tag Archives: algorithms
Big O(micron) and Big Omega and Big Theta
Teaching an algorithms course recently, I realized that the correct use of these asymptotic notations is apparently rather difficult for students to grasp. In fact, I have some colleagues whose understanding of these concepts is not maximally clear.
In 1976 Donald Knuth published an article explaining these notations in detail and recommending their use. After 35 years and plenty of evidence that it works well, we still have resistance. Perhaps one reason is that the idea of “asymptotically equivalent to”, or “of the exact order of” is formalized by the symbol Theta, while O is a simpler and more familiar symbol that evokes the word “order”. The most common misuse I have seen is exactly this use of O when Theta is meant. The principle that the most important and useful concepts should have the simplest notation implies that O would be better for computer science use. However, that would make it inconsistent with mathematical use where big-O is definitely used for upper bounds only.
The main mistake seen (also mentioned by Knuth) apart from the perhaps excusable one above is not excusable: it is the use of O to discuss lower bounds as in the example: “Algorithm A is better than Algorithm B because A is known to run in time O(n log n) and B in time O(n^2)”. If O is replaced by Theta, then this might make sense, but the literature is full of algorithms whose O-bounds are not asymptotically tight – how do we know B doesn’t run in time O(n) also? Again, if you think that O means Theta, this mistake is an easy one to make.
Random and exhaustive generation of permutations and cycles
to appear in Annals of Combinatorics (10 pages).
Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. This algorithm is very similar to the standard method for generating a random permutation, but is less well known.
We consider both methods in a unified way, and discuss their relation with exhaustive generation methods. We analyse several random variables associated with the algorithms and find their grand probability generating functions, which gives easy access to moments and limit laws.
Probability generating functions for Sattolo’s algorithm
Mark C. Wilson, Journal of the Iranian Statistical Society 3 (2004), 297-308 (special issue on probabilistic analysis of algorithms).
Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger’s analysis by finding limit laws for the same two random variables.
The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results results by determining the “grand” probability generating functions of the random variables.
The focus throughout is on using standard methods that give a unified approach, and open the door to further study.
Asymptotics of multivariate sequences, part II: multiple points of the singular variety
Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.
Abstract: Let $latex F(mathbf{z})=sum_mathbf{r} a_mathbf{r}mathbf{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $latex mathbb{C}^d$, and let $latex mathcal{V}$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $latex mathcal{V}$.
In the first article in this series, we treated the case of smooth points of $latex mathcal{V}$. In this article we deal with multiple points of $latex mathcal{V}$.
Degree- and time-constrained broadcast networks
Michael J. Dinneen, Geoffrey Pritchard and Mark C. Wilson, Networks 39 (2002), 1–9.
Abstract: We consider the problem of constructing networks with as many nodes as possible, subject to upper bounds on the degree and broadcast time. The paper includes the results of an extensive empirical study of broadcasting in small regular graphs using a stochastic search algorithm to approximate the broadcast time. Significant improvements on known results are obtained for cubic broadcast networks.