Category Archives: Algorithms

Call for papers CATS 2012

I am a PC member for the first time.

—

Call for Papers

CATS 2012 — Computing: The Australasian Theory Symposium
Melbourne, Australia, January 30-February 2, 2012
http://cats.it.usyd.edu.au/

The 18th Computing: The Australasian Theory Symposium (CATS) will be
held in Melbourne, Australia, in January/February 2012. CATS is an
annual conference held in the Australia-New Zealand region, dedicated
to theoretical computer science.

Authors are invited to submit papers that present original and
unpublished research on topics related to theoretical aspects of
computer science, including (but not limited to):
– algorithms and data structures
– algorithmic game theory
– combinatorial optimization
– computability
– computational complexity theory
– computational geometry
– graph theory and combinatorics
– parallel and distributed algorithms
– logic and type systems
– program derivation, analysis, and verification
– theory of programming languages

Important dates:
– Paper submission deadline: Monday 15 August, 2011
– Acceptance notification: Monday 10 October, 2011
– Final version due: Monday 7 November, 2011
– Conference dates: Monday 30 January – Thursday 2 February, 2012

The proceedings of this event will be published by the Australian
Computer Society (ACS) in the CRPIT Series (http://crpit.com/), and
will also appear in the ACM digital library. CATS 2012 is part of the
Australasian Computer Science Week (ACSW), an international annual
conference event, supported by the Computing Research and Education
Association (CORE) in Australia. ACSW 2012 is hosted by RMIT
University in Melbourne, Australia.

For more information please visit http://cats.it.usyd.edu.au/
Contact: Julian Mestre <cats2012@easychair.org>

Where now for A of A?

For the first time in several years I will not be attending the annual AofA workshop/conference. This year it is being held in Brazil at an inconvenient time for me. The scientific programme looks quite interesting.

I have never seen a full history of the field of analysis of algorithms (the SODA talk by Philippe Flajolet has some interesting comments). A rough summary of what I believe to be the case: before Knuth came along, people analysed algorithms by implementing them and guessing their asymptotic runtime via extrapolation. Knuth changed this by showing that serious classical mathematics could be brought to bear on analysis of algorithms, and that this ultimately led to models that would predict to high accuracy the real running time on large problems. Notwithstanding the fact that many researchers in the area of algorithms (the “big-O crowd”) are content with less precise estimates, I am sure they were happy that such analysis was possible.

Recently I have seen more and more examples of situations where this kind of analysis is called into question. The main problems seem to be caching and branch prediction, which ensure that the time to execute an “elementary” operation can vary wildly. A relatively small number of papers have appeared that discuss these issues (after all, it should not be beyond the wit of man to say something analytical in these situations) but the results are necessarily less precise than in the old days (for a start, even finding out the branch prediction algorithm used by chip makers is not trivial).  Let’s see where the next few years lead.

Bernard Chazelle to visit NZ

As part of the programme in Algorithmics sponsored by the NZIMA, Professor Bernard Chazelle of Princeton University (he also has his own Wikipedia article) will visit New Zealand to give some public talks in March 2009. I have found some of his writings very stimulating, if a little bewildering in their language. In particular his essay The Algorithm: Idiom of Modern Science is very persuasive. With luck, public appreciation of algorithms will be considerably higher after his visit than it is now!

Algorithms research in NZ

Last week I was at the NZIMA Algorithms meeting in Napier, which I helped to organize. There were 5 invited speakers, and all their talks (they gave 2 each) were worthwhile listening. I got the role of amateur cameraman and so most of the talks have full video footage, which I hope to make available on the web soon.

At a strategy session it was decided that we will try to create a more formal community for those researching in algorithms (interpreted broadly, from very pure to very applied). The mechanism will probably be to set up something like a Google group. Please contact me if you are interested in joining.

Random and exhaustive generation of permutations and cycles

to appear in Annals of Combinatorics (10 pages).

Download author version

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).

Download author version

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.