Mathematical Structures for Computer Science

by Gersting, Judith L.

• ISBN13: 9781429215107
• ISBN10: 1429215100
• Edition: 7th
• Format: Hardcover
• Copyright: 2014-01-01
• Publisher: W. H. Freeman

Summary

With a clear presentation of essential concepts, Mathematical Structures for Computer Science demonstrates a wide range of applications relevant to computer science majors.

Table of Contents

1.  Formal Logic         

1.1  Statements, Symbolic Representation, and Tautologies   
Connectives and Truth Values      
Tautologies         
Logical Connectives in the Real World     
An Algorithm        
Special Interest Page – Can "And" Ever Be "Or"?
Section 1.1 Review 
Exercises 1.1         

1.2  Propositional Logic        
Valid Arguments        
Derivation Rules for Propositional Logic     
Deduction Method and Other Rules     
Verbal Arguments        
Section 1.2 Review 
Exercises 1.2         

1.3  Quantifiers, Predicates, and Validity      
Quantifiers and Predicates       
Translation         
Validity         
Section 1.3 Review 
Exercises 1.3         

1.4  Predicate Logic        
Derivation Rules for Predicate Logic     
Universal Instantiation      
Existential Instantiation      
Universal Generalization      
Existential Generalization      
More Work with Rules       
Verbal Arguments        
Conclusion         
Section 1.4 Review 
Exercises 1.4         

1.5  Logic Programming        
Prolog         
Horn Clauses and Resolution      
Recursion         
Expert Systems        
Section 1.5 Review 
Exercises 1.5         

1.6  Proof of Correctness        
Assertions         
Assignment Rule        
Conditional Rule        
Section 1.6 Review 
Exercises 1.6         

Chapter 1 Review         
On the Computer         

2.  Proofs, Induction, and Number Theory      

2.1  Proof Techniques        
Theorems and Informal Proofs      
To Prove or Not to Prove       
Exhaustive Proof        
Direct Proof        
Contraposition        
Contradiction        
Serendipity         
Common Definitions       
Section 2.1 Review 
Exercises 2.1         

2.2  Induction           
First Principle of Induction   
Proofs by Mathematical Induction 
Second Principle of Induction 
Section 2.2 Review 
Exercises 2.2 

2.3  More on Proof of Correctness 
Loop Rule 
Euclidean Algorithm 
Special Interest Page – Making Safer Software 
Section 2.3 Review 
Exercises 2.3

2.4  Number Theory 
The Fundamental Theorem of Arithmetic  
More on Prime Numbers 
Euler Phi Function
Section 2.4 Review 
Exercises 2.4 

Chapter 2 Review 
On the Computer

3.  Recursion, Recurrence Relations, and Analysis of Algorithms

3.1  Recursive Definitions 
Recursively Defined Sequences 
Recursively Defined Sets 
Recursively Defined Operations 
Recursively Defined Algorithms
Section 3.1 Review
Exercises 3.1 

3.2  Recurrence Relations  
Linear First-Order Recurrence Relations 
Expand, Guess, and Verify 
A Solution Formula 
Linear Second-Order Recurrence Relations 
Divide-and-Conquer Recurrence Relations 
Section 3.2 Review
Exercises 3.2 

3.3  Analysis of Algorithms 
The General Idea 
Analysis Using Recurrence Relations  
Upper Bound (Euclidean Algorithm) 
Special Interest Page - Of Trees … and Pancakes
Section 3.3 Review
Exercises 3.3 

Chapter 3 Review 
On the Computer 

4.  Sets, Combinatorics, and Probability   

4.1  Sets  
Notation 
Relationships between Sets 
Sets of Sets 
Binary and Unary Operations 
Operations on Sets 
Set Identities 
Countable and Uncountable Sets 
Section 4.1 Review
Exercises 4.1 

4.2  Counting 
Multiplication Principle 
Addition Principle 
Using the Principles Together 
Decision Trees 
Section 4.2 Review
Exercises 4.2 
  
4.3  Principle of Inclusion and Exclusion; Pigeonhole Principle 
Principle of Inclusion and Exclusion 
Pigeonhole Principle 
Section 4.3 Review 
Exercises 4.3 

4.4  Permutations and Combinations 
Permutations 
Combinations 
Eliminating Duplicates 
Permutations and Combinations with Repetitions
Generating Permutations and Combinations
Special Interest Page – Archimedes and the Stomachion 
Section 4.4 Review
Exercises 4.4 

4.5 Binomial Theorem 
Pascal's Triangle 
Binomial Theorem and Its Proof 
Applying the Binomial Theorem 
Section 4.5 Review
Exercises 4.5

4.6   Probability 
Introduction to Finite Probability 
Probability Distributions 
Conditional Probability
Bayes' Theorem 
Expected Value 
Binomial Distribution 
Average Case Analysis of Algorithms
Section 4.5 Review
Exercises 4.6 

Chapter 4 Review 
On the Computer  

5.  Relations, Functions, and Matrices 

5.1  Relations 
Binary Relations 
Properties of Relations 
Closures of Relations 
Partial Orderings 
Equivalence Relations 
Section 5.1 Review
Exercises 5.1 

5.2  Topological Sorting 
Section 5.2 Review
Exercises 5.2 

5.3  Relations and Databases 
Entity-Relationship Model 
Relational Model 
Operations on Relations 
Null Values and Three-Valued Logic 
Database Integrity 
Section 5.3 Review
Exercises 5.3 

5.4  Functions 
Definition 
Properties of Functions 
Onto Functions 
One-to-One Functions 
Bijections 
Composition of Functions 
Inverse Functions 
Permutation Functions 
How Many Functions 
Equivalent Sets  
Section 5.4 Review
Exercises 5.4 

5.5  Order of Magnitude
Function Growth
More on Analysis of Algorithms 
The Master Theorem
Proof of the Master Theorem
Section 5.5 Review
Exercises 5.5

5.6  The Mighty Mod Function 
Hashing 
Computer Security  
Cryptography 
Hashing for Password Encryption 
Miscellaneous Applications 
Identification Codes 
Generating and Decomposing Integers 
Modular Arithmetic Designs 
Section 5.6 Review 
Exercises 5.6 
    
5.7 Matrices 
Terminology 
Matrix Operations
Gaussian Elimination 
Boolean Matrices
Special Interest Page - Solve Millions of Equations, Faster than Gauss
Section 5.7 Review
Exercises 5.7 
 
Chapter 5 Review 
On the Computer  

6.  Graphs and Trees  

6.1  Graphs and their Representations 
Definitions of a Graph 
Applications of Graphs 
Graph Terminology 
Isomorphic Graphs 
Planar Graphs 
Computer Representation of Graphs 
Adjacency Matrix 
Adjacency List
Special Interest Page - Isomorphic Protein Graphs 
Section 6.1 Review
Exercises 6.1 

6.2  Trees and their Representations 
Tree Terminology 
Applications of Trees 
Binary Tree Representation 
Tree Traversal Algorithms 
Results About Trees 
Section 6.2 Review
Exercises 6.2  
  
6.3  Decision Trees 
Searching 
Lower Bounds on Searching 
Binary Tree Search 
Sorting 
Section 6.3 Review
Exercises 6.3 

6.4  Huffman Codes 
Problem and Trial Solution 
Huffman Encoding Algorithm 
Justification 
Application of Huffman Codes
Section 6.4 Review
Exercises 6.4 
 
Chapter 6 Review 
On the Computer  

7.  Graph Algorithms 

7.1  Directed Graphs and Binary Relations; Warshall's Algorithm 
Directed Graphs and Binary Relations 
Reachability 
Warshall's Algorithm 
Section 7.1 Review
Exercises 7.1 

7.2  Euler Path and Hamiltonian Circuit 
Euler Path Problem 
Hamiltonian Circuit Problem 
Section 7.2 Review
Exercises 7.2 

7.3  Shortest Path and Minimal Spanning Tree 
Shortest-Path Problem 
Minimal Spanning Tree Problem
Special Interest Page - Pathfinding
Section 7.3 Review 
Exercises 7.3 

7.4  Traversal Algorithms 
Depth-First Search 
Breadth-First Search 
Analysis 
Applications 
Section 7.4 Review
Exercises 7.4 

7.5  Articulation Points and Computer Networks 
The Problem Statement 
The Idea Behind the Algorithm 
The Algorithm Itself 
Section 7.5 Review
Exercises 7.5

Chapter 7 Review 
On the Computer  

8.  Boolean Algebra and Computer Logic 

8.1 Boolean Algebra Structure 
Models or Abstractions 
Definition and Properties 
Isomorphic Boolean Algebras 
What is Isomorphism? 
Isomorphism as Applied to Boolean Algebra 
Section 8.1 Review
Exercises 8.1 

8.2  Logic Networks 
Combinational Networks 
Basic Logic Elements 
Boolean Expressions 
Truth Functions 
Networks and Expressions 
Canonical Form 
Minimization 
Programmable Logic Devices 
A Useful Network 
Other Logic Elements 
Constructing Truth Functions
Special Interest Page - Pruning Chips and Programs 
Section 8.2 Review
Exercises 8.2 

8.3  Minimization 
Minimization Process 
Karnaugh Map 
Maps for Three and Four Variables 
Using the Karnaugh Map 
Quine-McCluskey Procedure 
Section 8.3 Review
Exercises 8.3 

Chapter 8 Review 
On the Computer  

9.  Modeling Arithmetic, Computation, and Languages
9.1  Algebraic Structures 
Definitions and Examples 
Basic Results about Groups 
Subgroups 
Isomorphic Groups
Section 9.1 Review   
Exercises 9.1

9.2  Coding Theory 
Introduction
Background: Homomorphisms and Cosets
Generating Group Codes
Decoding Group Codes 
Section 9.2 Review
Exercises 9.2

9.3  Finite-State Machines 
Definition 
Examples of Finite-State Machines  
Recognition  
Regular Sets and Kleene's Theorem 
Machine Minimization 
Unreachable States 
Minimization Procedure 
Sequential Networks and Finite-State Machines
Special Interest Page – FSMs Behind the Game 
Section 9.3 Review
Exercises 9.3 

9.4  Turing Machines 
Definition 
Turing Machines as Set Recognizers 
Turing Machines as Function Computers 
Church-Turing Thesis 
Decision Problems and Uncomputability 
Examples of Decision Problems 
Halting Problem 
Computational Complexity 
Section 9.4 Review
Exercises 9.4 

9.5  Formal Languages 
Classes of Grammars 
Formal Languages and Computational Devices 
Context-Free Grammars 
Section 9.5 Review
Exercises 9.5 

Chapter 9 Review 
On the Computer 

Appendix A    Derivation Rules for Propositional and Predicate Logic 
Appendix B Summation and Product Notation
Appendix C The Logarithm Function
Appendix D  The Binary Number System

Answers to Practice Problems
Answers to Odd-Numbered Exercises
Answers to Self-Tests
Index