Progress in the Analysis of Algorithms at Sanford
Abstract
1)The most significant event of the year was the discovery by Flajolet, Knuth, and Pittel of new techniques for the analysis of random graphs. 2) Floyd and Knuth studied the properties of machines that can add, subtract, and test the sign of numbers. We showed that such machines can actually multiply, divide, and calculate greatest common divisors quite efficiently. 3) One of the main goals in the research proposal for this project was the creation of the Standard Graphbase, a database of interesting test cases that can be used as benchmarks for combinatorial algorithms. 4) Flajolet discovered a way to determine the asymptotic properties of the coefficients of the Hadamard product of two generating functions f(z) and g(z), when f or g have algebraic singularities on their circle of convergence. 5) Knuth and Wilf discovered a simple rule for the divisibility properties of generalized binomial coefficients, extending a classical theorem of Kummer. 6) Knuth, Papadimitriou, and Tsitsiklis studied the complexity of the algorithm for eliminating dominated strategies in certain games. 7) Knuth found a simple way to compute permutation groups with given generators, and showed that was reasonably efficient.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1988
- Accession Number
- ADA200895
Entities
People
- Donald Knuth
Organizations
- Stanford University