Discrete Mathematics

by Johnsonbaugh, Richard

• ISBN13: 9780131176867
• ISBN10: 0131176862
• Edition: 6th
• Format: Hardcover
• Copyright: 2009-01-01
• Publisher: Prentice Hall

Summary

This best-selling book provides an accessible introduction to discrete mathematics through an algorithmic approach that focuses on problem-solving techniques.The book 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.

Table of Contents

Preface

Logic and Proofs

Propositions

Conditional Propositions and Logical Equivalence

Quantifiers

Proofs

Resolution Proofs

Mathematical Induction

Strong Form of Induction and well ordering Property

The Language of Mathematics

Sets

Functions

Sequences and Strings

Relations

Relations

Relations

Equivalence Relations

Matrices of Relations

Relational Databases

Algorithms

Introduction

Correctness of Algorithms

Analysis of Algorithms

Recursive Algorithms

Introduction to Number Theory

Divisors

Representation of Integers and Integer Algorithims

The Euclidean Algorithm

The RSA Public-Key Cryptosystem

Counting Methods and the Pigeonhole Principle

Basic Principles

Permutations and Combinations

Algorithms for Generating Permutations and Combinations

Introduction to Discrete Probability

Discrete Probability Theory

Generalized Permutations and Combinations

Binomial Coefficients and Combinatorial Identities

The Pigeonhole Principle

Recurrence Relations

Introduction

Solving Recurrence Relations

Applications to the Analysis of Algorithms

Graph Theory

Introduction

Paths and Cycles

Hamiltonian Cycles and the Traveling Salesperson Problem

A Shortest-Path Algorithm

Representations of Graphs

Isomorphisms of Graphs

Planar Graphs

Instant Insanity

Trees

Introduction

Terminology and Characterizations of Trees

Spanning Trees

Minimal Spanning Trees

Binary Trees

Tree Traversals

Decision Trees and the Minimum Time for Sorting

Isomorphisms of Trees

Game Trees

Network Models

Introduction

A Maximal Flow Algorithm

The Max Flow, Min Cut Theorem

Matching

Boolean Algebras and Combinatorial Circuits

Combinatorial Circuits

Properties of Combinatorial Circuits

Boolean Algebras

Boolean Functions and Synthesis of Circuits

Applications

Automata, Grammars, and Languages

Sequential Circuits and Finite-State Machines

Finite-State Automata

Languages and Grammars

Nondeterministic Finite-State Automata

Relationships Between Languages and Automata

Computational Geometry

The Closest-Pair Problem

An Algorithm to Compute the Convex Hull

Appendices

Matrices

Algebra Review

References

Hints and Solutions to Selected Exercises

Index

Table of Contents provided by Publisher. All Rights Reserved.