Programming And Mathematical Thinking

Programming and MathematicalThinkingA Gentle Introduction to Discrete MathFeaturing PythonAllan M. StavelyThe New Mexico Tech PressSocorro, New Mexico, USA

Programming and Mathematical ThinkingA Gentle Introduction to Discrete Math Featuring PythonAllan M. StavelyAllan M. StavelyFirst EditionContent of this book available under the Creative Commons Attribution-Noncommercial-ShareAlike License. 0/ for details.Publisher's Cataloguing-in-Publication DataStavely, Allan MProgramming and mathematical thinking: a gentle introduction to discretemath featuring Python / Allan M. Stavely.xii, 246 p.: ill. ; 28 cmISBN 978-1-938159-00-8 (pbk.) — 978-1-938159-01-5 (ebook)1. Computer science — Mathematics. 2. Mathematics — DiscreteMathematics. 3. Python (Computer program language).QA 76.9 .M35 .S79 004-dc22OCLC Number: 863653804Published by The New Mexico Tech Press, a New Mexico nonprofit corporationThe New Mexico Tech PressSocorro, New Mexico, USA

Once more, to my parents, Earl and Anni

ii

Table of ContentsPreface . vii1. Introduction . 11.1. Programs, data, and mathematical objects . 11.2. A first look at Python . 31.3. A little mathematical terminology . 102. An overview of Python . 172.1. Introduction . 172.2. Values, types, and names . 182.3. Integers . 192.4. Floating-point numbers . 232.5. Strings . 253. Python programs . 293.1. Statements . 293.2. Conditionals . 313.3. Iterations . 354. Python functions . 414.1. Function definitions . 414.2. Recursive functions . 434.3. Functions as values . 454.4. Lambda expressions . 485. Tuples . 515.1. Ordered pairs and n-tuples . 515.2. Tuples in Python . 525.3. Files and databases . 546. Sequences . 576.1. Properties of sequences . 576.2. Monoids . 596.3. Sequences in Python . 646.4. Higher-order sequence functions . 676.5. Comprehensions . 736.6. Parallel processing . 747. Streams . 837.1. Dynamically-generated sequences . 837.2. Generator functions . 85iii

Programming and Mathematical Thinking7.3. Endless streams . 907.4. Concatenation of streams . 927.5. Programming with streams . 957.6. Distributed processing . 1038. Sets . 1078.1. Mathematical sets . 1078.2. Sets in Python . 1108.3. A case study: finding students for jobs . 1148.4. Flat files, sets, and tuples . 1188.5. Other representations of sets . 1239. Mappings . 1279.1. Mathematical mappings . 1279.2. Python dictionaries . 1319.3. A case study: finding given words in a file of text . 1359.4. Dictionary or function? . 1409.5. Multisets . 14510. Relations . 15310.1. Mathematical terminology and notation . 15310.2. Representations in programs . 15610.3. Graphs . 15910.4. Paths and transitive closure . 16410.5. Relational database operations . 16711. Objects . 17511.1. Objects in programs . 17511.2. Defining classes . 17711.3. Inheritance and the hierarchy of classes . 18011.4. Object-oriented programming . 18411.5. A case study: moving averages . 18511.6. Recursively-defined objects: trees . 19411.7. State machines . 2. Larger programs . 21312.1. Sharing tune lists . 21312.2. Biological surveys . 21812.3. Note cards for writers . 227Afterword . 233Solutions to selected exercises . 235Index . 241iv

List of Examples1.1. Finding a name . 41.2. Finding an email address . 71.3. Average of a collection of observations . 86.1. Finding a name again, in functional style . 716.2. Average of observations again, in functional style . 727.1. Combinations using a generator function . 898.1. Finding job candidates using set operations . 1178.2. Job candidates again, with different input files . 1229.1. Finding given words in a document . 1399.2. A memoized function: the nth Fibonacci number . 1449.3. Number of students in each major field . 14910.1. Distances using symmetry and reflexivity . 15911.1. The MovingAverage class . 19111.2. The MovingAverage class, version 2 . 19311.3. The Pushbutton class . 1.4. A state machine for finding fields in a string . 1.5. Code that uses a FieldsStateMachine . 1.6. A state machine for finding fields, version 2 . 209v

vi

PrefaceMy mission in this book is to encourage programmers to think mathematicallyas they develop programs.This idea is nothing new to programmers in science and engineering fields,because much of their work is inherently based on numerical mathematicsand the mathematics of real numbers. However, there is more to mathematicsthan numbers.Some of the mathematics that is most relevant to programming is known as“discrete mathematics”. This is the mathematics of discrete elements, such assymbols, character strings, truth values, and “objects” (to use a programmingterm) that are collections of properties. Discrete mathematics is concernedwith such elements; collections of them, such as sets and sequences; andconnections among elements, in structures such as mappings and relations.In many ways discrete mathematics is more relevant to programming thannumerical mathematics is: not just to particular kinds of programming, butto all programming.Many experienced programmers approach the design of a program bydescribing its input, output, and internal data objects in the vocabulary ofdiscrete mathematics: sets, sequences, mappings, relations, and so on. This isa useful habit for us, as programmers, to cultivate. It can help to clarify ourthinking about design problems; in fact, solutions often become obvious. Andwe inherit a well-understood vocabulary for specifying and documenting ourprograms and for discussing them with other programmers.1For example, consider this simple programming problem. Suppose that weare writing software to analyze web pages, and we want some code that willread two web pages and find all of the URLs that appear in both. Someprogrammers might approach the problem like this:1This paragraph and the example that follows are adapted from a previous book: Allan M. Stavely,Toward Zero-Defect Programming (Reading, Mass.: Addison Wesley Longman, 1999), 142–143.vii

First I'll read the first web page and store all the URLs I find in a list.Then I'll read the second web page and, every time I find a URL, searchthe list for it. But wait: I don't want to include the same URL in myresult more than once. I'll keep a second list of the URLs that I'vealready found in both web pages, and search that before I search thelist of URLs from the first web page.But a programmer who is accustomed to thinking in terms of discretemathematical structures might immediately think of a different approach:The URLs in a web page are a set. I'll read each web page and buildup the set of URLs in each using set insertion. Then I can get the URLscommon to both web pages by using set intersection.Either approach will work, but the second is conceptually simpler, and it willprobably be more straightforward to implement. In fact, once the problem isdescribed in mathematical terms, most of the design work is already done.That's the kind of thinking that this book promotes.As a vehicle, I use the programming language Python. It's a clean, modernlanguage, and it comes with many of the mathematical structures that we willneed: strings, sets, several kinds of sequences, finite mappings (dictionaries,which are more general than arrays), and functions that are first-class values.All these are built into the core of the language, not add-ons implemented bylibraries as in many programming languages. Python is easy to get startedwith and makes a good first language, far better than C or C or Java, inmy opinion. In short, Python is a good language for Getting Things Done witha minimum of fuss. I use it frequently in my own work, and many readers willfind it sufficient for much or all of their own programming.Mathematically, I start at a rather elementary level: the book assumes nomathematical background beyond algebra and logarithms. In a few places Iuse examples from elementary calculus, but a reader who has not studiedcalculus can skip these examples. I don't assume a previous course in discretemathematics; I introduce concepts from discrete mathematics as I go along.Some of these are simple but powerful concepts that (unfortunately) some