Programming and Mathematical Thinking

1 Programming and Mathematical Thinking A Gentle Introduction to Discrete math Featuring Python Allan M. Stavely The New Mexico Tech Press Socorro, New Mexico, USA. Programming and Mathematical Thinking A Gentle Introduction to Discrete math Featuring Python Allan M. Stavely Copyright 2014 Allan M. Stavely First Edition Content of this book available under the Creative Commons Attribution-Noncommercial-ShareAlike License. See for details. Publisher's Cataloguing-in-Publication Data Stavely, Allan M. Programming and Mathematical Thinking : a gentle introduction to discrete math featuring Python / Allan M. Stavely. xii, 246 p.: ill. ; 28 cm ISBN 978-1-938159-00-8 (pbk.) 978-1-938159-01-5 (ebook). 1. Computer science Mathematics. 2. Mathematics Discrete Mathematics. 3. Python (Computer program language). QA .M35 .S79 2014. 004-dc22. OCLC Number: 863653804. Published by The New Mexico Tech Press, a New Mexico nonprofit corporation The New Mexico Tech Press Socorro, New Mexico, USA. Once more, to my parents, Earl and Ann i ii Table of Contents Preface.

2 Vii 1. Introduction .. 1. Programs, data, and Mathematical objects .. 1. A first look at Python .. 3. A little Mathematical terminology .. 10. 2. An overview of Python .. 17. Introduction .. 17. Values, types, and names .. 18. Integers .. 19. Floating-point numbers .. 23. Strings .. 25. 3. Python programs .. 29. Statements .. 29. Conditionals .. 31. Iterations .. 35. 4. Python functions .. 41. Function definitions .. 41. Recursive functions .. 43. Functions as values .. 45. Lambda expressions .. 48. 5. Tuples .. 51. Ordered pairs and n-tuples .. 51. Tuples in Python .. 52. Files and databases .. 54. 6. Sequences .. 57. Properties of sequences .. 57. Monoids .. 59. Sequences in Python .. 64. Higher-order sequence functions .. 67. Comprehensions .. 73. Parallel processing .. 74. 7. Streams .. 83. Dynamically-generated sequences .. 83. Generator functions .. 85. iii Programming and Mathematical Thinking Endless streams .. 90. Concatenation of streams .. 92. Programming with streams.

3 95. Distributed processing .. 103. 8. Sets .. 107. Mathematical sets .. 107. Sets in Python .. 110. A case study: finding students for jobs .. 114. Flat files, sets, and tuples .. 118. Other representations of sets .. 123. 9. Mappings .. 127. Mathematical mappings .. 127. Python dictionaries .. 131. A case study: finding given words in a file of text .. 135. Dictionary or function? .. 140. Multisets .. 145. 10. Relations .. 153. Mathematical terminology and notation .. 153. Representations in programs .. 156. Graphs .. 159. Paths and transitive closure .. 164. Relational database operations .. 167. 11. Objects .. 175. Objects in programs .. 175. Defining classes .. 177. Inheritance and the hierarchy of classes .. 180. Object-oriented Programming .. 184. A case study: moving averages .. 185. Recursively-defined objects: trees .. 194. State machines .. 201. 12. Larger programs .. 213. Sharing tune lists .. 213. Biological surveys .. 218. Note cards for writers .. 227. Afterword.

4 233. Solutions to selected exercises .. 235. Index .. 241. iv List of Examples Finding a name .. 4. Finding an email address .. 7. Average of a collection of observations .. 8. Finding a name again, in functional style .. 71. Average of observations again, in functional style .. 72. Combinations using a generator function .. 89. Finding job candidates using set operations .. 117. Job candidates again, with different input files .. 122. Finding given words in a document .. 139. A memoized function: the nth Fibonacci number .. 144. Number of students in each major field .. 149. Distances using symmetry and reflexivity .. 159. The MovingAverage class .. 191. The MovingAverage class, version 2 .. 193. The Pushbutton class .. 204. A state machine for finding fields in a string .. 206. Code that uses a FieldsStateMachine .. 207. A state machine for finding fields, version 2 .. 209. v vi Preface My mission in this book is to encourage programmers to think mathematically as they develop programs.

5 This idea is nothing new to programmers in science and engineering fields, because much of their work is inherently based on numerical mathematics and the mathematics of real numbers. However, there is more to mathematics than numbers. Some of the mathematics that is most relevant to Programming is known as discrete mathematics . This is the mathematics of discrete elements, such as symbols, character strings, truth values, and objects (to use a Programming term) that are collections of properties. Discrete mathematics is concerned with such elements; collections of them, such as sets and sequences; and connections among elements, in structures such as mappings and relations. In many ways discrete mathematics is more relevant to Programming than numerical mathematics is: not just to particular kinds of Programming , but to all Programming . Many experienced programmers approach the design of a program by describing its input, output, and internal data objects in the vocabulary of discrete mathematics: sets, sequences, mappings, relations, and so on.

6 This is a useful habit for us, as programmers, to cultivate. It can help to clarify our Thinking about design problems; in fact, solutions often become obvious. And we inherit a well-understood vocabulary for specifying and documenting our programs and for discussing them with other For example, consider this simple Programming problem. Suppose that we are writing software to analyze web pages, and we want some code that will read two web pages and find all of the URLs that appear in both. Some programmers might approach the problem like this: 1. This 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, search the list for it. But wait: I don't want to include the same URL in my result more than once. I'll keep a second list of the URLs that I've already found in both web pages, and search that before I search the list of URLs from the first web page.

7 But a programmer who is accustomed to Thinking in terms of discrete- Mathematical structures might immediately think of a different approach: The URLs in a web page are a set. I'll read each web page and build up the set of URLs in each using set insertion. Then I can get the URLs common to both web pages by using set intersection. Either approach will work, but the second is conceptually simpler, and it will probably be more straightforward to implement. In fact, once the problem is described 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, modern language, and it comes with many of the Mathematical structures that we will need: 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 by libraries as in many Programming languages.

8 Python is easy to get started with and makes a good first language, far better than C or C++ or Java, in my opinion. In short, Python is a good language for Getting Things Done with a minimum of fuss. I use it frequently in my own work, and many readers will find it sufficient for much or all of their own Programming . Mathematically, I start at a rather elementary level: the book assumes no Mathematical background beyond algebra and logarithms. In a few places I. use examples from elementary calculus, but a reader who has not studied calculus can skip these examples. I don't assume a previous course in discrete mathematics; I introduce concepts from discrete mathematics as I go along. Some of these are simple but powerful concepts that (unfortunately) some viii programmers never learn, and we'll see how to use them to create simple and elegant solutions to Programming problems. For example, one recurring theme in the book is the concept of a monoid. It turns out that monoids (more than, for example, groups and semigroups) are ubiquitous in the data types and data structures that programmers use most often.

9 I emphasize the extent to which all monoids behave alike and how concepts and algorithms can be transferred from one to another. I recommend this book for use in a first university-level course, or even an advanced high-school course, for mathematically-oriented students who have had some exposure to computers and Programming . For students with no such exposure, the book could be supplemented by an introductory Programming textbook, using either Python or another Programming language, or by additional lecture material or tutorials presenting techniques of Programming . Or the book could be used in a second course that is preceded by an introductory Programming course of the usual kind. Otherwise, the ideal reader is someone who has had at least some experience with Programming , using either Python or another Programming language. In fact, I hope that some of my readers will be quite experienced programmers who may never have been through a modern, mathematically-oriented program of study in computer science.

10 If you are such a person, you'll see many ideas that will probably be new to you and that will probably improve your Programming . At the end of most chapters is a set of exercises. Instructors can use these exercises in laboratory sessions or as homework exercises, and some can be used as starting points for class discussions. Many instructors will want to supplement these exercises with their own extended Programming assignments. In a number of places I introduce a topic and then say something like . details are beyond the scope of this book. The book could easily expand to encompass most of the computer science curriculum, and I had to draw the line somewhere. I hope that many readers, especially students, will pursue some of these topics further, perhaps with the aid of their instructors or in later Programming and computer science classes. Some of the topics are ix exception handling, parallel computing, distributed computing, various advanced data structures and algorithms, object-oriented Programming , and state machines.