Discrete Mathematics for Computing

Description

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