| |
| |
| |
| Sets, Subsets, Induction and Recursion | |
| |
| |
| The Pascal Triangle (Application: A Counting Problem) | |
| |
| |
| Induction (Application: The Tower of Hanoi) | |
| |
| |
| Sets, Subsets, and Binary Strings (Application: The Knapsack Problem) | |
| |
| |
| Set Operations (Application: An Error-Correcting Code) | |
| |
| |
| Recursions (Application: Shift Registers) | |
| |
| |
| |
| Integers, Remainders, and the Golden Ratio | |
| |
| |
| The Integers (Application: When is Div(n)a Tree?) | |
| |
| |
| Lam�'s Theorem (Application: Egyptian Fractions) | |
| |
| |
| The Integers Modn(Application: Public Key Encryption) | |
| |
| |
| |
| Functions, Relations, and Counting | |
| |
| |
| Functions and Relations (Application: The Pr�fer Correspondence) | |
| |
| |
| Counting Rules (Application: Boolean Functions) | |
| |
| |
| Three Counting Techniques (Application: Tenth Powers) | |
| |
| |
| |
| Graphs | |
| |
| |
| Graphs (Application: The Icosahedron and Dodecahedron) | |
| |
| |
| Graph Theory (Application: One-Way Streets) | |
| |
| |
| Trees (Application: Structural Induction) | |
| |
| |
| |
| Proof Techniques and Logic | |
| |
| |
| Proof Techniques (Application: The Liar Problem) | |
| |
| |
| Logic (Application: Logic and the Genetic Code) | |
| |
| |
| The Propositional Calculus (Application: Syllogisms) | |
| |
| |
| |
| Boolean Algebras, Boolean Functions, and Logic | |
| |
| |
| Boolean Algebras and Functions (Application: Normal Forms in the Propositional Calculus) | |
| |
| |
| Boolean Functions and Circuits (Application: Regions in Logic Diagrams) | |
| |
| |
| The Predicate Calculus (Application: Proving Program Correctness) | |
| |
| |
| |
| Graphs and Relations | |
| |
| |
| Graph Coloring and Matching (Application: Register Allocation) | |
| |
| |
| Posets and Lattices (Application: The Kirkman Schoolgirl Problem) | |
| |
| |
| |
| Algorithms | |
| |
| |
| Sorting, Searching, and Listing (Application: The Man, Dog, Goat, and Cabbage Problem) | |
| |
| |
| Graph Algorithms (Application: Network Flows) | |
| |
| |
| The Complexity of an Algorithm (Application: Kruskal's Algorithm and Prim's Algorithm) | |
| |
| |
| |
| Combinatorics | |
| |
| |
| Recursions and Their Solution (Application: AVL trees) | |
| |
| |
| Probabilities (Application: Network Reliability) | |
| |
| |
| Groups and Counting (Application: Rooted Trees) | |
| |
| |
| |
| Models of Computation | |
| |
| |
| Languages and Grammars (Application: The Chomsky Heirarchy) | |
| |
| |
| Finite State Machines and Turing Machines (Application: DNA Computing) | |
| |
| |
| G�del and Turing (Application: The Vanishing) | |
| |
| |
| Appendices | |
| |
| |
| Guide to the Literature | |
| |
| |
| Notes | |
| |
| |
| Answers to Selected Exercises | |
| |
| |
| Index | |