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.

2 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 .. vii 1. Introduction .. 1. Programs, data, and Mathematical objects .. 1. A first look at python .. 3. A little Mathematical terminology.

3 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.

4 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 .. 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.

5 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.

6 218. Note cards for writers .. 227. Afterword .. 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.

7 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. 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.

8 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 .

9 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. 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.

10 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.