Discrete Algorithmic Mathematics, Third Edition

by Maurer; Stephen B.

• ISBN13: 9781568811666
• ISBN10: 1568811667
• Edition: 3rd
• Format: Hardcover
• Copyright: 2005-01-21
• Publisher: TAYLOR & FRANCIS

Summary

Thoroughly revised for a one-semester course, this well-known and highly regarded book is an outstanding text for undergraduate discrete mathematics. It has been updated with new or extended discussions of order notation, generating functions, chaos, aspects of statistics, and computational biology. Written in a lively, clear style that talks to the reader, the book is unique for its emphasis on algorithmics and the inductive and recursive paradigms as central mathematical themes. It includes a broad variety of applications, not just to mathematics and computer science, but to natural and social science as well.A manual of selected solutions is available for sale to students; see sidebar. A complete solution manual is available free to instructors who have adopted the book as a required text. To request a copy of the complete solutions contact Susannah Sieper at 303-817-1996 or email [e-mail] authors have created an Errata sheet, which they update periodically.Selected excerpts are available for evaluation: - Contents - Instructor's Preface - Chapter Summaries - Recursive Algorithms - Induction and Recursive Algorithms - Shortest Paths - Combinatorial Identities and Combinatorial Arguments

Table of Contents

List of Algorithms
Instructor's Preface	ix
Student's Preface	xiv
Chapter Summaries	xvii
Pathways Through the Book	xx
Problem Difficulty Rating	xxii
Symbols, Notation, Abbreviations and Conventions	xxiii
Prologue What Is Discrete Algorithmic Mathematics?	1	(8)
Mathematical Preliminaries	9	(64)
Sets, Relations, and Functions	9	(11)
Some Important Functions	20	(10)
Growth Rates and Order Notation	30	(10)
Summation and Product Notation	40	(10)
Matrix Algebra	50	(6)
The Language and Methods of Reasoning	56	(17)
Supplementary Problems	69	(4)
Algorithms	73	(62)
Some Examples of Algorithms	73	(15)
Aspects of AL	88	(6)
Recursive Algorithms	94	(11)
Algorithmic Language: Procedures and Functions	105	(12)
The Analysis of Algorithms	117	(18)
Supplementary Problems	131	(4)
Mathematical Induction	135	(82)
Introduction	135	(2)
First Examples	137	(14)
Strong Induction and Other Variants	151	(7)
Induction and Recursive Algorithms	158	(10)
Induction and Iterative Algorithms	168	(12)
How to Conjecture What to Prove	180	(14)
Inductive Definitions	194	(7)
Faulty Inductions	201	(16)
Supplementary Problems	210	(7)
Graphs and Trees	217	(104)
Examples and Terminology	217	(19)
Paths, Cycles and the Adjacency Matrix	236	(14)
Eulerian and Hamiltonian Paths and Cycles	250	(16)
Shortest Paths	266	(12)
Breadth First Search and Depth First Search	278	(7)
Coloring Problems	285	(11)
Trees	296	(25)
Supplementary Problems	311	(10)
Fundamental Counting Methods	321	(90)
Introduction	321	(1)
First Examples: The Sum and Product Rules	322	(7)
Subtler Examples and Further Rules	329	(12)
Permutations and Combinations	341	(7)
Combinatorial Identities and Combinatorial Arguments	348	(7)
The Binomial Theorem	355	(10)
Four Common Problems with Balls and Urns	365	(10)
Generating Functions	375	(10)
Combinatorial Algorithms	385	(14)
Algorithmic Pigeonholes	399	(12)
Supplementary Problems	406	(5)
Difference Equations	411	(102)
Introduction	411	(2)
Modeling with Difference Equations	413	(13)
Getting Information from Difference Equations	426	(7)
Terminology and a Fundamental Theorem	433	(6)
Constant Coefficient Homogeneous Linear Difference Equations	439	(12)
Qualitative Analysis	451	(6)
Nonhomogeneous Difference Equations	457	(5)
Applications to Algorithms	462	(17)
Variable Coefficients, Sums, and Recent Advances in Computer Algebra	479	(5)
Nonlinear Difference Equations	484	(11)
Finite Differences	495	(18)
Supplementary Problems	508	(5)
Probability	513	(98)
Introduction	513	(4)
Probability Space	517	(10)
Conditional Probability, Independence, and Bayes' Theorem	527	(12)
Random Variables and Distributions	539	(18)
Expected Value	557	(12)
Variance	569	(8)
Statistical Estimation	577	(9)
Applications to Algorithms: Proofs of Prior Claims	586	(9)
Recursive Methods in Probability	595	(16)
Supplementary Problems	606	(5)
An Introduction to Mathematical Logic	611	(80)
Introduction and Terminology	611	(5)
The Propositional Calculus	616	(14)
Validity and Tautology	630	(7)
Algorithm Verification	637	(6)
Boolean Algebra	643	(20)
The Predicate Calculus	663	(13)
Algorithm Verification Using the Predicate Calculus	676	(6)
Theorems and Proofs	682	(9)
Supplementary Problems	689	(2)
Epilogue Coming Full Circle with Biology and Minimax Theorems	691	(26)
DNA Matching	691	(16)
Algorithmic Mathematics and Minimax Theorems	707	(10)
Final Problems	717	(6)
References	723	(6)
Appendix: Limits	729	(4)
Hints and Answers	733	(28)
Index	761