book

Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

by Ronald L. Graham, Donald E. Knuth, Oren Patashnik

February 1994

Intermediate to advanced

672 pages

18h 51m

English

Addison-Wesley Professional

Read now

Unlock full access

1.1 The Tower of Hanoi1.2 Lines in the Plane1.3 The Josephus ProblemExercises

2.1 Notation2.2 Sums and Recurrences2.3 Manipulation of Sums2.4 Multiple Sums2.5 General Methods2.6 Finite and Infinite Calculus2.7 Infinite SumsExercises
3.1 Floors and Ceilings3.2 Floor/Ceiling Applications3.3 Floor/Ceiling Recurrences3.4 ‘MOD’: The Binary Operation3.5 Floor/Ceiling SumsExercises
4.1 Divisibility4.2 Primes4.3 Prime Examples4.4 Factorial Factors4.5 Relative Primality4.6 ‘MOD’: The Congruence Relation4.7 Independent Residues4.8 Additional Applications4.9 PHI and MUExercises
5.1 Basic Identities5.2 Basic Practice5.3 Tricks of the Trade5.4 Generating Functions5.5 Hypergeometric Functions5.6 Hypergeometric Transformations5.7 Partial Hypergeometric Sums5.8 Mechanical SummationExercises
6.1 Stirling Numbers6.2 Eulerian Numbers6.3 Harmonic Numbers6.4 Harmonic Summation6.5 Bernoulli Numbers6.6 Fibonacci Numbers6.7 ContinuantsExercises
7.1 Domino Theory and Change7.2 Basic Maneuvers7.3 Solving Recurrences7.4 Special Generating Functions7.5 Convolutions7.6 Exponential gf’s7.7 Dirichlet Generating FunctionsExercises
8.1 Definitions8.2 Mean and Variance8.3 Probability Generating Functions8.4 Flipping Coins8.5 HashingExercises
9.1 A Hierarchy9.2 O Notation9.3 O Manipulation9.4 Two Asymptotic Tricks9.5 Euler’s Summation Formula9.6 Final SummationsExercises

Content preview from Concrete Mathematics: A Foundation for Computer Science, 2nd Edition

C

Credits for Exercises

The exercises in this book have been drawn from many sources. The authors have tried to trace the origins of all the problems that have been published before, except in cases where the exercise is so elementary that its inventor would probably not think anything was being invented.

Many of the exercises come from examinations in Stanford’s Concrete Mathematics classes. The teaching assistants and instructors often devised new problems for those exams, so it is appropriate to list their names here:

Year	Instructor	Teaching Assistant(s)
1970	Don Knuth	Vaughan Pratt
1971	Don Knuth	Leo Guibas
1973	Don Knuth	Henson Graves, Louis Jouaillec
1974	Don Knuth	Scot Drysdale, Tom Porter
1975	Don Knuth	Mark Brown, Luis ...