''Concrete Mathematics: A Foundation for Computer Science'', by

Ronald Graham Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...

Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...

, and

Oren Patashnik Oren Patashnik (born 1954) is an American computer scientist. He is notable for co-creating BibTeX, and co-writing '' Concrete Mathematics: A Foundation for Computer Science''. He is a researcher at the Center for Communications Research, La Jol ...

, first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the analysis of algorithms.

Contents and history

The book provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms. According to the preface, the topics in ''Concrete Mathematics'' are "a blend of CONtinuous and disCRETE mathematics".

Calculus Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithm ...

is frequently used in the explanations and exercises. The term "concrete mathematics" also denotes a complement to " abstract mathematics". The book is based on a course begun in 1970 by Knuth at

Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...

. The book expands on the material (approximately 100 pages) in the "Mathematical Preliminaries" section of Knuth's ''

The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of com ...

''. Consequently, some readers use it as an introduction to that series of books. ''Concrete Mathematics'' has an informal and often humorous style. The authors reject what they see as the dry style of most mathematics textbooks. The margins contain "mathematical

graffiti Graffiti (plural; singular ''graffiti'' or ''graffito'', the latter rarely used except in archeology) is art that is written, painted or drawn on a wall or other surface, usually without permission and within public view. Graffiti ranges from s ...

", comments submitted by the text's first editors: Knuth and Patashnik's students at Stanford. As with many of Knuth's books, readers are invited to claim a

reward Reward may refer to: Places * Reward (Shelltown, Maryland), a historic home in Shelltown Maryland * Reward, California (disambiguation) * Reward-Tilden's Farm, a historic home in Chestertown Maryland Arts, entertainment, and media * "Rewa ...

for any error found in the book—in this case, whether an error is "technically, historically, typographically, or

politically incorrect ''Political correctness'' (adjectivally: ''politically correct''; commonly abbreviated ''PC'') is a term used to describe language, policies, or measures that are intended to avoid offense or disadvantage to members of particular groups in socie ...

". The book popularized some mathematical notation: the Iverson bracket,

floor and ceiling functions In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...

, and notation for rising and falling factorials.

Typography

Donald Knuth used the first edition of ''Concrete Mathematics'' as a test case for the

AMS Euler AMS Euler is an upright cursive typeface, commissioned by the American Mathematical Society (AMS) and designed and created by Hermann Zapf with the assistance of Donald Knuth and his Stanford graduate students. It tries to emulate a mathematicia ...

typeface and

Concrete Roman Concrete Roman is a slab serif typeface designed by Donald Knuth using his METAFONT program. It was intended to accompany the Euler mathematical font which it partners in Knuth's book ''Concrete Mathematics''. It has a darker appearance than its ...

font.

Chapter outline

# Recurrent Problems #

Summation In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, mat ...

# Integer Functions #

Number Theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

Binomial Coefficients In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...

# Special Numbers #

Generating Functions In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...

# Discrete Probability #

Asymptotics In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as bec ...

Editions

* * Errata

(1994)

(January 1998)

(27th printing run, printing, May 2013)

References

External links

ToC and blurb for ''Concrete Mathematics: A Foundation for Computer Science'', 2nd ed.

{{Donald Knuth navbox 1988 non-fiction books Computer science books Mathematics textbooks Books by Donald Knuth Addison-Wesley books American non-fiction books