Problem Solving with Python: Using Computational Thinking in Everyday Life

Contents....8 Welcome....18 1. Read a Children’s Book....26 Problem Solving, in General....26 Problem Solving, in Detail....27 Our First Computational Problem....29 Imagine a Specific Instance....30 Sketch Using Computational Thinking....30 Capturing This Thinking....32 An Environment for Coding....32 Our Generic IDE....33 Our First Pseudocode....35 Comments....35 Commands and Input Parameters....35 Scripts Versus Execution....36 Our First Error....37 The Interactive Interpreter....37 Code and Transcript Blocks....38 Interacting with the Interpreter....39 The Interpreter as a Calculator....39 Python Help....40 Revisiting Our First Error....40 Undefined Names....41 Talking Through Your Confusion....41 Naming a Computation’s Result....42 Debugging....43 Showtime....43 Printing to the Console Pane....44 Statements, Objects, Attributes, and Types....44 Namespaces....45 Strings and String Literals....46 Variables....47 Valid Names in Python....47 Terminology Illustrated....48 Aliasing....49 Reading Two Lines....51 Carriage Returns....51 Reading an Entire Story....52 Creating a Loop....53 End of File (EOF)....54 Three Major Tasks....55 Testing a Condition....56 Exiting the Loop....56 Indentation....57 Loop Until....57 Any Book....59 This Problem, in General....60 Historical References to Computational Thinking....60 2. Grab the Dialogue....62 What Is the Current Task?....62 A New Problem....63 Splitting the Problem into Small Pieces....64 Reuse....64 Switching Between Goals....66 Finite State Machines....66 Error Handling in FSMs....67 Encoding the State Information....68 This or That....69 Work on a State....69 Strings as a Sequence of Characters....70 Membership Test....71 Coding a Transition....71 Indexing and Slicing....72 For-Loops....73 String Find....75 Design Patterns for Error Handling....76 Never Go Too Long Without Testing....76 Concatenation, Overloading, and Shorthands....77 Off-by-One and Other Potential Errors....78 Testing....78 Beware of Hidden Assumptions....80 Function Composition....80 Abstraction as Information Hiding....83 There Is No Character....83 3. Replace Text with Emoji....84 Internationalization....85 Encoding....85 Standards....87 Unicode....87 A New Problem....88 Decomposition to Reduce the Problem’s Complexity....88 Strings as Immutable Sequences....89 Encode an Emoji in Unicode....90 Multiple Different Replacements....92 Feeling Overwhelmed?....92 Functions....93 Function Definitions....94 The Actual Function Definition and Its Invocation....95 Function Execution....97 Abstraction, Decomposition, and Algorithms....98 Definition Before Use....99 Python’s Special Variables....99 Docstrings....101 Getting a Feel for Abstraction....101 Another Kind of Abstraction....102 Lists Are Sequence Objects....103 Abstraction Barriers....105 Methods....106 Modules....107 Avoiding Main....109 Pure Functions....109 4. Query a Web Resource....112 Packages and Libraries....112 APIs....113 A New Problem....113 Searching Wikipedia....114 The Client-Server Programming Model....116 Resources, Transactions, and Protocols....117 The URL....118 The Programmable Web....119 Python Dictionaries....120 An HTTP Response....123 The Response Header....125 JSON and the Response Body....126 Enumerating Answers from HOLLIS....128 Beyond Printing....129 Blocking and Non-Blocking Function Calls....132 5. Play Guess-a-Number....134 Guessing a Number....135 The Player’s Guess....137 Type Conversion....138 Try and Recover....139 The Game Loop....140 Testing Our Proposed Solution....141 A Networked Architecture....141 Its Sequence Diagram....144 When to Use a New Library....145 Sockets in Action....146 Specifying the Other Party....147 Sending and Receiving Messages....148 Size Matters....150 Encoding Again!....150 A Simplified Networking Interface....151 The Server....152 A Connection....153 Picking Up a Call....154 The Conversation....154 Programmer Beware....156 Run It!....157 6. Do You See My Dog?....160 Numbers and Knowledge....161 Do You See My Dog?....162 No Interpretation, Please....163 Reading a Hexdump....164 Hexadecimal Explained....165 Converting Between Number Systems....166 Does the Computer See My Dog?....167 Painting a Picture....168 Bits....169 One Finger, No Thumb....170 The Digital Abstraction....170 Bits, Bytes, and Nibbles....171 Setting a Pixel’s Color....171 Saturation....172 Overflow and Underflow....173 Finding Edges....174 7. Many but Not Any Number....178 Floating-Point Numbers and Numerical Computing....178 Computers Struggle with Arithmetic?....179 The Range of an FP Number....180 Precision....180 Illustrating This Issue of Precision....181 Getting Started....182 One Bit at a Time....183 Searching for the Smallest Difference....183 FP Errors Accumulate....185 8. What Is My Problem?....186 Data Science....186 Images as Data About the World....187 Yes, You Must Clean Up....188 Understanding What Might Go Wrong....188 Noise and Its Removal....189 The Power to Create New Realities....190 A Process for Eliminating Photobombing....190 This Data Is Not Wrong, but . . .....191 Zero Out the Unnecessary Details....192 No Visible Difference....196 Image Steganography....197 Where Is That Pixel?....197 And How Did We Get There?....198 Visualizing a Traversal....198 Inverting a Pixel’s Color....199 Naming the Traversal....200 Specifying the Range You Want....201 Storing a 2D Array in Memory....202 What You’ve Learned....203 9. Find a Phrase....206 A Complex Problem-to-Be-Solved....206 Some Basic Facts....208 Which Algorithm?....208 Algorithms, Formally....209 A Well-Studied Specification for String Matching....209 Is a Specification an Algorithm?....210 A Brute-Force Algorithm....211 A BF-String-Matching Program....211 One Algorithm, Multiple Implementations....213 Evaluation....214 Evaluation in Context....214 Measuring Performance....215 How Do We Do Better?....217 Loops Are Where the Action Is....219 Computational Complexity....221 Computational Complexity in Action....221 Problem Unsolved....226 10. Build an Index....228 Strings to Numbers....229 A Simple Hash Function....230 Updating a Hash with O(1) Work....231 Allow Collisions....234 Other Applications of Hashing....237 Indices for Fast Data Retrieval....237 Hash Tables....238 The Speed of Array-Index Operations....238 With High Probability....240 Collision Resolution....240 Specification for Creating a Book Index....241 Building Top-Down....241 Updating the Index....244 Sort and Strip....247 11. Discover Driving Directions....250 A New Approach to Programming....250 Driving Directions, a Formal Specification....252 Parallels with Finite State Machines....253 Solutions with Specific Characteristics....253 Let’s Walk Before We Drive....253 A Random Walk....255 Will It Work?....255 A Short Walk, Please....256 No Loops....256 Only Visit New Spots....256 A Dog Walk....257 Simulation....259 Object-Oriented Programming....261 Classes....261 Building an Instance....263 Self and Instance Attributes....265 Methods....266 Representation Invariant....267 Magic Methods....267 Building on Others....269 General Maps....270 Keeping Track....270 Remembering How We Got There....274 The Solution....276 Depth-First Search (DFS)....278 Breadth-First Search (BFS)....279 Informed Searches....279 12. Divide and Conquer....282 A Specification for Sorting....283 Sorting in Python....284 Sorting in Descending Order....286 Sorting with Your Own Comparison Function....286 Sorting Playing Cards....288 Time Complexity of Brute-Force Sorting....289 Binary Search....290 Divide-and-Conquer Algorithms....292 From Split to Merge....293 Iterative Merge Sort....294 Recursion....295 Iterative Factorial....297 Recursive Merge Sort....298 Beckett’s Challenge....299 Its Base Case....299 The Play with a Single Actor....300 Looking for the Pattern....301 A Polished, Full Solution....302 13. Rewrite the Error Message....304 The Mistakes We Make in Problem Solving....305 Our Problem-to-Be-Solved....306 From the GUI to the Shell....308 Understanding Paths....309 From Paths to Programs....310 Redirecting Inputs and Outputs....312 Which Output?....312 Pattern Matching....313 Wildcards in the Shell....314 Regular Expressions....315 Finding Simple Words....315 Matching Metacharacters....316 Using REs....317 Finding Filenames....319 Python RE Extensions....320 Putting It All Together....322 Shell Pipes....322 Scripting What the Shell Did....323 Concurrency....324 Making python32 Look Like python3....324 14. The Dream of Bug Fixing....328 Finding All Bugs....329 Decision Problems....331 Uncomputable Problems....332 An Analysis That Finds a Bug....333 Running Our Simple Analysis....334 A Tool for Running Analyses....335 Grabbing a Function with a Syntax Error....337 Analyzing Other Functions....338 Using the Input....338 A Nontrivial Decision Problem....340 An Indecisive Decision Function....342 Insight from Indecision....343 Specifications Without Implementations....345 15. Embrace Runtime Debugging....346 The Duality of Code and Data....348 Breakpoints and Runtime State....348 Inserting a Breakpoint....349 Inserting a New Statement....351 Indenting That Statement....352 Launching a Script from Another....354 Instrumenting a Script....357 REPL....360 16. Catch Them Early....362 Divide-by-Zero Bugs....363 A Silly Coding Error....364 What’s Hidden?....367 Why Compile?....368 Finding Type Errors....369 To Squiggle or Not....369 Dynamic Typing....370 Why Types Are Interesting....371 Types Versus Values....372 Dynamic Type Checking....372 Static Type Checking....373 Type Hints....375 No Free Lunch....375 17. Build Prediction Models....378 Predicting Home Prices....379 Your Sister’s Data....379 Solving This Problem Ourselves....381 Machine Learning....383 Labeled Training Data....384 ML Workflow....385 Getting a Feel for the Data....386 Set the Prediction Target....388 Pick Some Features....388 Fit the Model to Our Data....389 Predicting Unseen Data....390 Model Validation....391 Making the Fit Just Right....392 Bias in ML....394 Classifying Comments as Toxic....395 More Art than Science....396 18. Use Generative AI....398 Navigating the Jagged Frontier....400 My Use of GAI....402 Large Language Models (LLMs)....403 The Operation of LLMs....404 Complexity from Simplicity....405 Training a Neural Network....406 Two Pieces to Problem Solving with GAI....407 An Easy Request?....408 Write the Script Ourselves....409 Ask ChatGPT....411 Is This Task Within the Frontier?....413 The Expanding Frontier....414 How to Problem-Solve with an LLM....414 Writing Good Prompts....416 Final Thoughts....418 Acknowledgments....420 Index....422