Discrete Mathematics for Computing

Cover
Title
Copyright
Contents
List of symbols
Preface
Chapter 1 Introduction to algorithms
1.1 What is an algorithm?
1.2 Control structures
1.3 Further examples of algorithms
Exercises
Chapter 2 Bases and number representation
2.1 Real numbers and the decimal number system
2.2 The binary number system
2.3 Conversion from decimal to binary
2.4 The octal and hexadecimal systems
2.5 Arithmetic in non-decimal bases
Exercises
Chapter 3 Computer representation and arithmetic
3.1 Representing numbers in a computer
3.2 Representing integers
3.3 Arithmetic with integers
3.4 Representing real numbers
3.5 Arithmetic with real numbers
3.6 Binary coded decimal representation
Exercises
Chapter 4 Logic
4.1 Logic and computing
4.2 Propositions
4.3 Connectives and truth tables
4.4 Compound propositions
4.5 Logical equivalence
4.6 Laws of logic
4.7 Predicate logic
4.8 Proof techniques
Exercises
Chapter 5 Sets and relations
5.1 Sets
5.2 Subsets, set operations and Venn diagrams
5.3 Cardinality and Cartesian products
5.4 Computer representation of sets
5.5 Relations
Exercises
Chapter 6 Functions
6.1 Functions and computing
6.2 Composite functions and the inverse of a function
6.3 Functions in programming languages
Exercises
Chapter 7 Induction and recursion
7.1 Recursion and sequences
7.2 Proof by induction
7.3 Induction and recursion
7.4 Solving linear recurrences
7.5 Recursively defined functions and recursive algorithms
7.6 Recursively defined functions in programming languages
Exercises
Chapter 8 Boolean algebra and digital circuits
8.1 Boolean algebra
8.2 Simplifying Boolean expressions
8.3 Digital circuits
8.4 Disjunctive normal form and Karnaugh maps
Exercises
Chapter 9 Combinatorics
9.1 Combinatorics and computing
9.2 The Principle of inclusion and exclusion
9.3 The Multiplication principle
9.4 Permutations
9.5 Combinations
Exercises
Chapter 10 Introduction to graph theory
10.1 What is a graph?
10.2 Basic concepts in graph theory
10.3 The matrix representation of a graph
10.4 Isomorphism of graphs
10.5 Paths and circuits
Exercises
Chapter 11 Trees
11.1 Introduction to trees
11.2 Local area networks and minimal spanning trees
11.3 Minimal distance paths
11.4 Rooted trees
Exercises
Chapter 12 Number theory
12.1 What is number theory?
12.2 Divisibility and prime numbers
12.3 Greatest common divisors and the Euclidean algorithm
12.4 Congruences
12.5 Pseudo-random number generation
12.6 Cryptography
12.7 Proof of the Fundamental theorem of arithmetic
Exercises
Chapter 13 Algorithms and computational complexity
13.1 How long does an algorithm take to run?
13.2 Dominant operations and the first two approximations
13.3 Comparing functions and the third approximation
13.4 The fourth approximation and the O(f) notation
13.5 Sorting algorithms
13.6 Tractable and intractable algorithms
Exercises
Answers to exercises
Index