Accession Number:

AD0726158

Title:

Mathematical Analysis of Algorithms,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1971-03-01

Pagination or Media Count:

30.0

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

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE