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

An innovative new way to teach computational thinking and problem solving that makes programming accessible to anyone.

Problem solving with computation has become a basic literacy required of modern life, but the traditional way we teach students to code doesn’t work for everyone. This innovative textbook provides a highly engaging alternative approach. Problem Solving with Python is a hands-on introduction to computational thinking, useful computer science concepts, and the art of computer programming, where skills and ideas are introduced in service of solving an interesting problem.

Each chapter begins with an ambiguous problem description drawn from everyday life that resolves with a piece of working code. Gradually progressing in difficulty, the book’s three-act structure charts a clear developmental path from novice to skilled programmer. Michael Smith first presents the basics of programming through repeated application of a worklist algorithm, allowing the reader to become comfortable in problem decomposition and fundamentals before attempting more complicated algorithms and approaches. He then shows how to solve real-world problems using the power of abstraction, algorithms, and the right data structures. Finally, the exercises in the book’s last act fully transition the reader from programmer to problem solver. Based on the author's popular class at Harvard, this accessible textbook builds conceptual understanding through practical skills development to enable anyone to master the what and how of computational thinking.

• Prioritizes the development of computational thinking
• Does not assume students are intrinsically motivated to learn programming
• Emphasizes active learning through real-world problems and case studies
• Is suitable for students and self-learners from all backgrounds
• Includes coverage of data representation, arithmetic and logical operations, algorithms, networks, computability, operating systems and compilers, memory systems, and security
• Offers extensive ancillary resources