Mathematical Analysis of Algorithms,
Abstract
The report consists of the texts of lectures presented to the International Congress of Mathematicians in 1970 and to the IFIP Congress in 1971. The lectures are essentially sales pitches intended to popularize work in algorithmic analysis, a field of study which involves numerous applications of discrete mathematics to computer science. Both lectures attempt to indicate the flavor of the general field by considering particular applications in detail. The 'mathematical' lecture deals with the problem of calculating greatest common divisors, and includes a presentation of a new algorithm which lowers the asymptotic running time for gcd of n-bit integers from n squared to n to the power (1+ epsilon). The information processing lecture deals with the problems of in situ permutation and selection of the t-th largest element, emphasizing techniques for analyzing particular algorithms which have appeared in the literature. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1971
- Accession Number
- AD0726158
Entities
People
- Donald Knuth
Organizations
- Stanford University