Discrete Mathematics With Proof, Second Edition

Eric Gossett

John Wiley & Sons, Inc.

10 digit ISBN: 0470457937 13 digit ISBN: 9780470457931

Now available.

Second Edition Table of Contents

General Links

Textbook-Related Links

Review Material

Errors

A picture of a potential front cover.

General Links

Java

Several of the downloads will require the Java runtime system to be installed before they will run. The Java runtime system is free. The following links should get you close to the download pages.

Windows, Linux and other Unix systems Look for the "Downloads" link. You want the Java SE (Java Standard Edition). The JRE (Java Runtime Environment) is sufficient; you do not need the full JDK (Java Developer's Kit).
Macintosh, OS X and later comes with the Java runtime system pre-installed.

MathWorld

MathWorld is one of the best general math references on the web.

Table of Contents - a student commentary

How many chapters should you read?

Textbook-Related Links

Chapter 1

Chapter 2

Chapter Review

Chapter 3

Visualizing Induction
Chess Boards: The chess board example on pages 143, 144 was introduced by S. W. Golomb. See the paper Checker Boards and polyominoes, The American Mathematical Monthly, Vol. 61, No. 10 (Dec., 1954), pp. 675-682
Proof Strategies
Common Errors In Proofs
An Enigma Machine Emulator
Chapter Review

Chapter 4

Bloatbusters - look for the "down" links to read more
Dieter Bühler's Boyer-Moore and KMP emulator
- Download (right-click and save) the java application BoyerMoore.jar.
- You will need the java runtime system. Double-click the jar file, or from acmd or terminal window trype java -jar BoyerMoore.jar.
Halting Problem is Solvable, by Bala Rajagopalan
Chapter Review

Chapter 5

VCP: Visualizing Combinatorial Proofs
Amanda Nelson and Steven Yackel create a pizza in honor of the Pigeon Hole Principle.
Sacajawea Written by Lara Marks when she was a student at Washington University, St. Louis, Missouri. Used by permission.
Sacajawea From Native American Women
Chapter Review

Chapter 6

Chapter 7

RecursionDemo A Java application. Requires the java runtime system. Right-click and save the link. Double-click on RecursionDemo.jar to run the program.
Persian Rugs Application
Sierpinski Curves A Mathematica notebook. Right-click and save the link.
Adaptive Quadrature Demo A Java application. Requires the java runtime system. Right-click and save the link. Double-click on AQ.jar to run the program.
The Tower of Hanoi Puzzle
The impossibility of solving general quintics in radicals
Solving the Quintic with Mathematica
Some hints about early versions of the Josephus Problem. (Near the end of the article by David Singmaster.) Singmaster states elsewhere that Cardan was the first to connect this problem with Josephus (in 1539).
Chapter Review

Chapter 8

A pdf file that combines the proof of Theorem 8.13 and Example 8.8.
Instructors who have adopted the text may request code to solve knapsack problems. Code is currently available in Java.
The Extended version of Theorem 8.43 (Knapsack Heuristic)
A pdf file containing Examples 8.50 and 8.51 (illustrating Theorem 8.63).
Magic Squares
Western Square Dance
Chapter Review

Chapter 9

"Matthew Chapman's FSME - Finite State Machine Explorer A Java applet or application. Requires the java runtime system.
A web page for testing regular expressions.
dmgrep: a perl script for testing regular expressions Right-click and save the link.
Janelle Johnson's version of the Pumping Lemma.
Cookies and Finite State Automata - Elizabeth O'Connor, Emily Stavem, Janelle Johnson, Kelly Kirkwood
CPAN - the Comprehensive Perl Archive Network Look at the binary distributions link.
A regular expression that matches valid email addresses (full generality). From http://www.regexlib.com/DisplayPatterns.aspx
([a-zA-Z0-9_\-\.]+)@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.)|(([a-zA-Z0-9\-]+\.)+))([a-zA-Z]{2,4}|[0-9]{1,3})(\]?)
Chapter Review

Chapter 10

Modern Day Königsberg
- A satellite image of Kaliningrad from Google Maps. Two of the bridges have been removed (so the graph is now a simple graph).
- The fork in the river eventually rejoins.
The Sandbox Application. Requires the files Sandbox.jar and graph.dtd. Double-click on Sandbox.jar to run the program.
Note: Your web browser may try to save these files as zip or HTML files. Select "All Files" (if available) and make sure they are named exactly as shown on this web page.
- Sandbox.jar (version 1.1) Right-click and save the link.
- graph.dtd Right-click and save the link.
Sample data files for Sandbox. Right-click and save the link(s).
- Alien Spaceship
- Grotztsch
- Heawood
- Konigsberg
- K_3,3
- K₅
- Petersen
- Tutte
- Errera This graph can be used to show that the Kempe chain proof of the five color theorem (Theorem 10.53) cannot be modified to produce a proof of the four color theorem. The key idea is to color G' so that every vertex is adjacent to vertices with every other color.
An online game to find planar embeddings for planar graphs. It starts with easy examples and gets progressively more difficult.
The Tutte Graph
The graph for Exercise 21 on page 650.
http://www.maa.org/devlin/devlin_01_05.html: Last doubts removed about the proof of the Four Color Theorem from MAA Online
Dijkstra's algorithm (Table 10.6) and Table 10.8 on a single page.
Chapter Review