Combinatorial and Algorithmic Mathematics
Description
Detailed review of optimization from first principles, supported by rigorous math and computer science explanations and various learning aids
Supported by rigorous math and computer science foundations, Combinatorial and Algorithmic Mathematics: From Foundation to Optimization provides a from-scratch understanding to the field of optimization, discussing 70 algorithms with roughly 220 illustrative examples, 160 nontrivial end-of-chapter exercises with complete solutions to ensure readers can apply appropriate theories, principles, and concepts when required, and Matlab codes that solve some specific problems. This book helps readers to develop mathematical maturity, including skills such as handling increasingly abstract ideas, recognizing mathematical patterns, and generalizing from specific examples to broad concepts.
Starting from first principles of mathematical logic, set-theoretic structures, and analytic and algebraic structures, this book covers both combinatorics and algorithms in separate sections, then brings the material together in a final section on optimization. This book focuses on topics essential for anyone wanting to develop and apply their understanding of optimization to areas such as data structures, algorithms, artificial intelligence, machine learning, data science, computer systems, networks, and computer security.
Combinatorial and Algorithmic Mathematics includes discussion on:
- Propositional logic and predicate logic, set-theoretic structures such as sets, relations, and functions, and basic analytic and algebraic structures such as sequences, series, subspaces, convex structures, and polyhedra
- Recurrence-solving techniques, counting methods, permutations, combinations, arrangements of objects and sets, and graph basics and properties
- Asymptotic notations, techniques for analyzing algorithms, and computational complexity of various algorithms
- Linear optimization and its geometry and duality, simplex and non-simplex algorithms for linear optimization, second-order cone programming, and semidefinite programming
Combinatorial and Algorithmic Mathematics is an ideal textbook resource on the subject for students studying discrete structures, combinatorics, algorithms, and optimization. It also caters to scientists across diverse disciplines that incorporate algorithms and academics and researchers who wish to better understand some modern optimization methodologies.
More details
Other editions
Additional editions
Person
Baha Alzalg is a Professor in the Department of Mathematics at the University of Jordan in Amman, Jordan. He has also held the post of visiting associate professor in the Department of Computer Science and Engineering at the Ohio State University in Columbus, Ohio. His research interests include topics in optimization theory, applications, and algorithms, with an emphasis on interior-point methods for cone programming.
Content
About the Author xiii
Preface xv
Acknowledgments xvii
About the Companion Website xxi
Part I Foundations 1
1 Mathematical Logic 3
1.1 Propositions 3
1.2 Logical Operators 6
1.3 Propositional Formulas 15
1.4 Logical Normal Forms 24
1.5 The Boolean Satisfiability Problem 29
1.6 Predicates and Quantifiers 30
1.7 Symbolizing Statements of the Form "All P Are Q" 37
2 Set-Theoretic Structures 51
2.1 Induction 51
2.2 Sets 54
2.3 Relations 59
2.4 Partitions 64
2.5 Functions 65
3 Analytic and Algebraic Structures 77
3.1 Sequences 77
3.2 Summations and Series 81
3.3 Matrices, Subspaces, and Bases 87
3.4 Convexity, Polyhedra, and Cones 91
3.5 Farkas' Lemma and Its Variants 95
Part II Combinatorics 103
4 Graphs105
4.1 Basic Graph Definitions 106
4.2 Isomorphism and Properties of Graphs 113
4.3 Eulerian and Hamiltonian Graphs 118
4.4 Graph Coloring 122
4.5 Directed Graphs 125
5 Recurrences 133
5.1 Guess-and-Confirm 133
5.2 Recursion-Iteration 136
5.3 Generating Functions 138
5.4 Recursion-Tree 140
6 Counting149
6.1 Binomial Coefficients and Identities 149
6.2 Fundamental Principles of Counting 154
6.3 The Pigeonhole Principle 161
6.4 Permutations 163
6.5 Combinations 166
Part III Algorithms 179
7 Analysis of Algorithms 181
7.1 Constructing and Comparing Algorithms 182
7.2 Running Time of Algorithms 189
7.3 Asymptotic Notation 199
7.4 Analyzing Decision-Making Statements 211
7.5 Analyzing ProgramsWithout Function Calls 213
7.6 Analyzing Programs with Function Calls 219
7.7 The Complexity Class NP-Complete 224
8 Array and Numeric Algorithms 241
8.1 Array Multiplication Algorithms 241
8.2 Array Searching Algorithms 244
8.3 Array Sorting Algorithms 248
8.4 Euclid's Algorithm 253
8.5 Newton's Method Algorithm 255
9 Elementary Combinatorial Algorithms 267
9.1 Graph Representations 267
9.2 Breadth-First Search Algorithm 270
9.3 Applications of Breadth-First Search 273
9.4 Depth-First Search Algorithm 277
9.5 Applications of Depth-First Search 279
9.6 Topological Sort 283
Part IV Optimization 293
10 Linear Programming 295
10.1 Linear Programming Formulation and Examples 296
10.2 The Graphical Method 302
10.3 Standard Form Linear Programs 309
10.4 Geometry of Linear Programming 311
10.5 The Simplex Method 320
10.6 Duality in Linear Programming 339
10.7 A Homogeneous Interior-Point Method 347
11 Second-Order Cone Programming 363
11.1 The Second-Order Cone and Its Algebraic Structure 363
11.2 Second-Order Cone Programming Formulation 368
11.3 Applications in Engineering and Finance 370
11.4 Duality in Second-Order Cone Programming 375
11.5 A Primal-Dual Path-Following Algorithm 379
11.6 A Homogeneous Self-Dual Algorithm 386
12 Semidefinite Programming and Combinatorial Optimization 395
12.1 The Cone of Positive Semidefinite Matrices 395
12.2 Semidefinite Programming Formulation 399
12.3 Applications in Combinatorial Optimization 401
12.4 Duality in Semidefinite Programming 405
12.5 A Primal-Dual Path-Following Algorithm 408
Exercises 417
Notes and Sources 418
References 418
Appendix A Solutions to Chapter Exercises 421
References 487
Bibliography 489
Index 501
1
Mathematical Logic
CHAPTER CONTENTS
- 1.1 Propositions
- 1.2 Logical Operators
- 1.3 Propositional Formulas
- 1.4 Logical Normal Forms
- 1.5 The Boolean Satisfiability Problem
- 1.6 Predicates and Quantifiers
- 1.7 Symbolizing Statements of the Form "All P Are Q"
The term "logic" has a broad definition, and countless logics have been explored by philosophers, mathematicians, and computer scientists. For most individuals, "logic" typically refers to either propositional logic or predicate logic. Propositional logic, a classical form, involves two truth values (true and false). Predicate logic, on the other hand, expands upon propositional logic by allowing explicit discussion of objects and their properties.
In this chapter, we first study the propositional logic which is the simplest, and most abstract logic we can study. After that, we study the predicate logic. We start by introducing the notion of a proposition.
Throughout this chapter (and the entire book), denotes the set of all natural numbers, denotes the set of all integers, and denotes the set of all rational numbers. For example, 2 and are rational numbers, but and are irrational numbers. We also let denote the set of all real (rational and irrational) numbers.
1.1 Propositions
In this section, we define a proposition and introduce two different types of propositions with examples. To begin with, we have the following definition.
Definition 1.1 A proposition is a statement that can be either true or false.
It is essential to emphasize that the proposition must hold either a true or false value, and it cannot simultaneously possess both. We give the following example.
Identify each of the following statements as a proposition or not and provide any required clarifications.
- .
- .
- Hillary Clinton is a former president of the United States.
- Bill Clinton is a former president of the United States.
- Be careful.
- Is Abraham Lincoln the greatest president that the United States has ever had?
- .
Solution
- "" is a proposition (a true proposition).
- "" is a proposition (a false proposition).
- "Hillary Clinton is a former president of the United States" is a proposition (a false proposition).
- "Bill Clinton is a former president of the United States" is a proposition (a true proposition).
- "Be careful" is not a proposition.
- "Is Abraham Lincoln the greatest president that the United States has ever had?" is not a proposition.
- "" is not a proposition. In fact, the values of the variables have not been assigned. So, we do not know the values of and , and hence it is neither true or false.
▄
Sometimes a sentence does not provide enough information to determine whether it is true or false, so it is not a proposition. An example is, "Your answer to Question 13 is incorrect." The sentence does not tell us who we are talking about. If we identify the person, say "Adam's answer to Question 13 is incorrect," then the sentence becomes a proposition.
Note that, for a given statement, being not able to decide whether it is true or false (due to the lack of information) is different from being not able to know how to verify whether it is true or false. Consider Goldbach's conjecture1: "Every even integer greater than 2 can be written as the sum of two primes."2 Despite its origin dating back to 1742 and computational data suggesting its validity, this conjecture remains an open problem in number theory. It is impossible for this sentence to be true sometimes, and false at other times. As of now, no one has proved or disproved this claim, classifying it as a proposition with an undetermined truth value because it cannot simultaneously be both true and false, and its resolution may await future mathematical breakthroughs.
There are some sentences that cannot be determined to be either true or false. For example, the sentence: "This statement is false." This is not a proposition because we cannot decide whether it is true or false. In fact, if the sentence: "This statement is false" is true, then by its meaning it is false. On the other hand, if the sentence: "This statement is false" is false, then by its meaning it is true. Therefore, the sentence: "This statement is false" can have neither true nor false for its truth value. This type of sentence is referred to as paradoxes.3 The study of a paradox has played a fundamental role in the development of modern mathematical logic.
Note that the sentence "This statement is false," which is self-contradicting, is different from the sentence "This statement is true," which is self-consistent on either choice. Nevertheless, neither is a proposition. The latter type of sentence is referred to as an anti-paradox.4 The question that arises now is: Why the sentence "This statement is true" is not a proposition? This question is left as an exercise for the reader.
We now define atomic (or primitive) propositions. Intuitively, these are the set of smallest propositions.
Definition 1.2 An atomic proposition is one whose truth or falsity does not depend on the truth or falsity of any other proposition.
According to Definition 1.2, we find that all the propositions in items - of Example 1.1 are atomic.
Definition 1.3 A compound proposition is a proposition that involves the assembly of multiple atomic propositions.
The following connectives allow us to build up compound propositions:
Example 1.2 The following proposition is compound.
Note that
- compound proposition 1 = (atomic proposition 1) (atomic proposition 2),
- compound proposition 2 = (compound proposition 1) (atomic proposition 3).
▄
In the realm of natural language, such as English, ambiguity is a recurring challenge that writers and readers encounter. The following remark says that slight variations in context could drastically alter the intended message.
Remark 1.1 Sentences in natural languages can often be ambiguous and words can have different meanings in the context in which they are used.
To illustrate Remark 1.1, we consider the following sentences:
- The sentence "You can download WhatsApp or Skype to ring friends" could mean that you can only download one of the applications or it could mean that you can download just one or download both.
- The sentence "I smelled a chlorine-like odor and felt ill" implies that the odor of chlorine made you sick, but the sentence "I am majoring in CS and minoring in Math" does not imply that majoring in CS caused you to minor in Math.
- The sentence "I went to Chicago and took a plane" could mean that you took a plane to travel to Chicago or it could mean that you went to Chicago and then took a plane from Chicago to another destination, such as Las Vegas.
In mathematics and computer science, it is important to avoid ambiguity and for sentences to have a precise meaning. This is why people have invented artificial languages such as Java.
1.1.1 Notations
Rather than writing out propositions in full, we will abbreviate them by using propositional variables: , etc.
Example 1.3 (Example 1.2 revisited)
In Example 1.2, let be the proposition "It is raining," be the proposition "You are outside," and be the proposition "You get wet." Then we can abbreviate the compound proposition
▄
In Section 1.2, we will learn more about the connectives AND, OR, NOT, IF-THEN, and IFF. This will enable us to gain a comprehensive understanding of how these connectives function within the context of formal logic and the role they play in constructing logical statements and arguments.
1.2 Logical Operators
In this section, we study the following logical operators or connectives: Negation, conjunction, disjunction, exclusive disjunction, implication, and double implication.
Before starting with the logical operators, we introduce the truth tables which help us understand how such operators work by calculating all of the possible return values of atomic propositions.
Definition 1.4 A truth table is a mathematical table used to show the truth or falsity of a compound proposition depending on the truth or falsity of the atomic propositions from which it is constructed.
Examples of truth tables will be seen very frequently throughout this chapter.
1.2.1 Negation, Conjunction, and Disjunction
This part is devoted to introducing the logical operators:...
