This book, updated and improved, introduces the mathematics that support advanced computer programming and the analysis of algorithms. The book's primary aim is to provide a solid and relevant base of mathematical skills. It is an indispensable text and reference for computer scientists and serious programmers in virtually every discipline.
Author(s): Ronald L. Graham; Donald Ervin Knuth; Oren Patashnik
Edition: 2
Publisher: Addison-Wesley Professional
Year: 1994
Language: English
Pages: 657
Preface
A Note on Notation
Contents
1 Recurrent Problems
1.1 The Tower of Hanoi
1.2 Lines in the Plane
1.3 The Josephus Problem
Exercises
2 Sums
2.1 Notation
2.2 Sums and Recurrences
2.3 Manipulation of Sums
2.4 Multiple Sums
2.5 General Methods
2.6 Finite and Infinite Calculus
2.7 Infinite Sums
Exercises
3 Integer Functions
3.1 Floors and Ceilings
3.2 Floor/Ceiling Applications
3.3 Floor/Ceiling Recurrences
3.4 `mod': The Binary Operation
3.5 Floor/Ceiling Sums
Exercises
4 Number Theory
4.1 Divisibility
4.2 Primes
4.3 Prime Examples
4.4 Factorial Factors
4.5 Relative Primality
4.6 `mod': The Congruence Relation
4.7 Independent Residues
4.8 Additional Applications
4.9 Phi and Mu
Exercises
5 Binomial Coefficients
5.1 Basic Identities
5.2 Basic Practice
5.3 Tricks of the Trade
5.4 Generating Functions
5.5 Hypergeometric Functions
5.6 Hypergeometric Transformations
5.7 Partial Hypergeometric Sums
5.8 Mechanical Summation
Exercises
6 Special Numbers
6.1 Stirling Numbers
6.2 Eulerian Numbers
6.3 Harmonic Numbers
6.4 Harmonic Summation
6.5 Bernoulli Numbers
6.6 Fibonacci Numbers
6.7 Continuants
Exercises
7 Generating Functions
7.1 Domino Theory and Change
7.2 Basic Maneuvers
7.3 Solving Recurrences
7.4 Special Generating Functions
7.5 Convolutions
7.6 Exponential Generating Functions
7.7 Dirichlet Generating Functions
Exercises
8 Discrete Probability
8.1 De nitions
8.2 Mean and Variance
8.3 Probability Generating Functions
8.4 Flipping Coins
8.5 Hashing
Exercises
9 Asymptotics
9.1 A Hierarchy
9.2 O Notation
9.3 O Manipulation
9.4 Two Asymptotic Tricks
9.5 Euler's Summation Formula
9.6 Final Summations
Exercises
A Answers to Exercises
B Bibliography
C Credits for Exercises
Index
List of Tables
