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