Fundamentals of Discrete Structures

by Weiss, Gary M; Lyons, Damian M; Papadakis-Kanaris, Christina; Werschulz, Arthur G

• ISBN13: 9780558837976
• ISBN10: 0558837972
• Edition: 1st
• Format: Paperback
• Copyright: 2010-01-01
• Publisher: Pearson Learning Solutions

Table of Contents

Introduction	p. 1
Sets and Sequences	p. 9
Sets	p. 10
Basic Definitions	p. 10
Naming and Describing Sets	p. 14
Comparison Relations on Sets	p. 17
Set Operators	p. 19
Principle of Inclusion/Exclusion	p. 29
Sequences	p. 34
Numerical Sequences	p. 35
Describing Patterns in Sequences	p. 36
Summations	p. 43
Mathematical Induction	p. 45
Deductive Reasoning	p. 46
First Principle of Mathematical Induction	p. 47
Examples Using Mathematical Induction	p. 48
Logic	p. 63
Prepositional Logic	p. 64
Logical Operations	p. 66
Prepositional Forms	p. 71
Parse Trees and the Operator Hierarchy*	p. 73
From English to Propositions	p. 75
Prepositional Equivalences	p. 76
Prepositional Identities and Duality	p. 79
Predicate Logic	p. 81
Quantifiers	p. 83
Some Rules for Using Predicates	p. 85
Relations	p. 91
Ways to Describe Relations Between Objects	p. 02
Describing a Relation Using English	p. 93
Describing a Relation using a Picture	p. 96
Describing a Relation as a Subset of the Cartesian Product	p. 97
Properties of Relations	p. 100
Reflexivily	p. 100
Symmetry	p. 103
Transitivity	p. 106
Functions	p. 113
What is a Function?	p. 114
Functions and Relations	p. 119
Properties of Functions	p. 123
Function Composition	p. 127
Identity and Inverse Functions	p. 131
An Application: Cryptography	p. 138
Caesar Rotation	p. 139
Cryptography in Cyber-Commerce	p. 140
More About Functions	p. 141
Standard Mathematical Functions	p. 141
Growth Functions	p. 142
Functions in Program Construction	p. 144
An Application: Secure Storage of Passwords	p. 147
Counting	p. 153
Counting and How to Count	p. 154
Elementary Rules for Counting	p. 156
The Addition Rule	p. 156
The Multiplication Rule	p. 157
Using the Elementary Rules for Counting Together	p. 162
Permutations and Combinations	p. 164
Permutations	p. 165
Combinations	p. 167
Additional Examples	p. 169
Probability	p. 177
Terminology and Background	p. 178
Complement	p. 182
Elementary Rules for Probability	p. 183
The Elementary Addition Rule for Probability	p. 185
The Elementary Multiplication Rule for Probability	p. 187
General Rules for Probability	p. 189
The General Addition Rule for Probability	p. 190
The General Multiplication Rule for Probability	p. 192
Bernoulli Trials and Probability Distributions	p. 194
Expected Value	p. 196
Algorithms	p. 205
What is an Algorithm?	p. 206
Applications of Algorithms	p. 206
Searching and Sorting Algorithms	p. 208
Search Algorithms	p. 208
Sorting Algorithms	p. 211
Analysis of Algorithms	p. 215
How Do We Measure Efficiency?	p. 216
The Run-Time Complexity of an Algorithm	p. 216
Analysis of the Linear Search Algorithm	p. 219
Analysis of the Binary Search Algorithm	p. 219
Analysis of the Bubblesort Algorithm	p. 220
Big-O Notation*	p. 222
Graphs	p. 227
Graph Notation	p. 229
Vertices and Edges	p. 229
Directed and Undirected Graphs	p. 231
Complete Graphs	p. 232
Euler Trails and Circuits	p. 233
Walks, Trails, Circuits and Cycles	p. 233
Euler Circuits	p. 235
Weighted Graphs	p. 236
Minimum Spanning Tree	p. 238
Subgraphs and Spanning Trees	p. 239
Prim's Algorithm for the Minimum Spanning Tree	p. 240
Matrix Notation For Graphs	p. 242
Index	p. 254
Table of Contents provided by Ingram. All Rights Reserved.