The Practice of Computing using Python

ContentsI Thinking About Computing 0 The Study of Computer Science0.1 Why Computer Science?0.1.1 Importance of Computer Science0.1.2 Computer “Science”0.1.3 Computer Science Through Computer Programming0.2 The Difficulty and Promise of Programming0.2.1 Difficulty 1: two things at once0.2.2 Difficulty 2: What is a good program?0.2.3 The Promise of a Computer Program0.3 Choosing a Computer Language0.3.1 Different Computer Languages0.3.2 Why Python?0.3.3 Is Python the Best Language?0.4 What is Computation?0.5 What is a computer?0.5.1 Computation in Nature0.5.2 The Human Computer0.6 The Modern, Electronic Computer0.6.1 It’s the Switch!0.6.2 The Transistor0.7 A High Level look at a Modern Computer0.8 Representing Data0.8.1 Binary Data0.8.2 Working with Binary0.8.3 Limits0.8.4 Representing Letters0.8.5 Representing other Data0.8.6 What does a number represent?0.8.7 How to talk about quantities of data0.8.8 How much data is that?0.9 Overview of Coming Chapters0.10 SummaryII Starting to Program1 Beginnings 1.1 Practice, Practice, Practice1.2 QUICKSTART 1, the Circumference Program1.2.1 Examining the code1.3 An Interactive Session1.4 Parts of a Program1.4.1 Modules1.4.2 Statements and Expressions1.4.3 Whitespace1.4.4 Comments1.4.5 Special Python Elements: Tokens1.4.6 Naming Objects1.5 Variables1.5.1 Variable Creation and Assignment1.6 Objects and Types1.6.1 Numbers1.6.2 Other Built-in Types1.6.3 Object, not variable, types1.6.4 Constructing new values1.7 Operators1.7.1 Integer Operators1.7.2 Floating Point Operators1.7.3 Mixed Operations1.7.4 Order of Operations and Parenthesis1.7.5 Augmented Assignment Operators: a shortcut!1.8 Our first module, math1.9 Developing an Algorithm1.10 Conclusion1.11 Visual Vignette: Turtle Graphic1.12 Exercises1.12.1 Programming Projects2 Control 2.1 The selection statement for decisions: if2.1.1 Booleans for decisions2.1.2 The if statement2.1.3 Example: what lead is safe in basketball?2.1.4 Repetition2.1.5 Example: Finding Perfect Numbers2.2 In-depth Control2.2.1 True and False: Booleans2.2.2 Boolean Variables2.2.3 Relational Operators2.2.4 Boolean Operators2.2.5 Precedence2.2.6 Boolean Operators Example2.2.7 Another Word on Assignments2.2.8 The Selection statement for decisions2.2.9 More on Python decision statements2.2.10 Repetition: the while statement2.2.11 Sentinel Loop2.2.12 Summary of repetition2.2.13 More on the for statement2.2.14 Nesting2.2.15 Hailstone Sequence example2.2.16 Summary2.3 Visual Vignette: Plotting Data with pylab2.4 Computer Science Perspectives: Minimal Universal Computing2.4.1 Minimal Universal Computing2.5 Exercises2.5.1 Programming Projects3 Algorithms and Program Development3.1 What is an algorithm?3.1.1 Example Algorithms3.2 Algorithm Features3.2.1 Algorithm versus program3.2.2 Detailed3.2.3 Effective3.2.4 Specify Behavior3.2.5 General Purpose3.2.6 Can we really do all that?3.3 What is a program?3.3.1 Readable3.3.2 Robust3.3.3 Correct3.4 Strategies for program design3.4.1 Engage and Commit3.4.2 Understand, then visualize3.4.3 Think before you Program3.4.4 Try it: Experiment3.4.5 Simplify3.4.6 Stop and Think3.4.7 Relax, give it a break3.5 A simple example3.5.1 Build the skeleton3.5.2 Output3.5.3 Input3.5.4 Doing the calculation3.6 Summary3.7 ExercisesIII Organizing: Data Structures and Functions 4 Working with Strings 4.1 The String type4.1.1 The triple quote string4.1.2 Non-printing characters4.1.3 String representation4.1.4 Strings as a sequence4.1.5 More Indexing and Slicing4.2 String operations4.2.1 Concatenation (+) and Repetition (*)4.2.2 When is + addition and when is it concatenation?4.2.3 Comparison operators4.2.4 The in operator4.2.5 String collection is immutable4.3 A preview of functions and methods4.3.1 What is a function? First cut4.3.2 A String Method4.3.3 Determining method names and method arguments4.3.4 String Methods4.3.5 String functions4.4 Formatted Output for Strings4.4.1 Descriptor codes4.4.2 Width Descriptor4.4.3 Floating-point Precision Descriptor4.5 Control and Strings4.6 Working with strings4.6.1 Example, reordering a person’s name4.6.2 Palindromes4.7 Example: Counting Poker Hands4.7.1 Program to Count Poker Hands4.8 Summary4.9 Exercises4.9.1 Programming Projects5 Functions–QuickStart5.1 What is a function?5.1.1 Why have functions?5.2 Python Functions5.3 Flow of control with Functions5.3.1 Function Flow in Detail5.3.2 Another Function Example5.3.3 Function Example: Word Puzzle5.3.4 Functions calling Functions5.3.5 When to use a Function5.3.6 What if there is no return statement?5.3.7 What if there are multiple return statements?5.4 Conclusion5.5 Visual Vignette: Turtle Flag5.6 Exercises5.6.1 Programming Projects6 Lists and Tuples6.1 What is a list?6.2 What we already know how to do with lists (mostly)6.2.1 Indexing and Slicing6.2.2 Operators6.2.3 Functions6.2.4 List iteration6.3 New things in Lists6.3.1 Lists are Mutable6.3.2 List Methods6.4 Some old and new friends: range, split and other functions and methods6.4.1 range, split and multiple assignment6.4.2 List to string and back again, using join6.4.3 The sorted function6.5 Working with some Examples6.5.1 Anagrams6.5.2 Example: file analysis6.6 Mutable Objects and references6.6.1 Shallow vs. deep copy6.6.2 Mutable Implementations6.7 Tuples6.7.1 Tuples from Lists6.7.2 Why tuples?6.8 Lists, the Data Structure6.8.1 Example data structure6.8.2 What are some other example data structures?6.9 Algorithm Example: US EPA automobile mileage data6.10 Python Diversion: List Comprehension6.11 Visual Vignette: More Plotting6.11.1 Numpy arrays6.11.2 Plotting Trigonometric Functions6.12 Summary6.13 Exercises6.13.1 Programming Projects7 More on Functions7.1 Functions calling Functions7.2 Scope, a first cut7.2.1 Arguments, Parameters and Namespaces7.2.2 Passing Mutable Objects7.2.3 Returning a complex object.7.2.4 Refactoring evens()7.3 Default Values and Parameters as Keywords7.3.1 Example: Default Values and Parameter Keywords7.3.2 Issues with Default Values7.4 Functions as Objects7.4.1 Doc Strings7.5 Example: Determining a Final Grade7.5.1 The Data7.5.2 The Design7.5.3 Function: weightedGrade7.5.4 Function: grade7.5.5 Function main7.5.6 Example Use7.6 Esoterica: "by value" or "by reference"7.7 Conclusion7.8 Exercises7.8.1 Programming Projects8 Dictionaries and Sets8.1 Dictionaries8.1.1 Dictionary example8.1.2 Python Dictionaries8.1.3 Dictionary Indexing and Assignment8.1.4 Operators8.2 Word Count Example8.2.1 Count words in a string8.2.2 Word Frequency for Gettysburg Address8.2.3 Output and comments8.3 Periodic Table Example8.3.1 Working with CSV files8.3.2 Algorithm Overview8.3.3 Functions for Divide and Conquer8.4 Sets8.4.1 History8.4.2 What’s in a set?8.4.3 Python Sets8.4.4 Methods, Operators and Functions for Python sets8.4.5 Set methods8.5 Set Applications8.5.1 Relationship betweenWords of Different Documents8.5.2 Output and Comments8.6 Scope, the full story8.6.1 Namespaces and Scope8.6.2 Search rule for scope8.6.3 Local8.6.4 Global8.6.5 Built-ins8.6.6 Enclosed8.7 Python Pointer: Using Zip to Create Dictionaries8.8 Summary8.9 Visual Vignette: Bar Graph of Word Frequency8.9.1 Getting the data right8.9.2 Labels and the xticks command8.9.3 Plotting8.10 Exercises8.10.1 Programming Projects9 Files 9.1 What is a file?9.2 Accessing Files: Reading Text Files9.2.1 Other File Access Methods9.2.2 What’s really happening?9.3 Accessing Files: Writing Text Files9.4 Reading and Writing Text Files in a Program9.5 File Creation and Overwriting9.5.1 Universal New Line Format9.5.2 Moving around in a file9.6 Closing a file9.7 CSV Files9.7.1 csv module9.7.2 CSV reader9.7.3 CSVWriter9.7.4 Example, Update Some Grades9.8 Example: Reprompting for a “good” file name9.9 Module: os9.9.1 Directory/Folder structure9.9.2 Module os functions9.9.3 Module os example9.10 Summary9.11 Exercises9.11.1 Programming Projects10 More Program Development10.1 Introduction10.2 Divide and Conquer10.2.1 Top-Down Refinement10.3 The Breast Cancer Classifier10.3.1 The Problem10.3.2 The Approach: Classification10.3.3 Training and testing the classifier10.3.4 Building the classifier10.4 Designing the Classifier Algorithm10.4.1 Divided, now Conquer10.4.2 Data Structures10.4.3 File Format10.4.4 Function: makeTrainingSet10.5 Continuing the building process10.5.1 The makeTestSet() function10.5.2 The trainClassifier() function10.5.3 trainClassifer(), Round 210.5.4 Testing the classifier on new data10.5.5 The reportResults() function10.6 Running the Classifier on Full Data10.6.1 Training versus Testing10.7 Other interesting problems10.7.1 Tag Clouds10.7.2 S&P 500 predictions10.7.3 Predicting Religion with Flags10.8 Summary10.9 Exercises10.9.1 Programming Projects IV Classes: Making Your Own Data Structures & Algorithms11 Introduction to Classes 11.0.2 Simple Student Class11.1 Object-oriented programming11.1.1 Python is Object Oriented!11.1.2 Characteristics of OOP11.2 Working with Object Oriented Programming11.2.1 Class and Instance11.3 Working with classes and instances11.3.1 Built-in Class and Instance11.3.2 Our First Class11.3.3 Changing Attributes11.3.4 The special relationship between instance and class: instance-of11.4 Object Methods11.4.1 Using object methods11.4.2 Writing Methods11.4.3 The special argument self11.4.4 Methods are the interface to a class instance11.5 Fitting into the Python class model11.5.1 Making Programmer-defined Classes11.5.2 A Student Class11.5.3 Python-standard methods11.5.4 Now there are three: Class Designer, Programmer and User11.6 Example: Point class11.6.1 Construction11.6.2 Distance11.6.3 Summing two points11.6.4 Improving the Point Class11.7 Python and OOP11.7.1 Encapsulation11.7.2 Inheritance11.7.3 Polymorphism11.8 An aside: Python and other OOP languages11.8.1 Public vs. Private11.8.2 Indicating privacy using double underscores ( __ )11.8.3 Python’s Philosophy11.8.4 Modifying an Instance11.9 Conclusion11.10 Exercises11.10.1 Programming Projects12 More on Classes12.1 More about Class Properties12.1.1 Rational Number (Fraction) class example12.2 How does Python know?12.2.1 Classes, Types and Introspection12.2.2 Remember Operator Overloading12.3 Creating Your Own Operator Overloading12.3.1 Mapping Operators to Special Methods12.4 Building the Rational Number Class12.4.1 Making the Class12.4.2 Review Fraction Addition12.4.3 Back to Adding Fractions12.4.4 Equality and Reducing Fractions12.4.5 Divide-and-Conquer at work12.5 What doesn’t work (yet)12.5.1 Introspection12.5.2 Repairing int + Rational Errors12.6 Inheritance12.6.1 The “Find the Attribute” Game12.6.2 Using Inheritance12.6.3 An example, the StandardModel12.7 Summary12.8 Exercises13 Program Development with Classes 13.1 Predator-prey Problem13.1.1 The rules13.1.2 Simulation using Object Oriented programming13.2 Classes13.2.1 Island Class13.2.2 Predator and Prey, kinds of Animals13.2.3 Predator and Prey Class13.2.4 Object Diagram13.2.5 Filling the Island13.3 Adding Behavior13.3.1 Refinement: AddMovement13.3.2 Refinement: Time simulation loop13.4 Refinement: Eating, Breeding and Keeping Time13.4.1 Improved Time Loop13.4.2 Breeding13.4.3 Eating13.4.4 The tick of the clock13.5 Refinements13.5.1 Refinement: How many times to move?13.5.2 Refinement: Graphing Population Size13.6 Conclusion13.7 ExercisesV Becoming a Better Programmer 14 Exceptions and Exception Handling14.1 Introduction14.2 Basic Exception Handling14.2.1 A simple example14.3 A philosophy concerning exceptions14.4 Exception: else and finally14.4.1 Example: Refactoring the reprompting of a file name14.5 Exception usage14.5.1 Check input14.5.2 Check file opening14.6 More on exceptions14.6.1 Raise14.6.2 Create your own14.7 Example: Password Manager14.8 Summary14.9 Examples15 Testing 15.1 Why Testing?15.1.1 Kinds of errors15.1.2 “Bugs” and debugging15.2 Kinds of Testing15.2.1 Testing is hard!15.2.2 Importance of Testing15.3 Example Problem15.3.1 NBA efficiency15.3.2 Basic Algorithm15.4 Incorporating Testing15.4.1 Catching User Errors15.4.2 Catching Developer Errors15.5 Automation of Testing15.5.1 doctest15.5.2 Other kinds of testing15.6 Conclusion15.7 Exercises16 Recursion—another control mechanism 16.1 What is recursion?16.2 Mathematics and Rabbits16.3 Let’s write our own: reversing a string16.4 How does recursion actually work?16.4.1 Stack Data Structure16.4.2 Stacks and Function Calls16.5 Recursion in figures16.5.1 Recursive tree16.5.2 Sierpinski triangles16.6 Recursion to Non-recursion16.7 Conclusion16.8 ExercisesA Getting and Using Python A.1 About Python A.1.1 History A.1.2 Python is free and portable A.1.3 Starting Python Up A.1.4 Working with Python A.1.5 Making a Program A.2 Some Conventions for this Book A.2.1 Interactive Code A.2.2 Program: Written Code A.2.3 Combined Program and Output A.3 SummaryB Simple Drawing with Turtle GraphicsB.1 Tidbits B.1.1 Keeping the window open B.1.2 Working nicely with IDLEC Plotting and Numeric Tools, a Quick Survey C.1 Matplotlib C.1.1 Getting matplotlib C.2 Working with matplotlib C.2.1 Plot command C.2.2 Plot properties C.2.3 Tick Labels C.2.4 Bar Graphs C.2.5 Histograms C.2.6 Pie Charts C.3 Numeric Python (Numpy)C.3.1 Arrays are not lists C.3.2 Creating a numpy array C.3.3 Manipulating arraysD Python 3.0 D.1 Simpler Built-in Types D.2 Unsurprising Arithmetic D.3 Cleaner Comparisons D.4 Consistent I/O D.5 Iterator Changes D.6 String module D.7 Conversion D.8 Text Examples in Python 3.x D.9 ConclusionE Table of ASCII valuesF Precedence