Ebook: Mathematics for Computer Science

This text explains how to use mathematical models and methods to analyze problems that arise in computer science. The subject offers an introduction to Discrete Mathematics oriented toward Computer Science and Engineering, adnd covers: Fundamental concepts of Mathematics: definitions, proofs, sets, functions, relations; Discrete structures: graphs, state machines, modular arithmetic, counting; Discrete probability theory.

Readers will be able
- to reason mathematically about basic data types and structures used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.
- to model and analyze computational processes using analytic and combinatorial methods.
- to apply principles of discrete probability to calculate probabilities and expectations of simple random processes.


Brief Contents
I Proofs
Introduction
1 What is a Proof?
2 The Well Ordering Principle
3 Logical Formulas
4 Mathematical Data Types
5 Induction
6 Recursive Data Types
7 Infinite Sets
8 Number Theory
II Structures
Introduction
9 Directed graphs & Partial Orders
10 Communication Networks
11 Simple Graphs
12 Planar Graphs
III Counting
Introduction
13 Sums and Asymptotics
14 Cardinality Rules
15 Generating Functions
IV Probability
Introduction
16 Events and Probability Spaces
17 Random Variables
18 Deviation from the Mean
19 Random Processes
V Recurrences
Introduction
20 Recurrences
Bibliography
Index
Glossary of Symbols

Contents
I Proofs
1 What is a Proof?
1.1 Propositions
1.2 Predicates
1.3 The Axiomatic Method
1.4 Our Axioms
1.5 Proving an Implication
1.6 Proving an “If and Only If”
1.7 Proof by Cases
1.8 Proof by Contradiction
1.9 Good Proofs in Practice
2 The Well Ordering Principle
2.1 Well Ordering Proofs
2.2 Template for Well Ordering Proofs
2.3 Factoring into Primes
2.4 Well Ordered Sets
3 Logical Formulas
3.1 Propositions from Propositions
3.2 Propositional Logic in Computer Programs
3.3 Equivalence and Validity
3.4 The Algebra of Propositions
3.5 The SAT Problem
3.6 Predicate Formulas
4 Mathematical Data Types
4.1 Sets
4.2 Sequences
4.3 Functions
4.4 Binary' Relations
4.5 Finite Cardinality
5 Induction
5.1 Ordinary Induction
5.2 Strong Induction
5.3 Strong Induction vs. Induction vs. Well Ordering
5.4 State Machines
6 Recursive Data Types
6.1 Recursive Definitions and Structural Induction
6.2 Strings of Matched Brackets
6.3 Recursive Functions on Nonnegative Integers
6.4 Arithmetic Expressions
6.5 Induction in Computer Science
7 Infinite Sets
7.1 Infinite Cardinality
7.2 The Halting Problem
7.3 The Logic of Sets
7.4 Does All This Really Work?
8 Number Theory
8.1 Divisibility
8.2 The Greatest Common Divisor
8.3 Prime Mysteries
8.4 The Fundamental Theorem of Arithmetic
8.5 Alan Turing
8.6 Modular Arithmetic
8.7 Remainder Arithmetic
8.8 Turing’s Code (Version 2.0)
8.9 Multiplicative Inverses and Cancelling
8.10 Euler’s Theorem
8.11 RSA Public Key Encryption
8.12 What has SAT got to do with it?
II Structures
9 Directed graphs & Partial Orders
9.1 Digraphs & Vertex Degrees
9.2 Adjacency Matrices
9.3 Walk Relations
9.4 Directed Acyclic Graphs & Partial Orders
9.5 Weak Partial Orders
9.6 Representing Partial Orders by Set Containment
9.7 Path-Total Orders
9.8 Product Orders
9.9 Scheduling
9.10 Equivalence Relations
9.11 Summary of Relational Properties
10 Communication Networks
10.1 Complete Binary Tree
10.2 Routing Problems
10.3 Network Diameter
10.4 Switch Count
10.5 Network Latency
10.6 Congestion
10.7 2-D Array
10.8 Butterfly
10.9 BeneS Network
11 Simple Graphs
11.1 Vertex Adjacency and Degrees
11.2 Sexual Demographics in America
11.3 Some Common Graphs
11.4 Isomorphism
11.5 Bipartite Graphs & Matchings
11.6 The Stable Marriage Problem
11.7 Coloring
11.8 Getting from u to v in a Graph
11.9 Connectivity
11.10 Odd Cycles and 2-Colorability
11.11 Forests & Trees
12 Planar Graphs
12.1 Drawing Graphs in the Plane
12.2 De finitions of Planar Graphs
12.3 Euler’s Formula
12.4 Bounding the Number of Edges in a Planar Graph
12.5 Returning to K5 and 3
12.6 Coloring Planar Graphs
12.7 Classifying Polyhedra
12.8 Another Characterization for Planar Graphs
III Counting
13 Sums and Asymptotics
13.1 The Value of an Annuity
13.2 Sums of Powers
13.3 Approximating Sums
13.4 Hanging Out Over the Edge
13.5 Products
13.6 Double Trouble
13.7 Asymptotic Notation
14 Cardinality Rules
14.1 Counting One Thing by Counting Another
14.2 Counting Sequences
14.3 The Generalized Product Rule
14.4 The Division Rule
14.5 Counting Subsets
14.6 Sequences with Repetitions
14.7 Counting Practice: Poker Hands
14.8 The Pigeonhole Principle
14.9 Inclusion-Exclusion
14.10 Combinatorial Proofs
15 Generating Functions
15.1 Infinite Series
15.2 Counting with Generating Functions
15.3 Partial Fractions
15.4 Solving Linear Recurrences
15.5 Formal Power Series
IV Probability
16 Events and Probability Spaces
16.1 Let's Make a Deal
16.2 The Four Step Method
16.3 Strange Dice
16.4 Set Theory and Probability
16.5 Conditional Probability
16.6 Independence
17 Random Variables
17.1 Random Variable Examples
17.2 Independence
17.3 Distribution Functions
17.4 Great Expectations
17.5 Linearity of Expectation
18 Deviation from the Mean
18.1 Why the Mean?
18.2 Markov’s Theorem
18.3 Chebyshev’s Theorem
18.4 Properties of Variance
18.5 Estimation by Random Sampling
18.6 Confidence versus Probability
18.7 Sums of Random Variables
18.8 Really Great Expectations
19 Random Processes
19.1 Gamblers’Ruin
19.2 Random Walks on Graphs
V Recurrences
20 Recurrences
20.1 The Towers of Hanoi
20.2 Merge Sort
20.3 Linear Recurrences
20.4 Divide-and-Conquer Recurrences
20.5 A Feel for Recurrences
Bibliography
Index