Each topic has provisoriacally assigned a supervisor,
(EA) for Ernst Althaus, (PS) for Peter Sanders.
- Skip List:
- Randomized data structure for sorted sequences. For its
simplicity and efficiency, Skip-Lists are used in LEDA [1, Section 8.3,] (EA).
- Convex Hull:
- The convex hull of a set of points is the smallest convex
set that contains all the points. The algorithm is a randomized
incremental algorithm, i.e. the points were added one by one in a random
order and the convex hull of the current set is
maintained [1, Section 9.2,]
(EA). Assigned to Wei Ding.
- Satisfiability:
- A (relatively) fast randomized algorithm for finding
satisfying assignments of satisfiable formulae in concunctive
normal form [2] (EA). Assigned to Hans Raj Tiwary
- Maximum Satisfiability:
- given a set of clauses in conjunctive normal
form over n variables, find the truth assignment for the variables that
satisfy the maximum number of clauses. You should present an algorithm
based on randomized rounding [1, Section 5.2,] (EA).
Assigned to Paul McCabe.
- s-t cuts
- There is a simple proof via randomized rounding that the LP
relaxation of integer linear program for s-t cuts is integral
[Srinivasan: Approximation algorithms via randomized rounding: a survey]
(ask citeseer) (EA).
- Primality Testing:
-
Given a k bit integer find out in time polynomial in k whether
it is a prime number.
Although recently a deterministic polynomial time algorithm for primality
testing has finally been found. Randomized Algorithms remain the only
practical choice.
[1, Section 14.6,] (EA).
Assigned to Mehmet Kiraz.
- Multiple Choice Allocation:
- Explain the analysis
of the shortest queue algorithm. http://ls2-www.cs.uni-dortmund.de/ voecking/aracne.ps
- Two-Point Sampling:
- A way to make more out of your random bits [1, Section 3.4,]. (EA)
- Expander Graphs:
- Graphs with very nice properties.
For example arbitrary subsets of nodes can communicate with arbitrary
other subsets at high bandwidth
[1, Section 5.3,] (EA).
- Routing:
- Communication in Parallel Computers can suffer freom severe
contention. It turns out that choosing random intermediate
destinations resoleves this contention in many cases [1, Section 4.2,]
http://ls2-www.cs.uni-dortmund.de/ voecking/papers/STOC01.ps.gz (PS).
Assigned to Eske Vladimir.
- Random Number Generators:
- [3, Section 7.1,][4, 5] (PS).
Assigned to Kara, Abdul Qadar
- Random Bit Generators:
- [3, Section 7.4,] (PS).
Assigned to Waqar Saleem.
- Generating Nonuniform Random Variables:
- For example how to
generate RVs that are binomially distributed, normally distributed,
exponentially distributed,...[3, Section 7.2-7.3,] (PS).
- Random Sampling:
- How to pick a random sample from an array
correctly and efficiently -- by coin tosses, with replacement,
without replacement [5] (PS).
Assigned to Dimitris Michail.
- Numerical Integration:
- It turns that randomization is important
for fast numerical integration of functions that depend on
a large number of variables [3, Section 7.6-7.8,] (PS).
Assigned to Ruzica Riskac.
- Simulated Annealing:
- A randomized optimiztion strategy based on
local search
with a nice analogy to the behavior of some physical systems
[6] (PS).
- Paging:
- How randomization can fool an otherwise all too powerful
adversary in virtual memory management [1, Section 13.1-13.3,]. (EA)
Assigned to Kanela Kaligossi.
- MST in sublinear time?
- One can find the approximate weight of
a minimum spanning tree very quickly for integer edge weights.
http://www.cs.princeton.edu/~chazelle/pubs/MstApprox.ps
. (PS)
- Graphics:
http://www.gris.uni-tuebingen.de/publics/staff/Michael_Wand_abs.html
The Randomized z-Buffer Algorithm: Interactive
Rendering of Highly Complex Scenes. (PS)
References
- 1
-
J. Motwani and P. Raghavan.
Randomized Algorithms.
Cambridge University Press, 1995.
- 2
-
Uwe Schöning.
A probabilistic algorithm for k-sat and constraint satisfaction
problems.
In 40th IEEE Symposium on Foundations of Computer Science,
pages 410-414, 1999.
- 3
-
W. H. Press, S.A. Teukolsky, W. T. Vetterling, and B. P. Flannery.
Numerical Recipes in C.
Cambridge University Press, 2. edition, 1992.
- 4
-
P. L'Ecuyer.
Random numbers for simulation.
Communications of the ACM, 33(10):85-97, 1990.
- 5
-
D. E. Knuth.
The Art of Computer Programming -- Seminumerical Algorithms,
volume 2.
Addison Wesley, 2nd edition, 1981.
- 6
-
E. H. L. Aarts and J. H. M Korst.
Simulated Annealing and Boltzmann Machines.
John Wiley & Sons, Chichester, U.K., 1989.
Peter Sanders
Fri Dec 13 17:00:35 MET 2002