Discrete Mathematics for Computer Science: An Example-Based Introduction

by Jon Pierre Fortney

Overview

Discrete Mathematics for Computer Science: An Example-Based Introduction is intended for a first- or second-year discrete mathematics course for computer science majors. It covers many important mathematical topics essential for future computer science majors, such as algorithms, number representations, logic, set theory, Boolean algebra, functions, combinatorics, algorithmic complexity, graphs, and trees.

Features

• Designed to be especially useful for courses at the community-college level
• Ideal as a first- or second-year textbook for computer science majors, or as a general introduction to discrete mathematics
• Written to be accessible to those with a limited mathematics background, and to aid with the transition to abstract thinking
• Filled with over 200 worked examples, boxed for easy reference, and over 200 practice problems with answers
• Contains approximately 40 simple algorithms to aid students in becoming proficient with algorithm control structures and pseudocode
• Includes an appendix on basic circuit design which provides a real-world motivational example for computer science majors by drawing on multiple topics covered in the book to design a circuit that adds two eight-digit binary numbers

Jon Pierre Fortney graduated from the University of Pennsylvania in 1996 with a BA in Mathematics and Actuarial Science and a BSE in Chemical Engineering. Prior to returning to graduate school, he worked as both an environmental engineer and as an actuarial analyst. He graduated from Arizona State University in 2008 with a PhD in Mathematics, specializing in Geometric Mechanics. Since 2012, he has worked at Zayed University in Dubai. This is his second mathematics textbook.

Product Details

ISBN-13:	9780367549893
Publisher:	CRC Press
Publication date:	12/24/2020
Pages:	270
Product dimensions:	7.00(w) x 10.00(h) x (d)

About the Author

Jon Pierre Fortney graduated from the University of Pennsylvania in 1996 with a B.A. in Mathematics and Actuarial Science and a B.S.E. in Chemical Engineering. Prior to returning to graduate school he worked as both an environmental engineer and as an actuarial analyst. He graduated from Arizona State University in 2008 with a Ph.D. in Mathematics, specializing in Geometric Mechanics. Since 2012 he has worked at Zayed University in Dubai. This is his second mathematics textbook.

Table of Contents

Preface xi

Chapter 1 Introduction to Algorithms 1

1.1 What are Algorithms? 1

1.2 Control Structures 2

1.3 Tracing an Algorithm 5

1.4 Algorithm Examples 7

1.5 Problems 13

Chapter 2 Number Representations 19

2.1 Whole Numbers 19

2.2 Fractional Numbers 22

2.3 The Relationship between Binary, Octal, and Hexadecimal Numbers 25

2.4 Converting From Decimal Numbers 30

2.5 Problems 38

Chapter 3 Logic 43

3.1 Propositions and Connectives 43

3.2 Connective Truth Tables 46

3.3 Truth Value of Compound Statements 51

3.4 Tautologies and Contradictions 55

3.5 Logical Equivalence and the Laws of Logic 56

3.6 Problems 59

Chapter 4 Set Theory 61

4.1 Set Notation 61

4.2 Set Operations 64

4.3 Venn Diagrams 71

4.4 The Laws of Set Theory 74

4.5 Binary Relations on Sets 76

4.6 Problems 82

Chapter 5 Boolean Algebra 89

5.1 Definition of Boolean Algebra 89

5.2 Logic and Set Theory as Boolean Algebras 92

5.3 Digital Circuits 96

5.4 Sums-Of-Products and Products-of-Sums 102

5.5 Problems 105

Chapter 6 Functions 111

6.1 Introduction to Functions 111

6.2 Real-Valued Functions 118

6.3 Function Composition and Inverses 122

6.4 Problems 127

Chapter 7 Counting and Combinatorics 133

7.1 Addition and Multiplication Principles 133

7.2 Counting Algorithm Loops 136

7.3 Permutations and Arrangements 138

7.4 Combinations and Subsets 141

7.5 Permutation and Combination Examples 143

7.6 Problems 145

Chapter 8 Algorithmic Complexity 149

8.1 Overview of Algorithmic Complexity 149

8.2 Time-Complexity Functions 150

8.3 Finding Time-Complexity Functions 153

8.4 Big-O Notation 156

8.5 Ranking Algorithms 163

8.6 Problems 165

Chapter 9 Graph Theory 167

9.1 Basic Definitions 167

9.2 Eulerian and Semi-Eulerian Graphs 174

9.3 Matrix Representations of Graphs 181

9.4 Reachability for Directed Graphs 185

9.5 Problems 190

Chapter 10 Trees 195

10.1 Basic Definitions 195

10.2 Minimal Spanning Trees of Weighted Graphs 200

10.3 Minimal Distance Paths 202

10.4 Problems 206

Appendix A Basic Circuit Design 209

A.1 Binary Addition 209

A.2 The Half-Adder 210

A.3 The Full-Adder 212

A.4 Adding Two Eight-Digit Binary Numbers 214

Appendix B Answers To Problems 217

B.1 Chapter One Answers 217

B.2 Chapter Two Answers 224

B.3 Chapter Three Answers 227

B.4 Chapter Four Answers 230

B.5 Chapter Five Answers 235

B.6 Chapter Six Answers 238

B.7 Chapter Seven Answers 245

B.8 Chapter Eight Answers 246

B.9 Chapter Nine Answers 247

B.10 Chapter Ten Answers 251

Index 255