Discrete Mathematics for Computer Science (with Student Solutions Manual CD-ROM)

by Haggard, Gary; Schlipf, John; Whitesides, Sue

• ISBN13: 9780534495015
• ISBN10: 053449501X
• Edition: 1st
• Format: Hardcover
• Copyright: 2005-02-01
• Publisher: Cengage Learning

Summary

Master the fundamentals of discrete mathematics with DISCRETE MATHEMATICS FOR COMPUTER SCIENCE with Student Solutions Manual CD-ROM! An increasing number of computer scientists from diverse areas are using discrete mathematical structures to explain concepts and problems and this mathematics text shows you how to express precise ideas in clear mathematical language. Through a wealth of exercises and examples, you will learn how mastering discrete mathematics will help you develop important reasoning skills that will continue to be useful throughout your career.

Table of Contents

CHAPTER 1 Sets, Proof Templates, and Induction	1	(88)
1.1 Basic Definitions	1	(12)
1.1.1 Describing Sets Mathematically	2	(2)
1.1.2 Set Membership	4	(1)
1.1.3 Equality of Sets	4	(1)
1.1.4 Finite and Infinite Sets	5	(1)
1.1.5 Relations Between Sets	5	(2)
1.1.6 Venn Diagrams	7	(1)
1.1.7 Templates	8	(5)
1.2 Exercises	13	(2)
1.3 Operations on Sets	15	(16)
1.3.1 Union and Intersection	15	(5)
1.3.2 Set Difference, Complements, and DeMorgan's Laws	20	(6)
1.3.3 New Proof Templates	26	(2)
1.3.4 Power Sets and Products	28	(1)
1.3.5 Lattices and Boolean Algebras	28	(3)
1.4 Exercises	31	(3)
1.5 The Principle of Inclusion-Exclusion	34	(8)
1.5.1 Finite Cardinality	34	(2)
1.5.2 Principle of Inclusion-Exclusion for Two Sets	36	(1)
1.5.3 Principle of Inclusion-Exclusion for Three Sets	37	(4)
1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets	41	(1)
1.6 Exercises	42	(3)
1.7 Mathematical Induction	45	(11)
1.7.1 A First Form of Induction	45	(4)
1.7.2 A Template for Constructing Proofs by Induction	49	(2)
1.7.3 Application: Fibonacci Numbers	51	(2)
1.7.4 Application: Size of a Power Set	53	(1)
1.7.5 Application: Geometric Series	54	(2)
1.8 Program Correctness	56	(6)
1.8.1 Pseudocode Conventions	56	(2)
1.8.2 An Algorithm to Generate Perfect Squares	58	(1)
1.8.3 Two Algorithms for Computing Square Roots	58	(4)
1.9 Exercises	62	(4)
1.10 Strong Form of Mathematical Induction	66	(13)
1.10.1 Using the Strong Form of Mathematical Induction	69	(3)
1.10.2 Application: Algorithm to Compute Powers	72	(3)
1.10.3 Application: Finding Factorizations	75	(2)
1.10.4 Application: Binary Search	77	(2)
1.11 Exercises	79	(2)
1.12 Chapter Review	81	(8)
1.12.1 Summary	82	(2)
1.12.2 Starting to Review	84	(1)
1.12.3 Review Questions	85	(2)
1.12.4 Using Discrete Mathematics in Computer Science	87	(2)
CHAPTER 2 Formal Logic	89	(68)
2.1 Introduction to Propositional Logic	89	(10)
2.1.1 Formulas	92	(2)
2.1.2 Expression Trees for Formulas	94	(3)
2.1.3 Abbreviated Notation for Formulas	97	(1)
2.1.4 Using Gates to Represent Formulas	98	(1)
2.2 Exercises	99	(3)
2.3 Truth and Logical Truth	102	(14)
2.3.1 Tautologies	106	(3)
2.3.2 Substitutions into Tautologies	109	(1)
2.3.3 Logically Valid Inferences	109	(3)
2.3.4 Combinatorial Networks	112	(2)
2.3.5 Substituting Equivalent Subformulas	114	(1)
2.3.6 Simplifying Negations	115	(1)
2.4 Exercises	116	(5)
2.5 Normal Forms	121	(10)
2.5.1 Disjunctive Normal Form	122	(2)
2.5.2 Application: DNF and Combinatorial Networks	124	(1)
2.5.3 Conjunctive Normal Form	125	(2)
2.5.4 Application: CNF and Combinatorial Networks	127	(1)
2.5.5 Testing Satisfiability and Validity	127	(2)
2.5.6 The Famous P not equal NP Conjecture	129	(1)
2.5.7 Resolution Proofs: Automating Logic	129	(2)
2.6 Exercises	131	(3)
2.7 Predicates and Quantification	134	(9)
2.7.1 Predicates	135	(1)
2.7.2 Quantification	135	(1)
2.7.3 Restricted Quantification	136	(1)
2.7.4 Nested Quantifiers	137	(1)
2.7.5 Negation and Quantification	138	(1)
2.7.6 Quantification with Conjunction and Disjunction	139	(2)
2.7.7 Application: Loop Invariant Assertions	141	(2)
2.8 Exercises	143	(4)
2.9 Chapter Review	147	(10)
2.9.1 Summary	148	(1)
2.9.2 Starting to Review	149	(1)
2.9.3 Review Questions	150	(1)
2.9.4 Using Discrete Mathematics in Computer Science	151	(6)
CHAPTER 3 Relations	157	(62)
3.1 Binary Relations	157	(6)
3.1.1 n-ary Relations	162	(1)
3.2 Operations on Binary Relations	163	(3)
3.2.1 Inverses	163	(2)
3.2.2 Composition	165	(1)
3.3 Exercises	166	(1)
3.4 Special Types of Relations	167	(11)
3.4.1 Reflexive and Irreflexive Relations	168	(1)
3.4.2 Symmetric and Antisymmetric Relations	169	(3)
3.4.3 Transitive Relations	172	(1)
3.4.4 Reflexive, Symmetric, and Transitive Closures	173	(3)
3.4.5 Application: Transitive Closures in Medicine and Engineering	176	(2)
3.5 Exercises	178	(3)
3.6 Equivalence Relations	181	(7)
3.6.1 Partitions	183	(3)
3.6.2 Comparing Equivalence Relations	186	(2)
3.7 Exercises	188	(3)
3.8 Ordering Relations	191	(10)
3.8.1 Partial Orderings	191	(3)
3.8.2 Linear Orderings	194	(2)
3.8.3 Comparable Elements	196	(1)
3.8.4 Optimal Elements in Orderings	196	(2)
3.8.5 Application: Finding a Minimal Element	198	(2)
3.8.6 Application: Embedding a Partial Order	200	(1)
3.9 Exercises	201	(1)
3.10 Relational Databases: An Introduction	202	(9)
3.10.1 Storing Information in Relations	203	(1)
3.10.2 Relational Algebra	204	(7)
3.11 Exercises	211	(1)
3.12 Chapter Review	212	(7)
3.12.1 Summary	213	(2)
3.12.2 Starting to Review	215	(1)
3.12.3 Review Questions	216	(1)
3.12.4 Using Discrete Mathematics in Computer Science	217	(2)
CHAPTER 4 Functions	219	(64)
4.1 Basic Definitions	219	(20)
4.1.1 Functions as Rules	221	(1)
4.1.2 Functions as Sets	222	(2)
4.1.3 Recursively Defined Functions	224	(1)
4.1.4 Graphs of Functions	225	(1)
4.1.5 Equality of Functions	226	(2)
4.1.6 Restrictions of Functions	228	(1)
4.1.7 Partial Functions	229	(2)
4.1.8 1-1 and Onto Functions	231	(6)
4.1.9 Increasing and Decreasing Functions	237	(2)
4.2 Exercises	239	(4)
4.3 Operations on Functions	243	(5)
4.3.1 Composition of Functions	243	(2)
4.3.2 Inverses of Functions	245	(3)
4.3.3 Other Operations on Functions	248	(1)
4.4 Sequences and Subsequences	248	(3)
4.5 Exercises	251	(2)
4.6 The Pigeon-Hole Principle	253	(9)
4.6.1 k to 1 Functions	254	(1)
4.6.2 Proofs of the Pigeon-Hole Principle	255	(2)
4.6.3 Application: Decimal Expansion of Rational Numbers	257	(2)
4.6.4 Application: Problems with Divisors and Schedules	259	(1)
4.6.5 Application: Two Combinatorial Results	260	(2)
4.7 Exercises	262	(2)
4.8 Countable and Uncountable Sets	264	(9)
4.8.1 Countably Infinite Sets	266	(2)
4.8.2 Cantor's First Diagonal Argument	268	(2)
4.8.3 Uncountable Sets and Cantor's Second Diagonal Argument	270	(3)
4.8.4 Cardinalities of Power Sets	273	(1)
4.9 Exercises	273	(2)
4.10 Chapter Review	275	(8)
4.10.1 Summary	275	(2)
4.10.2 Starting to Review	277	(2)
4.10.3 Review Questions	279	(1)
4.10.4 Using Discrete Mathematics in Computer Science	280	(3)
CHAPTER 5 Analysis of Algorithms	283	(48)
5.1 Comparing Growth Rates of Functions	284	(12)
5.1.1 A Measure for Comparing Growth Rates	284	(5)
5.1.2 Properties of Asymptotic Domination	289	(2)
5.1.3 Polynomial Functions	291	(2)
5.1.4 Exponential and Logarithmic Functions	293	(3)
5.2 Exercises	296	(2)
5.3 Complexity of Programs	298	(15)
5.3.1 Counting Statements	300	(2)
5.3.2 Two Algorithms Illustrating Selection	302	(2)
5.3.3 An Algorithm Illustrating Repetition	304	(3)
5.3.4 An Algorithm Illustrating Nested Repetition	307	(1)
5.3.5 Time Complexity of an Algorithm	308	(3)
5.3.6 Variants on the Definition of Complexity	311	(2)
5.4 Exercises	313	(3)
5.5 Uncomputability	316	(5)
5.5.1 The Halting Problem	318	(3)
5.6 Chapter Review	321	(10)
5.6.1 Summary	321	(1)
5.6.2 Starting to Review	322	(1)
5.6.3 Review Questions	322	(1)
5.6.4 Using Discrete Mathematics in Computer Science	323	(8)
CHAPTER 6 Graph Theory	331	(90)
6.1 Introduction to Graph Theory	331	(7)
6.1.1 Definitions	334	(2)
6.1.2 Subgraphs	336	(2)
6.2 The Handshaking Problem	338	(2)
6.3 Paths and Cycles	340	(5)
6.3.1 Hamiltonian Cycles	341	(4)
6.4 Graph Isomorphism	345	(1)
6.5 Representation of Graphs	346	(2)
6.5.1 Adjacency Matrix	346	(1)
6.5.2 Adjacency Lists	347	(1)
6.6 Exercises	348	(4)
6.7 Connected Graphs	352	(9)
6.7.1 The Relation CONN	352	(2)
6.7.2 Depth First Search	354	(3)
6.7.3 Complexity of Dfs	357	(1)
6.7.4 Breadth First Search	357	(2)
6.7.5 Finding Connected Components	359	(2)
6.8 The Konigsberg Bridge Problem	361	(6)
6.8.1 Graph Tracing	365	(2)
6.9 Exercises	367	(3)
6.10 Trees	370	(4)
6.10.1 Definition of Trees	371	(1)
6.10.2 Characterization of Trees	372	(2)
6.11 Spanning Trees	374	(4)
6.11.1 Kruskal's Algorithm	374	(1)
6.11.2 Correctness of Kruskal's Algorithm	375	(1)
6.11.3 Kruskal's Algorithm for Weighted Graphs	376	(2)
6.11.4 Correctness of Kruskal's Weighted Graph Algorithm	378	(1)
6.12 Rooted Trees	378	(11)
6.12.1 Binary Trees	380	(2)
6.12.2 Binary Search Trees	382	(3)
6.12.3 Tree Traversals	385	(2)
6.12.4 Application: Decision Trees	387	(2)
6.13 Exercises	389	(3)
6.14 Directed Graphs	392	(2)
6.14.1 Basic Definitions	393	(1)
6.14.2 Directed Trails, Paths, Circuits, and Cycles	394	(1)
6.14.3 Directed Graph Isomorphism	394	(1)
6.15 Application: Scheduling a Meeting Facility	394	(3)
6.15.1 WAITFOR Graphs	396	(1)
6.16 Finding a Cycle in a Directed Graph	397	(2)
6.16.1 Directed Cycle Detection Algorithm	397	(1)
6.16.2 Correctness of Directed Cycle Detection	398	(1)
6.17 Priority in Scheduling	399	(3)
6.17.1 Algorithm for Topological Sort	400	(1)
6.17.2 Correctness of Topological Sort Algorithm	401	(1)
6.18 Connectivity in Directed Graphs	402	(3)
6.18.1 Strongly Connected Directed Graphs	402	(2)
6.18.2 Application: Designing One-Way Street Grids	404	(1)
6.19 Eulerian Circuits in Directed Graphs	405	(1)
6.20 Exercises	406	(3)
6.21 Chapter Review	409	(12)
6.21.1 Summary	409	(2)
6.21.2 Starting to Review	411	(2)
6.21.3 Review Questions	413	(3)
6.21.4 Using Discrete Mathematics in Computer Science	416	(5)
CHAPTER 7 Counting and Combinatorics	421	(54)
7.1 Traveling Salesperson's Problem	421	(2)
7.2 Counting Principles	423	(5)
7.2.1 The Multiplication Principle	424	(2)
7.2.2 Addition Principle	426	(2)
7.3 Set Decomposition Principle	428	(5)
7.3.1 Counting the Complement	429	(1)
7.3.2 Using the Pigeon-Hole Principle	430	(2)
7.3.3 Application: UNIX Logon Passwords	432	(1)
7.4 Exercises	433	(3)
7.5 Permutations and Combinations	436	(10)
7.5.1 Permutations	436	(1)
7.5.2 Linear Arrangements	437	(2)
7.5.3 Circular Permutations	439	(1)
7.5.4 Combinations	440	(1)
7.5.5 Poker Hands	441	(2)
7.5.6 Counting the Complement	443	(1)
7.5.7 Decomposition into Subproblems	444	(2)
7.6 Constructing the kth Permutation	446	(2)
7.7 Exercises	448	(3)
7.8 Counting with Repeated Objects	451	(6)
7.8.1 Permutations with Repetitions	452	(3)
7.8.2 Combinations with Repetitions	455	(2)
7.9 Combinatorial Identities	457	(12)
7.9.1 Binomial Coefficients	459	(3)
7.9.2 Multinomials	462	(1)
7.10 Pascal's Triangle	463	(2)
7.11 Exercises	465	(4)
7.12 Chapter Review	469	(6)
7.12.1 Summary	470	(1)
7.12.2 Starting to Review	471	(1)
7.12.3 Review Questions	471	(1)
7.12.4 Using Discrete Mathematics in Computer Science	472	(3)
CHAPTER 8 Discrete Probability	475	(74)
8.1 Ideas of Chance in Computer Science	475	(13)
8.1.1 Introductory Examples	476	(2)
8.1.2 Basic Definitions	478	(2)
8.1.3 Frequency Interpretation of Probability	480	(1)
8.1.4 Introductory Example Reconsidered	480	(2)
8.1.5 The Combinatorics of Uniform Probability Density	482	(2)
8.1.6 Set Theory and the Probability of Events	484	(4)
8.2 Exercises	488	(3)
8.3 Cross Product Sample Spaces	491	(14)
8.3.1 A Multiplication Principle	492	(3)
8.3.2 The Cross Product of Sample Spaces	495	(3)
8.3.3 Bernoulli Trial Processes	498	(2)
8.3.4 Events of Cross Product Form	500	(2)
8.3.5 Two Ways of Viewing Events	502	(3)
8.4 Exercises	505	(2)
8.5 Independent Events and Conditional Probability	507	(10)
8.5.1 Independent Events	507	(2)
8.5.2 Introduction to Conditional Probability	509	(3)
8.5.3 Exploring Conditional Probability	512	(2)
8.5.4 Using Bayes' Rule with the Theorem of Total Probability	514	(3)
8.6 Exercises	517	(3)
8.7 Discrete Random Variables	520	(9)
8.7.1 Distributions of a Random Variable	520	(2)
8.7.2 The Binomial Distribution	522	(1)
8.7.3 The Hypergeometric Distribution	522	(2)
8.7.4 Expectation of a Random Variable	524	(2)
8.7.5 The Sum of Random Variables	526	(3)
8.8 Exercises	529	(1)
8.9 Variance, Standard Deviation, and the Law of Averages	530	(10)
8.9.1 Variance and Standard Deviation	531	(2)
8.9.2 Independent Random Variables	533	(6)
8.10 Exercises	539	(1)
8.11 Chapter Review	540	(9)
8.11.1 Summary	541	(1)
8.11.2 Starting to Review	542	(1)
8.11.3 Review Questions	543	(2)
8.11.4 Using Discrete Mathematics in Computer Science	545	(4)
CHAPTER 9 Recurrence Relations	549	(38)
9.1 The Tower of Hanoi Problem	549	(5)
9.1.1 Recurrence Relation for the Tower of Hanoi Problem	552	(1)
9.1.2 Solving the Tower of Hanoi Recurrence	552	(2)
9.2 Solving First-Order Recurrence Relations	554	(4)
9.2.1 Solving First-Order Recurrences Using Back Substitution	555	(3)
9.3 Exercises	558	(3)
9.4 Fibonacci Recurrence Relation	561	(6)
9.4.1 Second Order-Recurrence Relations	562	(2)
9.4.2 Solving the Fibonacci Recurrence	564	(2)
9.4.3 Rules for Solving Second-Order Recurrence Relations	566	(1)
9.5 Exercises	567	(1)
9.6 Divide and Conquer Paradigm	568	(1)
9.7 Binary Search	568	(3)
9.7.1 Correctness	569	(1)
9.7.2 Complexity	570	(1)
9.8 Merge Sort	571	(2)
9.8.1 Correctness	571	(1)
9.8.2 Example	572	(1)
9.8.3 Complexity	572	(1)
9.9 Multiplication of n-Bit Numbers	573	(3)
9.10 Divide-and-Conquer Recurrence Relations	576	(3)
9.10.1 Complexity of Divide-and-Conquer Recurrence Relations	579	(1)
9.11 Exercises	579	(1)
9.12 Chapter Review	580	(7)
9.12.1 Summary	581	(1)
9.12.2 Starting to Review	582	(1)
9.12.3 Review Questions	582	(1)
9.12.4 Using Discrete Mathematics in Computer Science	583	(4)
Appendix A	587	(4)
Appendix B	591	(4)
Index	595