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.
Author(s): Thomas Mailund
Publisher: Apress
Year: 2021
Language: English
Pages: 670
City: New York
Table of Contents
About the Author
About the Technical Reviewer
Chapter 1: Introduction
Models of the World and Formalizing Problems
What Is Computational Thinking?
Computational Thinking in a Broader Context
What Is to Come
Chapter 2: Introducing Python Programming
Obtaining Python
Running Python
Expressions in Python
Logical (or Boolean) Expressions
Variables
Working with Strings
Lists
Tuples
Sets and Dictionaries
Input and Output
Conditional Statements (if Statements)
Loops (for and while)
Using Modules
Chapter 3: Introduction to Algorithms
Designing Algorithms
A Reductionist Approach to Designing Algorithms
Assertions and Invariants
Measuring Progress
Exercises for Sequential Algorithms
Below or Above
Exercises on Lists
Changing Numerical Base
The Sieve of Eratosthenes
Longest Increasing Substring
Compute the Powerset of a Set
Longest Increasing Subsequence
Merging
Chapter 4: Algorithmic Efficiency
The RAM Model of a Computer and Its Primitive Operations
Counting Primitive Operations Exercises
Types of Efficiency
Best-Case, Worst-Case, and Average-Case (or Expected-Case) Complexity
Exercise
Amortized Complexity
Asymptotic Running Time and Big-Oh Notation
Other Classes
Properties of Complexity Classes
Reasoning About Algorithmic Efficiency Using the Big-Oh Notation
Doing Arithmetic in Big-Oh
Important Complexity Classes
Asymptotic Complexity Exercises
Function Growth
Insertion Sort
Binary Search
Sieve of Eratosthenes
The Longest Increasing Substring
Merging
Empirically Validating Algorithms’ Running Time
Chapter 5: Searching and Sorting
Searching
Linear Search
Binary Search
Sorting
Built-In Sorting in Python
Comparison Sorts
Selection Sort
Insertion Sort
Bubble Sort
Index-Based Sorting Algorithms
Bucket Sort
Radix Sort
Generalizing Searching and Sorting
How Computers Represent Numbers
Layout of Bytes in a Word
Two’s-Complement Representation of Negative Numbers
Chapter 6: Functions
Parameters and Local and Global Variables
Side Effects
Returning from a Function
Higher-Order Functions
Functions vs. Function Instances
Default Parameters and Keyword Arguments
Generalizing Parameters
Exceptions
Writing Your Own Python Modules
Chapter 7: Inner Functions
A Comparison Function for a Search Algorithm
Counter Function
Apply
Currying Functions
Function Composition
Thunks and Lazy Evaluation
Lambda Expressions
Decorators
Efficiency
Chapter 8: Recursion
Definitions of Recursion
Recursive Functions
Recursion Stacks
Recursion and Iteration
Tail Calls
Continuations
Continuations, Thunks, and Trampolines
Chapter 9: Divide and Conquer and Dynamic Programming
Merge Sort
Quick Sort
Divide and Conquer Running Times
Frequently Occurring Recurrences and Their Running Times
Dynamic Programming
Engineering a Dynamic Programming Algorithm
Edit Distance
Recursion
Memoization
Dynamic Programming
Backtracking
Partitioning
Recursion
Dynamic Programming
Representing Floating-Point Numbers
Chapter 10: Hidden Markov Models
Probabilities
Conditional Probabilities and Dependency Graphs
Markov Models
Hidden Markov Models
Forward Algorithm
Viterbi Algorithm
Chapter 11: Data Structures, Objects, and Classes
Classes
Exceptions and Classes
Methods
Polymorphism
Abstract Data Structures
Magical Methods
Class Variables
Attributes (The Simple Story)
Objects, Classes, and Meta-classes
Getting Attributes
Setting Attributes
Properties
Descriptors
Return of the Decorator
Chapter 12: Class Hierarchies and Inheritance
Inheritance and Code Reuse
Multiple Inheritance
Mixins
Chapter 13: Sequences
Sequences
Linked Lists Sequences
Iterative Solutions
Adding a Dummy Element
Analysis
Concatenating
Adding an Operation for Removing the First Element
Remove the Last Element
Doubly Linked Lists
Adding a Last Dummy
A Word on Garbage Collection
Iterators
Python Iterators and Other Interfaces
Generators
Chapter 14: Sets
Sets with Built-In Lists
Linked Lists Sets
Search Trees
Inserting
Removing
Iterator
Analysis
Wrapping the Operations in a Set Class
Persistent and Ephemeral Data Structures
An Iterative Solution
A Dummy Value for Removing Special Cases
Restrictions to Your Own Classes
Garbage Collection
Hash Table
Hash Functions
Collision strategy
Analysis
Resizing
Dictionaries
Chapter 15: Red-Black Search Trees
A Persistent Recursive Solution
Insertion
A Domain-Specific Language for Tree Transformations
Deletion
Pattern Matching in Python
An Iterative Solution
Checking if a Value Is in the Search Tree
Inserting
Deleting
The Final Set Class
An Amortized Analysis
Chapter 16: Stacks and Queues
Building Stacks and Queues from Scratch
Expression Stacks and Stack Machines
Quick Sort and the Call Stack
Writing an Iterator for a Search Tree
Merge Sort with an Explicit Stack
Breadth-First Tree Traversal and Queues
Chapter 17: Priority Queues
A Tree Representation for a Heap
Leftist Heaps
Binomial Heaps
Binary Heaps
Adding Keys and Values
Binary Heap
Leftist Heaps
Binomial Heaps
Search Trees
Comparisons
Search Tree
Leftist Heap
Binomial Heap
Binary Heap
Other Heaps
Huffman Encoding
Chapter 18: Conclusions
Where to Go from Here
Index
