Discrete mathematics - Hardcover

Johnsonbaugh, Richard

Hardcover

ISBN 10: 0023609001 ISBN 13: 9780023609008

Publisher: Collier Macmillan Publishers, 1984

Synopsis

This best-selling book provides an accessible introduction to discrete mathematics through an algorithmic approach that focuses on problem- solving techniques. This edition has the techniques of proofs woven into the text as a running theme and each chapter has the problem-solving corner. The text provides complete coverage of: Logic and Proofs; Algorithms; Counting Methods and the Pigeonhole Principle; Recurrence Relations; Graph Theory; Trees; Network Models; Boolean Algebra and Combinatorial Circuits; Automata, Grammars, and Languages; Computational Geometry. For individuals interested in mastering introductory discrete mathematics.

About this title

From the Publisher:

This best-selling book provides an accessible introduction to discrete mathematics through an algorithmic approach that focuses on problem- solving techniques.

From the Inside Flap:

PREFACE

This book is intended for a one- or two-term introductory course in discrete mathematics, based on my experience in teaching this course over a 20-year period. Formal mathematics prerequisites are minimal; calculus is not required. There are no computer science prerequisites. The book includes examples, exercises, figures, tables, sections on problem-solving, section reviews, notes, chapter reviews, self-tests, and computer exercises to help the reader master introductory discrete mathematics. In addition, an Instructor's Guide and World Wide Web site are available.

The main changes in this edition (discussed in more detail later) are an expanded discussion of logic and proofs, the addition of two sections on discrete probability, a new appendix that reviews basic algebra, many new examples and exercises, section reviews, and computer exercises. OVERVIEW

In the early 1980s there were almost no books appropriate for an introductory course in discrete mathematics. At the same time, there was a need for a course that extended students' mathematical maturity and ability to deal with abstraction and also included useful topics such as combinatorics, algorithms, and graphs. The original edition of this book (1984) addressed this need. Subsequently, discrete mathematics courses were endorsed by many groups for several different audiences, including mathematics and computer science majors. A panel of the Mathematical Association of America (MAA) endorsed a year-long course in discrete mathematics. The Educational Activities Board of the Institute of Electrical and Electronics Engineers (IEEE) recommended a freshman discrete mathematics course. The Association for Computing Machinery (ACM) and IEEE accreditation guidelines mandated a discrete mathematics course. This edition, like its predecessors, includes topics such as algorithms, combinatorics, sets, functions, and mathematical induction endorsed by these groups. It also addresses understanding and doing proofs and, generally, expanding mathematical maturity. ABOUT THIS BOOK

This book includes

Logic (including quantifiers), proofs, proofs by resolution, and mathematical induction (Chapter 1). Sets, sequences, strings, sum and product notations, number systems, relations, and functions, including motivating examples such as an application of partial orders to task scheduling (Section 2.4), relational databases (Section 2.7), and an introduction to hash functions and pseudorandom number generators (Section 2.8). A thorough discussion of algorithms, recursive algorithms, and the analysis of algorithms (Chapter 3). In addition, an algorithmic approach is taken throughout this book. The algorithms are written in a flexible form of pseudocode. (The book does not assume any computer science prerequisites; the description of the pseudocode used is self-contained.) Among the algorithms presented are the Euclidean algorithm for finding the greatest common divisor (Section 3.3), tiling (Section 3.4), the RSA public-key encryption algorithm (Section 3.7), generating combinations and permutations (Section 4.3), merge sort (Section 5.3), Dijkstra's shortest-path algorithm (Section 6.4), backtracking algorithms (Section 7.3), breadth-first and depth-first search (Section 7.3), tree traversals (Section 7.6), evaluating a game tree (Section 7.9), finding a maximal flow in a network (Section 8.2), finding a closest pair of points (Section 11.1), and computing the convex hull (Section 11.3). A full discussion of the "big oh," omega, and theta notations for the growth of functions (Section 3.5)., Having all of these notations available makes it possible to make precise statements about the growth of functions and the complexity of algorithms. Combinations, permutations, discrete probability, and the Pigeonhole Principle (Chapter 4). Recurrence relations and their use in the analysis of algorithms (Chapter 5). Graphs, including coverage of graph models of parallel computers, the knight's tour, Hamiltonian cycles, graph isomorphisms, and planar graphs (Chapter 6). Theorem 6.4.3 gives a simple, short, elegant goof of the correctness of Dijkstra's algorithm. Trees, including binary trees, tree traversals, minimal spanning trees, decision trees, the minimum time for sorting, and tree isomorphisms (Chapter 7). Networks, the maximal flow algorithm, and matching (Chapter 8). A treatment of Boolean algebras that emphasizes the relation of Boolean algebras to combinatorial circuits (Chapter 9). An approach to automata emphasizing modeling and applications (Chapter 10). The SR flip-flop circuit is discussed in Example 10.1.11. Fractals, including the von Koch snowflake, are described by special kinds of grammars (Example 10.3.19). An introduction to computational geometry (Chapter 11). An appendix on matrices, and another that reviews basic algebra. A strong emphasis on the interplay among the various topics. As examples, mathematical induction is closely tied to recursive algorithms (Section 3.4); the Fibonacci sequence is used in the analysis of the Euclidean algorithm (Section 3.6); many exercises throughout the book require mathematical induction; we show how to characterize the components of a graph by defining an equivalence relation on the set of vertices (see the discussion following Example 6.2.13); and we count the number of n-vertex binary trees (Theorem 7.8.12). A strong emphasis on reading and doing proofs. Most proofs of theorems are illustrated with annotated figures. Ends of proofs are marked with a square symbol. Separate sections (Problem-Solving Corners) show students how to attack and solve problems and how to do proofs. Numerous worked examples throughout the book. (There are over 500 worked examples.) A large number of applications, especially applications to computer science. Over 3500 exercises, with answers to about one-third of them in the back of the book. (Exercises with numbers in color have an answer in the back of the book.) Figures and tables to illustrate concepts, to show how algorithms work, to elucidate proofs, and to motivate the material. Several figures illustrate proofs of theorems. The captions of these figures provide additional explanation and insight into the proofs. Section reviews. Notes sections with suggestions for further reading. Chapter reviews. Chapter self-tests. Computer exercises. A reference section containing 150 references. Front and back endpapers that summarize the mathematical and algorithm notation used in the book. CHANGES FROM THE FOURTH EDITION The first chapter on logic and proofs is considerably enhanced. Several new motivating examples have been added. A logic game, which offers an alternative way to determine whether a quantified propositional function is true or false, is discussed in Example 1.3.17. Section 1.4 now includes rules of inference for both propositions and quantified statements. The number of exercises in this chapter has been increased from 232 to 391. Arrow diagrams have been added to give a pictorial view of the definition of a function, one-to-one functions, onto functions, inverse functions, and the composition of functions (see Section 2.8). Graphs of functions have been added to give yet another view of functions (see Section 2.8). Two optional sections (Sections 4.4 and 4.5) have been added on discrete probability. We discuss the fundamental terminology (e.g., experiment, event), the use of counting techniques to compute probabilities, basic formulas, mutually exclusive events, conditional probability, independent events, and Bayes' Theorem and its use in pattern recognition. The setting for the Problem-Solving Corner in Chapter 5 has been changed to a more inviting and contemporary setting: sorting in a spreadsheet. The fourth edition's Section 8.5 on Petri nets has been moved to the Web site that accompanies this book. Appendix B, which reviews basic algebra, has been added. The topics treated are rules for combining and simplifying expressions, fractions, exponents, factoring, quadratic equations, inequalities, and logarithms. A number of computer examples now show actual computer screens to help connect the theory to practical applications. Several new examples have been added dealing with Searching the World Wide Web, with a real example using the AltaVista search engine and Boolean expressions (Example 1.1.14) A logic game (Example 1.3.17) Using the matrix of a relation to determine whether the relation is transitive (Example 2.6.7) Pseudorandom number generators (Example 2.8.14) The Melissa virus (as an example of combinatorial explosion) (Example 4.1.2) The birthday problem (Example 4.5.7) Telemarketing (Example 4.5.21) Detecting the HIV virus (Example 4.5.22) Computer file systems (Example 7.1.6). The new section reviews, which precede the exercises in every section, consist of exercises with answers in the back of the book. These exercises review the key concepts, definitions, theorems, techniques, and so on, of the section. Although intended for reviews of the sections, section reviews can also be used for placement and pretesting. Computer exercises

About this edition

• Publisher: Collier Macmillan Publishers
• Publication date: 1984
• ISBN 10: 0023609001
• ISBN 13: 9780023609008
• Binding: Hardcover
• Number of pages: 436