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

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