Uniform sampling from various sets

Add to your list(s) Download to your calendar using vCal

• Philip Sterne (University of Cambridge)
• Monday 02 June 2008, 11:15-12:15
• TCM Seminar Room, Cavendish Laboratory, Department of Physics.

If you have a question about this talk, please contact Carl Scheffler.

This week’s journal club has a computer science flavour. Try to solve the following tasks giving a loose bound on the space and time complexity of your solutions.

Sample uniformly from the following sets:

1. Subsets of size k (from a larger set of n items)
2. The set of all permutations with n items
3. The set of all binary trees with n nodes
4. The set of all partitions with n items

I will be cheating and presenting some interesting solutions from Chapters 12 and 13 of the book Non-Uniform Random Variate Generation

This talk is part of the Machine Learning Journal Club series.

This talk is included in these lists:

• Cambridge talks
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Interested Talks
• ML
• Machine Learning Journal Club
• Machine Learning Summary
• Quantum Matter Journal Club
• TCM Seminar Room, Cavendish Laboratory, Department of Physics
• TQS Journal Clubs
• rp587
• yk373's list

Note that ex-directory lists are not shown.