A Programmer's Introduction to Mathematics Second Edition

A Programmer's Introduction to Mathematics uses your familiarity with ideas from programming and software to teach mathematics. You'll learn about the central objects and theorems of mathematics, covering graphs, calculus, linear algebra, eigenvalues, optimization, and more. You'll also be immersed in the often unspoken cultural attitudes of mathematics, learning both how to read and write proofs while understanding why mathematics is the way it is. Between each technical chapter is an essay describing a different aspect of mathematical culture, and discussions of the insights and meta-insights that constitute mathematical intuition.

As you learn, we'll use new mathematical ideas to create wondrous programs, from cryptographic schemes to neural networks to hyperbolic tessellations. Each chapter also contains a set of exercises that have you actively explore mathematical topics on your own. By the end of the book, you will be able to learn mathematics on your own. In short, this book will teach you to engage with mathematics.

This is the ebook edition, a full-color pdf containing the complete contents of the book (the physical book is black and white). Due to the heavy use of mathematical typesetting, there is no plan for a ebook-reader-specific format (mobi, epub). This ebook is a simple pdf download.

Contents:
Our Goal i
Chapter 1. Like Programming, Mathematics has a Culture 1
Chapter 2. Polynomials 5
2.1 Polynomials, Java, and Definitions . . . . . . . . . . . . . . . . . . . . . . 5
2.2 A Little More Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Existence & Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Realizing it in Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Application: Sharing Secrets . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Chapter 3. On Pace and Patience 35
Chapter 4. Sets 39
4.1 Sets, Functions, and Their -Jections . . . . . . . . . . . . . . . . . . . . . 40
4.2 Clever Bijections and Counting . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Proof by Induction and Contradiction . . . . . . . . . . . . . . . . . . . . 51
4.4 Application: Stable Marriages . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.7 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Chapter 5. Variable Names, Overloading, and Your Brain 63
Chapter 6. Graphs 69
6.1 The Definition of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.3 Register Allocation and Hardness . . . . . . . . . . . . . . . . . . . . . . 73
6.4 Planarity and the Euler Characteristic . . . . . . . . . . . . . . . . . . . . 75
6.5 Application: the Five Color Theorem . . . . . . . . . . . . . . . . . . . . 78Sold to
6.6 Approximate Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.7 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.9 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Chapter 7. The Many Subcultures of Mathematics 89
Chapter 8. Calculus with One Variable 95
8.1 Lines and Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.2 Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.3 The Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.4 Taylor Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8.5 Remainders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.6 Application: Finding Roots . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.7 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Chapter 9. On Types and Tail Calls 129
Chapter 10. Linear Algebra 135
10.1 Linear Maps and Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . 136
10.2 Linear Maps, Formally This Time . . . . . . . . . . . . . . . . . . . . . . 141
10.3 The Basis and Linear Combinations . . . . . . . . . . . . . . . . . . . . . 143
10.4 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10.5 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.6 Conjugations and Computations . . . . . . . . . . . . . . . . . . . . . . . 155
10.7 One Vector Space to Rule Them All . . . . . . . . . . . . . . . . . . . . . 158
10.8 Geometry of Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 159
10.9 Application: Singular Value Decomposition . . . . . . . . . . . . . . . . . 164
10.10 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.12 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Chapter 11. Live and Learn Linear Algebra (Again) 185
Chapter 12. Eigenvectors and Eigenvalues 191
12.1 Eigenvalues of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
12.2 Limiting the Scope: Symmetric Matrices . . . . . . . . . . . . . . . . . . 195
12.3 Inner Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
12.4 Orthonormal Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
12.5 Computing Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
12.6 The Spectral Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.7 Application: Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.8 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225Sold to
12.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
12.10 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Chapter 13. Rigor and Formality 233
Chapter 14. Multivariable Calculus and Optimization 239
14.1 Generalizing the Derivative . . . . . . . . . . . . . . . . . . . . . . . . . . 239
14.2 Linear Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
14.3 Vector-valued Functions and the Chain Rule . . . . . . . . . . . . . . . . 246
14.4 Computing the Total Derivative . . . . . . . . . . . . . . . . . . . . . . . 248
14.5 The Geometry of the Gradient . . . . . . . . . . . . . . . . . . . . . . . . 251
14.6 Optimizing Multivariable Functions . . . . . . . . . . . . . . . . . . . . . 253
14.7 Gradient Descent: an Optimization Hammer . . . . . . . . . . . . . . . . 261
14.8 Gradients of Computation Graphs . . . . . . . . . . . . . . . . . . . . . . 262
14.9 Application: Automatic Differentiation and a Simple Neural Network . . 265
14.10 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
14.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
14.12 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Chapter 15. The Argument for Big-O Notation 291
Chapter 16. Groups 301
16.1 The Geometric Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . 303
16.2 The Interface Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
16.3 Homomorphisms: Structure Preserving Functions . . . . . . . . . . . . . 309
16.4 Building Blocks of Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 312
16.5 Geometry as the Study of Groups . . . . . . . . . . . . . . . . . . . . . . 314
16.6 The Symmetry Group of the Poincaré Disk . . . . . . . . . . . . . . . . . 324
16.7 Application: Drawing Hyperbolic Tessellations . . . . . . . . . . . . . . . 329
16.8 Cultural Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
16.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
16.10 Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
Chapter 17. A New Interface 353
Appendix A. Notation 363
Appendix B. A Summary of Proofs 365
B.1 Propositional and first-order logic . . . . . . . . . . . . . . . . . . . . . . 365
B.2 Methods of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
B.3 How does one actually prove things? . . . . . . . . . . . . . . . . . . . . 368
Appendix C. Annotated Resources 373
C.1 Fundamentals and Foundations . . . . . . . . . . . . . . . . . . . . . . . 373Sold to
C.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
C.3 Graph Theory and Combinatorics . . . . . . . . . . . . . . . . . . . . . . 375
C.4 Calculus and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
C.5 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
C.6 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
C.7 Abstract Algebra (Groups, etc.) . . . . . . . . . . . . . . . . . . . . . . . . 377
C.8 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
C.9 Computer Science, Theory, and Algorithms . . . . . . . . . . . . . . . . . 378
C.10 Fun and Recreation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
About the Author and Cover 381
Index 383