Randomiserade algoritmer - projektförslag

Proposals for PROJECTS in the course Randomized Algorithms

As part of the course, one project should be carried out, individually or in groups of 2-3 students.

Some projects invove the construction and implementation of some randomized algorithms. Other, more theoretical, projects need not involve any such parts. In the following list of project proposals, the two types of projects are signified with -P- (programming) and -L- (liteature study), respectively. Of course, there is no strict borderline between the two types of projects.

Note that suggestions for other projects, are welcome. Inspiration for other projects may, for instance, be found in the book ``Randomized Algorithms'' by Motwani and Raghavan.

When you have decided what which project you want do to, inform me, at latest on Monday 24th April. The projects are to be reported in writing, in Swedish or English. Deadline will be Friday 19th May. Most of the projects were proposed by Olle Häggström when he had the course, and were used later also by Fredrik Lundin.

0. -P- Do exercise 7.2 and estimate the expected number of ones.

1. -P- Explain how randomized algorithms come into play in connection with factorization and prime testing (which are important in cryptography). Useful references are Chapter 14 in Motwani och Raghavan: ``Randomized Algorithms'', and Johan Håstad's ``Notes for the course advanced algorithms''.

2. -L- Study how a refined analysis of the running time of RandomQuicksort can be carried out, leading to a central limit theorem for the running time. See ``A limit theorem for Qicksort'' and other papers by Uwe Rösler. See also McDiarmid, C: Large deviations for Quicksort, Journal of Algorithms 21 (1996), 476-507.

3. -P- In the generalized hard-core model (see Problem 7.4 in the book by Häggström) on large parts of the square lattice, qualitatively different behavior is obtained depending on the parameter value - a so-called phase transition. If the parameter is large, the system settles down to a chessboard pattern, with (just about) every second vertex occupied, whereas no such order appears for small parameters. Determine (approximately) the critical value for this phase transition, using MCMC methods.

4. -L- This project is probably quite advanced. An interesting alternative to the Propp-Wilson algorithm for perfect simulation is ``Fill's algorithm'' (Fill, J: An interruptible algorithm for perfect sampling via Markov chains, Annals of Applied Probability 8 (1998), 131-162). Explain this algorithm, its properties, and the theory behind it.

5. -L- This is similar to Project 8, except that it concerns the ``randomness recycler'', which was recently introduced by Jim Fill and Mark Huber, and which is yet another interesing alternative to the Propp-Wilson algorithm.

6. -P- Implement a simulated annealing algoritm for the traveling salesman problem, and try it out on a real case, such as (say) the 50 biggest towns in Sweden, with distances taken from some suitable road atlas.

7. -L- Discuss the modern theory of pseudo-random number generators, using, e.g., the references given in the book by Häggström.

8. -L- Devdatt Dubhashi at the CS department is, together with Alessandro Panconesi, working on the book project ``Concentration of Measure for Computer Scientists'', which deals with, among other things, the distribution of the running time of randomized algorithms. A preliminary version can be found via their home pages. Discuss suitable parts of the contents of this book.

9. -P- In the generalized hard-core model (see Problem 7.4 in the text book ) on large parts of the square lattice, qualitatively different behavior is obtained depending on the parameter value - a so-called phase transition. If the parameter is large, the system settles down to a chessboard pattern, with (just about) every second vertex occupied, whereas no such order appears for small parameters. Determine (approximately) the critical value for this phase transition, using MCMC methods.

10. -L- An area which is closely related to randomized algorithms, is probabilistic (average case) analysis of deterministic algorithms with random data. A possible ``testing ground'' for such problems is the theory of random graphs. Discuss (parts of) this area. A ueful reference is Frieze, A. och McDairmid, C: Algorithmic theory of random graphs, Random Structures and Algorithms 10 (1997), 5-42.

11. -L- Probabilistic methods for web search - a very hot area! Some information, and useful links, can be found here. Or see the paper ``Random walks with back buttons'' by eight (!) coauthors, available at the homepage of one of them, Madhu Sudan.

	0. -P- Do exercise 7.2 and estimate the expected number of ones.
	1. -P- Explain how randomized algorithms come into play in connection with factorization and prime testing (which are important in cryptography). Useful references are Chapter 14 in Motwani och Raghavan: ``Randomized Algorithms'', and Johan Håstad's ``Notes for the course advanced algorithms''.
	2. -L- Study how a refined analysis of the running time of RandomQuicksort can be carried out, leading to a central limit theorem for the running time. See ``A limit theorem for Qicksort'' and other papers by Uwe Rösler. See also McDiarmid, C: Large deviations for Quicksort, Journal of Algorithms 21 (1996), 476-507.
	3. -P- In the generalized hard-core model (see Problem 7.4 in the book by Häggström) on large parts of the square lattice, qualitatively different behavior is obtained depending on the parameter value - a so-called phase transition. If the parameter is large, the system settles down to a chessboard pattern, with (just about) every second vertex occupied, whereas no such order appears for small parameters. Determine (approximately) the critical value for this phase transition, using MCMC methods.
	4. -L- This project is probably quite advanced. An interesting alternative to the Propp-Wilson algorithm for perfect simulation is ``Fill's algorithm'' (Fill, J: An interruptible algorithm for perfect sampling via Markov chains, Annals of Applied Probability 8 (1998), 131-162). Explain this algorithm, its properties, and the theory behind it.
	5. -L- This is similar to Project 8, except that it concerns the ``randomness recycler'', which was recently introduced by Jim Fill and Mark Huber, and which is yet another interesing alternative to the Propp-Wilson algorithm.
	6. -P- Implement a simulated annealing algoritm for the traveling salesman problem, and try it out on a real case, such as (say) the 50 biggest towns in Sweden, with distances taken from some suitable road atlas.
	7. -L- Discuss the modern theory of pseudo-random number generators, using, e.g., the references given in the book by Häggström.
	8. -L- Devdatt Dubhashi at the CS department is, together with Alessandro Panconesi, working on the book project ``Concentration of Measure for Computer Scientists'', which deals with, among other things, the distribution of the running time of randomized algorithms. A preliminary version can be found via their home pages. Discuss suitable parts of the contents of this book.
	9. -P- In the generalized hard-core model (see Problem 7.4 in the text book ) on large parts of the square lattice, qualitatively different behavior is obtained depending on the parameter value - a so-called phase transition. If the parameter is large, the system settles down to a chessboard pattern, with (just about) every second vertex occupied, whereas no such order appears for small parameters. Determine (approximately) the critical value for this phase transition, using MCMC methods.

	10. -L- An area which is closely related to randomized algorithms, is probabilistic (average case) analysis of deterministic algorithms with random data. A possible ``testing ground'' for such problems is the theory of random graphs. Discuss (parts of) this area. A ueful reference is Frieze, A. och McDairmid, C: Algorithmic theory of random graphs, Random Structures and Algorithms 10 (1997), 5-42.
	11. -L- Probabilistic methods for web search - a very hot area! Some information, and useful links, can be found here. Or see the paper ``Random walks with back buttons'' by eight (!) coauthors, available at the homepage of one of them, Madhu Sudan.