Accession Number : AD0726158

Title :   Mathematical Analysis of Algorithms,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Knuth,Donald E.

Report Date : MAR 1971

Pagination or Media Count : 30

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)

Descriptors :   (*ALGORITHMS, MATHEMATICAL ANALYSIS), (*COMPUTER PROGRAMMING, ALGORITHMS), NUMERICAL ANALYSIS, PERMUTATIONS, SYMPOSIA

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE