Latest Studies in Algorithms

Probabilistic Methods: Lecture Notes on Tenure Game and Strategy Analysis

The tenure game is a perfect information game between two players, Paul chairman of the department and Carole dean of the school. An initial position is given in which various faculty (MELIH, FATIH, etc.) are at various pretenured positions. Paul will win if some faculty member receives tenure - Carole wins if no faculty member receives tenure. Each year (or round if you will) Chair Paul creates a promotion list L of the faculty and gives it to Dean Carole who has two options.

• Option One: Carole may promote all faculty on list L one rung and simultaneously fire all other faculty.
• Option Two: Carole may promote all faculty not on list L one rung and simultaneously fire all faculty on list L.

The report is mainly examines Tenure Game with some variations and strategy analysis. The report is based on Joel Spencer's (a famous Matematician in Probabilistic Methods) "Randomization, Derandomization, and Antirandomization: Three games" paper.

Download: [.pdf]

Paper: Josephus: An Improved Algorithm for Finding the Sole Survivor (coming soon!!)

(with Prof. Errol Lloyd)

The Josephus problem is a historic relative of the currently popular televison show Survivor. In the Josephus problem, the numbers from 1 to n are arranged in a circle, and starting from position 1, every m^th number around the circle is eliminated until only one number, the sole survivor, remains. In this paper we give an algorithm for determining the sole survivor in time O(max(m, m log n/m)).
The best prior result ran in time O(m log n).

References

1. A. Engel, Exploring Mathematics with your Computer , Mathematical Association of America, Washington, 1997.
2. A. Engel, Problem Solving Strategies , Springer, New York, 1998; Ex. 9.33.
3. R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics , Addison-Wesley, New York, 1989 (2nd edn., 1994).
4. L. Halbeisen, N. Hungerbühler, The Josephus Problem, Journal de Théorie des Nombres de Bordeaux , 9 (2), 1997, pp.303-318.
5. D. E. Knuth, The Art of Computer Programming , Addison­Wesley, New York; Vol. I, 2nd Ed. (1973), Ex. 1.3.2.22, and Vol. III (1975), Ex. 5.1.1.2.
6. E. L. Lloyd, An O(n log m) Algorithm for the Josephus Problem, Journal of Algorithms , 4 (3), (1983), 262-270.
7. A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. , 33 (1991), pp.235-240

Experimental result

You can download the presentation given in talk in the Discrete Math Group at ASU, 2005 [ .pps].

Heuristics for Minimum Brauer Chain Problem (2004)

A Brauer chain for a positive integer n is a sequence of integers 1 = a₀, a_1, a₂, ... , a_r = n such that a_i = a_i-1 + a_k for some 0 ≤ k < i and 1 ≤ i ≤ n. Brauer chain simply solves one of the essential problems of arithmetic in computer; "calculating xⁿ using minimum number of multiplications". In this paper, several heuristics for approximating minimum length Brauer chain for a given number n, is discussed. These heuristics are based on some greedy approaches and dynamic programming. Experimental results show that the approximation ratio is smaller than 1.5 for these heuristics and even better we achieved a very good approximation ratio.

Project report [.htm]

Project presentation [.ppt]