
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 nbit 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 tth 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