Introduction to Computational Thinking : Problem Solving, Algorithms, Data Structures, and More

Learn approaches of computational thinking and the art of designing algorithms. Most of the algorithms you will see in this book are used in almost all software that runs on your computer. Learning how to program can be very rewarding. It is a special feeling to seeing a computer translate your thoughts into actions and see it solve your problems for you. To get to that point, however, you must learn to think about computations in a new way―you must learn computational thinking. This book begins by discussing models of the world and how to formalize problems. This leads onto a definition of computational thinking and putting computational thinking in a broader context. The practical coding in the book is carried out in Python; you’ll get an introduction to Python programming, including how to set up your development environment. What You Will Learn Think in a computational way Acquire general techniques for problem solving See general and concrete algorithmic techniques Program solutions that are both computationally efficient and maintainable Who This Book Is For Those new to programming and computer science who are interested in learning how to program algorithms and working with other computational aspects of programming. Table of Contents 4 About the Author 12 About the Technical Reviewer 13 Chapter 1: Introduction 14 Models of the World and Formalizing Problems 16 What Is Computational Thinking? 17 Computational Thinking in a Broader Context 21 What Is to Come 24 Chapter 2: Introducing Python Programming 26 Obtaining Python 27 Running Python 28 Expressions in Python 28 Logical (or Boolean) Expressions 32 Variables 35 Working with Strings 36 Lists 39 Tuples 43 Sets and Dictionaries 43 Input and Output 45 Conditional Statements (if Statements) 47 Loops (for and while) 50 Using Modules 52 Chapter 3: Introduction to Algorithms 54 Designing Algorithms 57 A Reductionist Approach to Designing Algorithms 60 Assertions and Invariants 64 Measuring Progress 67 Exercises for Sequential Algorithms 69 Below or Above 70 Exercises on Lists 73 Changing Numerical Base 73 The Sieve of Eratosthenes 75 Longest Increasing Substring 76 Compute the Powerset of a Set 76 Longest Increasing Subsequence 76 Merging 77 Chapter 4: Algorithmic Efficiency 78 The RAM Model of a Computer and Its Primitive Operations 79 Counting Primitive Operations Exercises 85 Types of Efficiency 86 Best-Case, Worst-Case, and Average-Case (or Expected-Case) Complexity 87 Exercise 89 Amortized Complexity 89 Asymptotic Running Time and Big-Oh Notation 93 Other Classes 95 Properties of Complexity Classes 96 Reasoning About Algorithmic Efficiency Using the Big-Oh Notation 97 Doing Arithmetic in Big-Oh 98 Important Complexity Classes 102 Asymptotic Complexity Exercises 104 Function Growth 104 Insertion Sort 105 Binary Search 105 Sieve of Eratosthenes 105 The Longest Increasing Substring 106 Merging 106 Empirically Validating Algorithms’ Running Time 106 Chapter 5: Searching and Sorting 110 Searching 110 Linear Search 111 Binary Search 112 Sorting 114 Built-In Sorting in Python 118 Comparison Sorts 118 Selection Sort 118 Insertion Sort 121 Bubble Sort 124 Index-Based Sorting Algorithms 131 Bucket Sort 132 Radix Sort 136 Generalizing Searching and Sorting 140 How Computers Represent Numbers 144 Layout of Bytes in a Word 145 Two’s-Complement Representation of Negative Numbers 149 Chapter 6: Functions 152 Parameters and Local and Global Variables 156 Side Effects 161 Returning from a Function 165 Higher-Order Functions 169 Functions vs. Function Instances 173 Default Parameters and Keyword Arguments 175 Generalizing Parameters 179 Exceptions 183 Writing Your Own Python Modules 190 Chapter 7: Inner Functions 192 A Comparison Function for a Search Algorithm 194 Counter Function 198 Apply 201 Currying Functions 204 Function Composition 207 Thunks and Lazy Evaluation 208 Lambda Expressions 212 Decorators 213 Efficiency 218 Chapter 8: Recursion 219 Definitions of Recursion 219 Recursive Functions 220 Recursion Stacks 223 Recursion and Iteration 231 Tail Calls 238 Continuations 243 Continuations, Thunks, and Trampolines 252 Chapter 9: Divide and Conquer and Dynamic Programming 258 Merge Sort 259 Quick Sort 260 Divide and Conquer Running Times 268 Frequently Occurring Recurrences and Their Running Times 270 Dynamic Programming 278 Engineering a Dynamic Programming Algorithm 285 Edit Distance 286 Recursion 286 Memoization 287 Dynamic Programming 288 Backtracking 290 Partitioning 292 Recursion 293 Dynamic Programming 294 Representing Floating-Point Numbers 295 Chapter 10: Hidden Markov Models 300 Probabilities 300 Conditional Probabilities and Dependency Graphs 307 Markov Models 309 Hidden Markov Models 315 Forward Algorithm 318 Viterbi Algorithm 323 Chapter 11: Data Structures, Objects, and Classes 327 Classes 328 Exceptions and Classes 333 Methods 337 Polymorphism 342 Abstract Data Structures 345 Magical Methods 346 Class Variables 349 Attributes (The Simple Story) 354 Objects, Classes, and Meta-classes 356 Getting Attributes 358 Setting Attributes 363 Properties 364 Descriptors 370 Return of the Decorator 371 Chapter 12: Class Hierarchies and Inheritance 378 Inheritance and Code Reuse 385 Multiple Inheritance 391 Mixins 398 Chapter 13: Sequences 401 Sequences 401 Linked Lists Sequences 403 Iterative Solutions 406 Adding a Dummy Element 408 Analysis 410 Concatenating 410 Adding an Operation for Removing the First Element 412 Remove the Last Element 414 Doubly Linked Lists 418 Adding a Last Dummy 424 A Word on Garbage Collection 432 Iterators 438 Python Iterators and Other Interfaces 440 Generators 445 Chapter 14: Sets 451 Sets with Built-In Lists 454 Linked Lists Sets 458 Search Trees 460 Inserting 462 Removing 463 Iterator 465 Analysis 466 Wrapping the Operations in a Set Class 467 Persistent and Ephemeral Data Structures 468 An Iterative Solution 470 A Dummy Value for Removing Special Cases 476 Restrictions to Your Own Classes 478 Garbage Collection 479 Hash Table 482 Hash Functions 483 Collision strategy 487 Analysis 489 Resizing 489 Dictionaries 493 Chapter 15: Red-Black Search Trees 496 A Persistent Recursive Solution 497 Insertion 497 A Domain-Specific Language for Tree Transformations 500 Deletion 510 Pattern Matching in Python 530 An Iterative Solution 533 Checking if a Value Is in the Search Tree 538 Inserting 539 Deleting 543 The Final Set Class 549 An Amortized Analysis 551 Chapter 16: Stacks and Queues 553 Building Stacks and Queues from Scratch 558 Expression Stacks and Stack Machines 566 Quick Sort and the Call Stack 576 Writing an Iterator for a Search Tree 578 Merge Sort with an Explicit Stack 582 Breadth-First Tree Traversal and Queues 587 Chapter 17: Priority Queues 589 A Tree Representation for a Heap 591 Leftist Heaps 595 Binomial Heaps 601 Binary Heaps 613 Adding Keys and Values 621 Binary Heap 622 Leftist Heaps 627 Binomial Heaps 630 Search Trees 632 Comparisons 633 Search Tree 633 Leftist Heap 634 Binomial Heap 635 Binary Heap 636 Other Heaps 636 Huffman Encoding 637 Chapter 18: Conclusions 642 Where to Go from Here 643 Index 645