Discrete Mathematics with Ducks: 1st Edition (Hardback) book cover

Discrete Mathematics with Ducks

1st Edition

By sarah-marie belcastro

A K Peters/CRC Press

580 pages

Purchasing Options:$ = USD
Hardback: 9781466504998
pub: 2012-06-21
SAVE ~$18.75
$125.00
$106.25
x
eBook (VitalSource) : 9781466505025
pub: 2012-07-10
from $27.48


FREE Standard Shipping!

Description

Containing exercises and materials that engage students at all levels, Discrete Mathematics with Ducks presents a gentle introduction for students who find the proofs and abstractions of mathematics challenging. This classroom-tested text uses discrete mathematics as the context for introducing proofwriting.

Facilitating effective and active learning, each chapter contains a mixture of discovery activities, expository text, in-class exercises, and homework problems.

  • Elementary exercises at the end of each expository section prompt students to review the material
  • Try This! sections encourage students to construct fundamental components of the concepts, theorems, and proofs discussed.
  • Sets of discovery problems and illustrative examples reinforce learning.
  • Bonus sections can be used for take-home exams, projects, or further study
  • Instructor Notes sections offer suggestions on how to use the material in each chapter

Discrete Mathematics with Ducks offers students a diverse introduction to the field and a solid foundation for further study in discrete mathematics and complies with SIGCSE guidelines. The book shows how combinatorics and graph theory are used in both computer science and mathematics.

Reviews

This book can certainly be used to teach the standard course in discrete mathematics designed for computer science majors. The lighter touch of duck references does amuse you and does not ever overshadow or disguise the mathematical concepts.

—Charles Ashbacher, MAA Reviews, August 2012

When I used Discrete Mathematics with Ducks in class, I assigned readings, and my students came to class full of questions and ideas. Every day we had a good time in one way or another; these classes were a highlight of my teaching career. I give a lot of credit to this book, thanks to the author's skill at blending rigor, great examples, casual humor, and precise writing.

David Perkins, author of Calculus and Its Origins

I had a lot of fun teaching from Discrete Mathematics with Ducks! … I think the discovery/exploratory/problem solving approach is ABSOLUTELY the way this course should be taught, and of all the discrete books I have looked at, this text does the best job of supporting that kind of approach to the subject while still giving enough of the material in writing to fill in the gaps. … I found that the material provided and the instructor notes cut down on my prep time, and I definitely referred to them. Having the in-class activities included is a huge benefit to this book.

Dana Rowland, Associate Professor of Mathematics, Merrimack College

… an incredible book … readable by students, useful for instructors, and constructed with style and flair. This book will make it much easier to teach an exciting, student-centered discrete mathematics course that will also serve as an excellent introduction to advanced critical thinking, problem solving, and proofs. And there are ducks!

—Douglas Shaw, Professor of Mathematics, University of Northern Iowa

Table of Contents

THE BASICS

Counting and Proofs

Introduction and Summary

Try This! Let’s Count

The Sum and Product Principles

Preliminaries on Proofs and Disproofs

Pigeons and Correspondences

Where to Go from Here

Sets and Logic

Introduction and Summary

Sets

Logic

Try This! Problems on Sets and Logic

Proof Techniques: Not!

Try This! A Tricky Conundrum

Where to Go from Here

Bonus: Truth Tellers

Graphs and Functions

Introduction and Summary

Function Introduction

Try This! Play with Functions and Graphs

Functions and Counting

Graphs: Definitions and Examples

Isomorphisms

Graphs: Operations and Uses

Try This! More Graph Problems

Ramseyness

Where to Go from Here

Bonus: Party Tricks

Bonus 2: Counting with the Characteristic Function

Induction

Introduction and Summary

Induction

Try This! Induction

More Examples

The Best Inducktion Proof Ever

Try This! More Problems about Induction

Are They or Aren’t They? Resolving Grey Ducks

Where to Go from Here

Bonus: Small Crooks

Bonus 2: An Induction Song

Algorithms with Ciphers

Introduction and Summary

Algorithms

Modular Arithmetic (and Equivalence Relations)

Cryptography: Some Ciphers

Try This! Encryptoequivalent Modulagorithmic Problems

Where to Go from Here

Bonus: Algorithms for Searching Graphs

Bonus 2: Pigeons and Divisibility

COMBINATORICS

Binomial Coefficients and Pascal’s Triangle

Introduction and Summary

You Have a Choice

Try This! Investigate a Triangle

Pascal’s Triangle

Overcounting Carefully and Reordering at Will

Try This! Play with Powers and Permutations

Binomial Basics

Combinatorial Proof

Try This! Pancakes and Proofs

Where to Go from Here

Bonus: Sorting Bubbles in Order of Size

Bonus 2: Mastermind

Balls and Boxes and PIE—Counting Techniques

Introduction and Summary

Combinatorial Problem Types

Try This! Let’s Have Some PIE

Combinatorial Problem Solutions and Strategies

Let’s Explain Our PIE!

Try This! What Are the Balls and What Are the Boxes? And Do You Want Some PIE?

Where to Go from Here

Bonus: Linear and Integer Programming

Recurrences

Introduction and Summary

Fibonacci Numbers and Identities

Recurrences and Integer Sequences and Induction

Try This! Sequences and Fibonacci Identities

Naive Techniques for Finding Closed Forms and Recurrences

Arithmetic Sequences and Finite Differences

Try This! Recurrence Exercises

Geometric Sequences and the Characteristic Equation

Try This! Find Closed Forms for These Recurrence Relations!

Where to Go from Here

Bonus: Recurring Stories

Cutting up Food (Counting and Geometry)

Introduction and Summary

Try This! Slice Pizza (and a Yam)

Pizza Numbers

Try This! Spaghetti, Yams, and More

Yam, Spaghetti and Pizza Numbers

Where to Go from Here

Bonus: Geometric Gems

GRAPH THEORY

Trees

Introduction and Summary

Basic Facts about Trees

Try This! Spanning Trees

Spanning Tree Algorithms

Binary Trees

Try This! Binary Trees and Matchings

Matchings

Backtracking

Where to Go from Here

Bonus: The Branch-and-Bound Technique in Integer Programming

Euler’s Formula and Applications

Introduction and Summary

Try This! Planarity Explorations

Planarity

A Lovely Story

Or, Are Emus Full?: A Theorem and a Proof

Applications of Euler’s Formula

Try This! Applications of Euler’s Formula

Where to Go from Here

Bonus: Topological Graph Theory

Graph Traversals

Introduction and Summary

Try This! Euler Traversals

Euler Paths and Circuits

Hamilton Circuits, the Traveling Salesperson Problem, and Dijkstra’s Algorithm

Try This!—Do This!—Try This!

Where to Go from Here

Bonus: Digraphs, Euler Traversals, and RNA Chains

Bonus 2: Network Flows

Bonus 3: Two Hamiltonian Theorems

Graph Coloring

Introduction and Summary

Try This! Coloring Vertices and Edges

Introduction to Coloring

Try This! Let’s Think about Coloring

Coloring and Things (Graphs and Concepts) That Have Come Before

Where to Go from Here

Bonus: The Four-Color Theorem

OTHER MATERIAL

Probability and Expectation

Introduction and Summary

What Is Probability, Exactly?

High Expectations

You are Probably Expected to Try This!

Conditional Probability and Independence

Try This! . . . Probably, Under Certain Conditions

Higher Expectations

Where to Go from Here

Bonus: Ramsey Numbers and the Probabilistic Method

Fun with Cardinality

Introduction and Summary

Read This! Parasitology, The Play

How Big Is Infinite?

Try This! Investigating the Play

How High Can We Count?

Where to Go from Here

Bonus: The Schröder–Bernstein Theorem

Additional Problems

Solutions to Check Yourself Problems

The Greek Alphabet and Some Uses for Some Letters

List of Symbols

Glossary

Bibliography

Problems and Instructor Notes appear at the end of each chapter.

About the Originator

Subject Categories

BISAC Subject Codes/Headings:
COM046000
COMPUTERS / Operating Systems / General
MAT000000
MATHEMATICS / General
MAT036000
MATHEMATICS / Combinatorics