×

Discrete mathematics with algorithms. (English) Zbl 0651.68001

New York etc.: Wiley. XIII, 546 p.; £27.75; $ 47.15 (1988).
The book is a middle-level-introduction into the algorithmic techniques of discrete mathematics.
Chapter 1 presents basic notions of set theory, theory of Boolean functions, logics, and a definition of an algorithm. Chapter 2 introduces basic principles of arithmetics like induction proofs, the big oh concept, and proofs by contradiction, and uses as an example the exponentiation. The material in chapter 3 deals with subsets, binomial coefficients, permutations (and their application to the game of mastermind), and the binomial theorem. Chapter 4 gives a brief introduction into some algorithmic and counting ideas of discrete mathematics within number theory: greatest common divisor, the Euclidean algorithm, Fibonacci numbers, and coding.
Chapter 5 forms a brief introduction to some concepts of graph theory: graphs, spanning trees, networks, and Kruskal’s algorithm. Chapter 6 covers sorting, searching algorithms, search trees, the complexity of these algorithms, and the use of recursion for sorting and searching. Chapter 7 studies solutions of recurrence relations and counting problems that arise from recursive procedures. Chapter 8 contains an algorithmic development of some important problems in graph theory: minimum-distance trees, Eulerian cycles, Hamiltonian cycles, and the application of graph coloring to storage allocation.
A lot of exercises and questions are given throughout the book. For all questions, a solution is presented at the end of the book. The book has no references.
Reviewer: B.Thalheim

MSC:

68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68W99 Algorithms in computer science
68Rxx Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite