Discrete Mathematics for Computing
Publisher: Palgrave Macmillan
Published: March 15, 1995
Format: Paperback
Number of pages: 304
ISBN-13: 9780333646946
Subjects: Applied mathematics; Mathematical & statistical software; Mathematical theory of computation
Table of contents: title: List of symbols
pagenum: viii; title: Preface
pagenum: xi; label: 1
title: Introduction to Algorithms; label: 1.1
title: What is an algorithm?
pagenum: 1; label: 1.2
title: Control structures
pagenum: 3; label: 1.3
title: Further examples of algorithms
pagenum: 7; title: Exercises
pagenum: 11; label: 2
title: Bases and Number Representation; label: 2.1
title: Real numbers and the decimal number system
pagenum: 14; label: 2.2
title: The binary number system
pagenum: 15; label: 2.3
title: Conversion from decimal to binary
pagenum: 17; label: 2.4
title: The octal and hexadecimal systems
pagenum: 21; label: 2.5
title: Arithmetic in non-decimal bases
pagenum: 24; title: Exercises
pagenum: 26; label: 3
title: Computer Representation and Arithmetic; label: 3.1
title: Representing numbers in a computer
pagenum: 28; label: 3.2
title: Representing integers
pagenum: 28; label: 3.3
title: Arithmetic with integers
pagenum: 31; label: 3.4
title: Representing real numbers
pagenum: 34; label: 3.5
title: Arithmetic with real numbers
pagenum: 38; label: 3.6
title: Binary coded decimal representation
pagenum: 40; title: Exercises
pagenum: 41; label: 4
title: Logic; label: 4.1
title: Logic and computing
pagenum: 44; label: 4.2
title: Propositions
pagenum: 44; label: 4.3
title: Connectives and truth tables
pagenum: 46; label: 4.4
title: Compound propositions
pagenum: 49; label: 4.5
title: Logical equivalence
pagenum: 52; label: 4.6
title: Laws of logic
pagenum: 54; label: 4.7
title: Predicate logic
pagenum: 59; title: Exercises
pagenum: 65; label: 5
title: Sets and Relations; label: 5.1
title: Sets
pagenum: 69; label: 5.2
title: Subsets, set operations and Venn diagrams
pagenum: 71; label: 5.3
title: Cardinality and Cartesian products
pagenum: 77; label: 5.4
title: Computer representation of sets
pagenum: 80; label: 5.5
title: Relations
pagenum: 82; title: Exercises
pagenum: 89; label: 6
title: Functions; label: 6.1
title: Functions and computing
pagenum: 92; label: 6.2
title: Composite functions and the inverse of a function
pagenum: 98; label: 6.3
title: Functions in programming languages
pagenum: 104; title: Exercises
pagenum: 106; label: 7
title: Induction and Recursion; label: 7.1
title: Recursion and sequences
pagenum: 109; label: 7.2
title: Proof by induction
pagenum: 115; label: 7.3
title: Induction and recursion
pagenum: 119; label: 7.4
title: Recursively defined functions and recursive algorithms
pagenum: 121; label: 7.5
title: Recursively defined functions in programming languages
pagenum: 126; title: Exercises
pagenum: 128; label: 8
title: Boolean Algebra and Digital Circuits; label: 8.1
title: Boolean algebra
pagenum: 133; label: 8.2
title: Simplifying Boolean expressions
pagenum: 138; label: 8.3
title: Digital circuits
pagenum: 140; label: 8.4
title: Disjunctive normal form and Karnaugh maps
pagenum: 146; title: Exercises
pagenum: 153; label: 9
title: Combinatorics; label: 9.1
title: Combinatorics and computing
pagenum: 158; label: 9.2
title: The Multiplication principle
pagenum: 158; label: 9.3
title: Permutations
pagenum: 161; label: 9.4
title: Combinations
pagenum: 163; title: Exercises
pagenum: 167; label: 10
title: Introduction to Graph Theory; label: 10.1
title: What is a graph?
pagenum: 170; label: 10.2
title: Basic concepts in graph theory
pagenum: 170; label: 10.3
title: The matrix representation of a graph
pagenum: 177; label: 10.4
title: Isomorphism of graphs
pagenum: 179; label: 10.5
title: Paths and circuits
pagenum: 182; title: Exercises
pagenum: 192; label: 11
title: Trees; label: 11.1
title: Introduction to trees
pagenum: 197; label: 11.2
title: Local area networks and minimal spanning trees
pagenum: 199; label: 11.3
title: Minimal distance paths
pagenum: 205; label: 11.4
title: Rooted trees
pagenum: 207; title: Exercises
pagenum: 212; label: 12
title: Number Theory; label: 12.1
title: What is number theory?
pagenum: 215; label: 12.2
title: Divisibility and prime numbers
pagenum: 215; label: 12.3
title: Greatest common divisors and the Euclidean algorithm
pagenum: 218; label: 12.4
title: Congruences
pagenum: 223; label: 12.5
title: Pseudo-random number generation
pagenum: 230; label: 12.6
title: Proof of the Fundamental theorem of arithmetic
pagenum: 234; title: Exercises
pagenum: 234; label: 13
title: Algorithms and Computational Complexity; label: 13.1
title: How long does an algorithm take to run?
pagenum: 237; label: 13.2
title: Dominant operations and the first two approximations
pagenum: 238; label: 13.3
title: Comparing functions and the third approximation
pagenum: 240; label: 13.4
title: The fourth approximation and the O(f) notation
pagenum: 246; label: 13.5
title: Sorting algorithms
pagenum: 249; label: 13.6
title: Tractable and intractable algorithms
pagenum: 254; title: Exercises
pagenum: 258; title: Answers to exercises
pagenum: 260; title: Index
pagenum: 284