Practice of Computing using Python, The

Table of Contents

Contents
I Thinking About Computing
0 The Study of Computer Science
0.1 Why Computer Science?
0.1.1 Importance of Computer Science
0.1.2 Computer “Science”
0.1.3 Computer Science Through Computer Programming
0.2 The Difficulty and Promise of Programming
0.2.1 Difficulty 1: two things at once
0.2.2 Difficulty 2: What is a good program?
0.2.3 The Promise of a Computer Program
0.3 Choosing a Computer Language
0.3.1 Different Computer Languages
0.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 Nature
0.5.2 The Human Computer
0.6 The Modern, Electronic Computer
0.6.1 It’s the Switch!
0.6.2 The Transistor
0.7 A High Level look at a Modern Computer
0.8 Representing Data
0.8.1 Binary Data
0.8.2 Working with Binary
0.8.3 Limits
0.8.4 Representing Letters
0.8.5 Representing other Data
0.8.6 What does a number represent?
0.8.7 How to talk about quantities of data
0.8.8 How much data is that?
0.9 Overview of Coming Chapters
0.10 Summary
II Starting to Program
1 Beginnings
1.1 Practice, Practice, Practice
1.2 QUICKSTART 1, the Circumference Program
1.2.1 Examining the code
1.3 An Interactive Session
1.4 Parts of a Program
1.4.1 Modules
1.4.2 Statements and Expressions
1.4.3 Whitespace
1.4.4 Comments
1.4.5 Special Python Elements: Tokens
1.4.6 Naming Objects
1.5 Variables
1.5.1 Variable Creation and Assignment
1.6 Objects and Types
1.6.1 Numbers
1.6.2 Other Built-in Types
1.6.3 Object, not variable, types
1.6.4 Constructing new values
1.7 Operators
1.7.1 Integer Operators
1.7.2 Floating Point Operators
1.7.3 Mixed Operations
1.7.4 Order of Operations and Parenthesis
1.7.5 Augmented Assignment Operators: a shortcut!
1.8 Our first module, math
1.9 Developing an Algorithm
1.10 Conclusion
1.11 Visual Vignette: Turtle Graphic
1.12 Exercises
1.12.1 Programming Projects
2 Control
2.1 The selection statement for decisions: if
2.1.1 Booleans for decisions
2.1.2 The if statement
2.1.3 Example: what lead is safe in basketball?
2.1.4 Repetition
2.1.5 Example: Finding Perfect Numbers
2.2 In-depth Control
2.2.1 True and False: Booleans
2.2.2 Boolean Variables
2.2.3 Relational Operators
2.2.4 Boolean Operators
2.2.5 Precedence
2.2.6 Boolean Operators Example
2.2.7 Another Word on Assignments
2.2.8 The Selection statement for decisions
2.2.9 More on Python decision statements
2.2.10 Repetition: the while statement
2.2.11 Sentinel Loop
2.2.12 Summary of repetition
2.2.13 More on the for statement
2.2.14 Nesting
2.2.15 Hailstone Sequence example
2.2.16 Summary
2.3 Visual Vignette: Plotting Data with pylab
2.4 Computer Science Perspectives: Minimal Universal Computing
2.4.1 Minimal Universal Computing
2.5 Exercises
2.5.1 Programming Projects
3 Algorithms and Program Development
3.1 What is an algorithm?
3.1.1 Example Algorithms
3.2 Algorithm Features
3.2.1 Algorithm versus program
3.2.2 Detailed
3.2.3 Effective
3.2.4 Specify Behavior
3.2.5 General Purpose
3.2.6 Can we really do all that?
3.3 What is a program?
3.3.1 Readable
3.3.2 Robust
3.3.3 Correct
3.4 Strategies for program design
3.4.1 Engage and Commit
3.4.2 Understand, then visualize
3.4.3 Think before you Program
3.4.4 Try it: Experiment
3.4.5 Simplify
3.4.6 Stop and Think
3.4.7 Relax, give it a break
3.5 A simple example
3.5.1 Build the skeleton
3.5.2 Output
3.5.3 Input
3.5.4 Doing the calculation
3.6 Summary
3.7 Exercises
III Organizing: Data Structures and Functions
4 Working with Strings
4.1 The String type
4.1.1 The triple quote string
4.1.2 Non-printing characters
4.1.3 String representation
4.1.4 Strings as a sequence
4.1.5 More Indexing and Slicing
4.2 String operations
4.2.1 Concatenation (+) and Repetition (*)
4.2.2 When is + addition and when is it concatenation?
4.2.3 Comparison operators
4.2.4 The in operator
4.2.5 String collection is immutable
4.3 A preview of functions and methods
4.3.1 What is a function? First cut
4.3.2 A String Method
4.3.3 Determining method names and method arguments
4.3.4 String Methods
4.3.5 String functions
4.4 Formatted Output for Strings
4.4.1 Descriptor codes
4.4.2 Width Descriptor
4.4.3 Floating-point Precision Descriptor
4.5 Control and Strings
4.6 Working with strings
4.6.1 Example, reordering a person’s name
4.6.2 Palindromes
4.7 Example: Counting Poker Hands
4.7.1 Program to Count Poker Hands
4.8 Summary
4.9 Exercises
4.9.1 Programming Projects
5 Functions–QuickStart
5.1 What is a function?
5.1.1 Why have functions?
5.2 Python Functions
5.3 Flow of control with Functions
5.3.1 Function Flow in Detail
5.3.2 Another Function Example
5.3.3 Function Example: Word Puzzle
5.3.4 Functions calling Functions
5.3.5 When to use a Function
5.3.6 What if there is no return statement?
5.3.7 What if there are multiple return statements?
5.4 Conclusion
5.5 Visual Vignette: Turtle Flag
5.6 Exercises
5.6.1 Programming Projects
6 Lists and Tuples
6.1 What is a list?
6.2 What we already know how to do with lists (mostly)
6.2.1 Indexing and Slicing
6.2.2 Operators
6.2.3 Functions
6.2.4 List iteration
6.3 New things in Lists
6.3.1 Lists are Mutable
6.3.2 List Methods
6.4 Some old and new friends: range, split and other functions and methods
6.4.1 range, split and multiple assignment
6.4.2 List to string and back again, using join
6.4.3 The sorted function
6.5 Working with some Examples
6.5.1 Anagrams
6.5.2 Example: file analysis
6.6 Mutable Objects and references
6.6.1 Shallow vs. deep copy
6.6.2 Mutable Implementations
6.7 Tuples
6.7.1 Tuples from Lists
6.7.2 Why tuples?
6.8 Lists, the Data Structure
6.8.1 Example data structure
6.8.2 What are some other example data structures?
6.9 Algorithm Example: US EPA automobile mileage data
6.10 Python Diversion: List Comprehension
6.11 Visual Vignette: More Plotting
6.11.1 Numpy arrays
6.11.2 Plotting Trigonometric Functions
6.12 Summary
6.13 Exercises
6.13.1 Programming Projects
7 More on Functions
7.1 Functions calling Functions
7.2 Scope, a first cut
7.2.1 Arguments, Parameters and Namespaces
7.2.2 Passing Mutable Objects
7.2.3 Returning a complex object.
7.2.4 Refactoring evens()
7.3 Default Values and Parameters as Keywords
7.3.1 Example: Default Values and Parameter Keywords
7.3.2 Issues with Default Values
7.4 Functions as Objects
7.4.1 Doc Strings
7.5 Example: Determining a Final Grade
7.5.1 The Data
7.5.2 The Design
7.5.3 Function: weightedGrade
7.5.4 Function: grade
7.5.5 Function main
7.5.6 Example Use
7.6 Esoterica: "by value" or "by reference"
7.7 Conclusion
7.8 Exercises
7.8.1 Programming Projects
8 Dictionaries and Sets
8.1 Dictionaries
8.1.1 Dictionary example
8.1.2 Python Dictionaries
8.1.3 Dictionary Indexing and Assignment
8.1.4 Operators
8.2 Word Count Example
8.2.1 Count words in a string
8.2.2 Word Frequency for Gettysburg Address
8.2.3 Output and comments
8.3 Periodic Table Example
8.3.1 Working with CSV files
8.3.2 Algorithm Overview
8.3.3 Functions for Divide and Conquer
8.4 Sets
8.4.1 History
8.4.2 What’s in a set?
8.4.3 Python Sets
8.4.4 Methods, Operators and Functions for Python sets
8.4.5 Set methods
8.5 Set Applications
8.5.1 Relationship betweenWords of Different Documents
8.5.2 Output and Comments
8.6 Scope, the full story
8.6.1 Namespaces and Scope
8.6.2 Search rule for scope
8.6.3 Local
8.6.4 Global
8.6.5 Built-ins
8.6.6 Enclosed
8.7 Python Pointer: Using Zip to Create Dictionaries
8.8 Summary
8.9 Visual Vignette: Bar Graph of Word Frequency
8.9.1 Getting the data right
8.9.2 Labels and the xticks command
8.9.3 Plotting
8.10 Exercises
8.10.1 Programming Projects
9 Files
9.1 What is a file?
9.2 Accessing Files: Reading Text Files
9.2.1 Other File Access Methods
9.2.2 What’s really happening?
9.3 Accessing Files: Writing Text Files
9.4 Reading and Writing Text Files in a Program
9.5 File Creation and Overwriting
9.5.1 Universal New Line Format
9.5.2 Moving around in a file
9.6 Closing a file
9.7 CSV Files
9.7.1 csv module
9.7.2 CSV reader
9.7.3 CSVWriter
9.7.4 Example, Update Some Grades
9.8 Example: Reprompting for a “good” file name
9.9 Module: os
9.9.1 Directory/Folder structure
9.9.2 Module os functions
9.9.3 Module os example
9.10 Summary
9.11 Exercises
9.11.1 Programming Projects
10 More Program Development
10.1 Introduction
10.2 Divide and Conquer
10.2.1 Top-Down Refinement
10.3 The Breast Cancer Classifier
10.3.1 The Problem
10.3.2 The Approach: Classification
10.3.3 Training and testing the classifier
10.3.4 Building the classifier
10.4 Designing the Classifier Algorithm
10.4.1 Divided, now Conquer
10.4.2 Data Structures
10.4.3 File Format
10.4.4 Function: makeTrainingSet
10.5 Continuing the building process
10.5.1 The makeTestSet() function
10.5.2 The trainClassifier() function
10.5.3 trainClassifer(), Round 2
10.5.4 Testing the classifier on new data
10.5.5 The reportResults() function
10.6 Running the Classifier on Full Data
10.6.1 Training versus Testing
10.7 Other interesting problems
10.7.1 Tag Clouds
10.7.2 S&P 500 predictions
10.7.3 Predicting Religion with Flags
10.8 Summary
10.9 Exercises
10.9.1 Programming Projects
IV Classes: Making Your Own Data Structures & Algorithms
11 Introduction to Classes
11.0.2 Simple Student Class
11.1 Object-oriented programming
11.1.1 Python is Object Oriented!
11.1.2 Characteristics of OOP
11.2 Working with Object Oriented Programming
11.2.1 Class and Instance
11.3 Working with classes and instances
11.3.1 Built-in Class and Instance
11.3.2 Our First Class
11.3.3 Changing Attributes
11.3.4 The special relationship between instance and class: instance-of
11.4 Object Methods
11.4.1 Using object methods
11.4.2 Writing Methods
11.4.3 The special argument self
11.4.4 Methods are the interface to a class instance
11.5 Fitting into the Python class model
11.5.1 Making Programmer-defined Classes
11.5.2 A Student Class
11.5.3 Python-standard methods
11.5.4 Now there are three: Class Designer, Programmer and User
11.6 Example: Point class
11.6.1 Construction
11.6.2 Distance
11.6.3 Summing two points
11.6.4 Improving the Point Class
11.7 Python and OOP
11.7.1 Encapsulation
11.7.2 Inheritance
11.7.3 Polymorphism
11.8 An aside: Python and other OOP languages
11.8.1 Public vs. Private
11.8.2 Indicating privacy using double underscores ( __ )
11.8.3 Python’s Philosophy
11.8.4 Modifying an Instance
11.9 Conclusion
11.10 Exercises
11.10.1 Programming Projects
12 More on Classes
12.1 More about Class Properties
12.1.1 Rational Number (Fraction) class example
12.2 How does Python know?
12.2.1 Classes, Types and Introspection
12.2.2 Remember Operator Overloading
12.3 Creating Your Own Operator Overloading
12.3.1 Mapping Operators to Special Methods
12.4 Building the Rational Number Class
12.4.1 Making the Class
12.4.2 Review Fraction Addition
12.4.3 Back to Adding Fractions
12.4.4 Equality and Reducing Fractions
12.4.5 Divide-and-Conquer at work
12.5 What doesn’t work (yet)
12.5.1 Introspection
12.5.2 Repairing int + Rational Errors
12.6 Inheritance
12.6.1 The “Find the Attribute” Game
12.6.2 Using Inheritance
12.6.3 An example, the StandardModel
12.7 Summary
12.8 Exercises
13 Program Development with Classes
13.1 Predator-prey Problem
13.1.1 The rules
13.1.2 Simulation using Object Oriented programming
13.2 Classes
13.2.1 Island Class
13.2.2 Predator and Prey, kinds of Animals
13.2.3 Predator and Prey Class
13.2.4 Object Diagram
13.2.5 Filling the Island
13.3 Adding Behavior
13.3.1 Refinement: AddMovement
13.3.2 Refinement: Time simulation loop
13.4 Refinement: Eating, Breeding and Keeping Time
13.4.1 Improved Time Loop
13.4.2 Breeding
13.4.3 Eating
13.4.4 The tick of the clock
13.5 Refinements
13.5.1 Refinement: How many times to move?
13.5.2 Refinement: Graphing Population Size
13.6 Conclusion
13.7 Exercises
V Becoming a Better Programmer
14 Exceptions and Exception Handling
14.1 Introduction
14.2 Basic Exception Handling
14.2.1 A simple example
14.3 A philosophy concerning exceptions
14.4 Exception: else and finally
14.4.1 Example: Refactoring the reprompting of a file name
14.5 Exception usage
14.5.1 Check input
14.5.2 Check file opening
14.6 More on exceptions
14.6.1 Raise
14.6.2 Create your own
14.7 Example: Password Manager
14.8 Summary
14.9 Examples
15 Testing
15.1 Why Testing?
15.1.1 Kinds of errors
15.1.2 “Bugs” and debugging
15.2 Kinds of Testing
15.2.1 Testing is hard!
15.2.2 Importance of Testing
15.3 Example Problem
15.3.1 NBA efficiency
15.3.2 Basic Algorithm
15.4 Incorporating Testing
15.4.1 Catching User Errors
15.4.2 Catching Developer Errors
15.5 Automation of Testing
15.5.1 doctest
15.5.2 Other kinds of testing
15.6 Conclusion
15.7 Exercises
16 Recursion—another control mechanism
16.1 What is recursion?
16.2 Mathematics and Rabbits
16.3 Let’s write our own: reversing a string
16.4 How does recursion actually work?
16.4.1 Stack Data Structure
16.4.2 Stacks and Function Calls
16.5 Recursion in figures
16.5.1 Recursive tree
16.5.2 Sierpinski triangles
16.6 Recursion to Non-recursion
16.7 Conclusion
16.8 Exercises
A 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 Summary
B Simple Drawing with Turtle Graphics
B.1 Tidbits
B.1.1 Keeping the window open
B.1.2 Working nicely with IDLE
C 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 arrays
D 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 Conclusion
E Table of ASCII values
F Precedence