Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming

Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface
Acknowledgments
About the author
Chapter 1 ▪ How to Solve It
1.1 Understand the Problem
A first problem: computing reading level
Functional abstraction
1.2 Design an Algorithm
Take it from the top
Pseudocode
Implement from the bottom
1.3 Write a Program
Welcome to the circus
What's in a name?
Interactive computing
Looking ahead
1.4 Look Back
Testing
Algorithm efficiency
1.5 Summary and Further Discovery
Chapter 2 ▪ Visualizing Abstraction
2.1 Data Abstraction
Turtle graphics
2.2 Drawing Flowers and Plotting Earthquakes
Iteration
Tangent 2.1 Defining colors
Data visualization
2.3 Functional Abstraction
Function parameters
2.4 Programming in Style
Program structure
Documentation
Tangent 2.2 Global variables
Self-documenting code
2.5 A Return to Functions
The math module
Writing functions with return values
Return vs. print
2.6 Scope and Namespaces
Local namespaces
The global namespace
2.7 Summary and Further Discovery
Chapter 3 ▪ Inside a Computer
3.1 Computers are Dumb
Tangent 3.1 High performance computing
Machine language
Tangent 3.2 Byte code
3.2 Everything Is Bits
Bits are switches
Bits can represent anything
Tangent 3.3 Hexadecimal notation
Computing with bits
3.3 Computer Arithmetic
Limited precision
Tangent 3.4 Floating point notation
Error propagation
Division
Complex numbers
3.4 Binary Arithmetic
3.5 The Universal Machine
3.6 Summary and Further Discovery
Chapter 4 ▪ Growth and Decay
4.1 Accumulators
Managing a fishing pond
Measuring network value
Organizing a concert
4.2 Data Visualization
4.3 Conditional Iteration
When will the fish disappear?
When will your nest egg double?
4.4 Continuous Models
4.5 Numerical Analysis
4.6 Summing Up
Tangent 4.1 Triangular numbers
4.7 Further Discovery
4.8 Projects
Chapter 5 ▪ Forks in the Road
5.1 Random Walks
Tangent 5.1 Interval notation
One small step
Monte Carlo simulation
5.2 Pseudorandom Number Generators
5.3 Simulating Probability Distributions
5.4 Back to Booleans
Predicate functions
Short circuit evaluation
DeMorgan's laws
Thinking inside the box
Many happy returns
5.5 Defensive Programming
Checking parameters
Assertions
Unit testing
Tangent 5.2 Unit testing frameworks
Testing floats
Catching exceptions
5.6 Guess My Number
Ending the game nicely
Friendly hints
A proper win/lose message
5.7 Summary and Further Discovery
5.8 Projects
Chapter 6 ▪ Text, Documents, and DNA
6.1 First Steps
Normalization
Tangent 6.1 Natural language processing
Tokenization
Creating your own module
Testing your module
6.2 Text Documents
Reading from text files
Writing to text files
Reading from the web
6.3 Encoding Strings
Computing checksums
Unicode
Tangent 6.2 Compressing text files
Indexing and slicing
6.4 A Concordance
Finding a word
A concordance entry
A complete concordance
6.5 Word Frequency Trends
Finding the frequency of a word
Getting the frequencies in slices
Plotting the frequencies
6.6 Comparing Texts
Dot plots
6.7 Time Complexity
6.8 Computational Genomics
6.9 Summary and Further Discovery
6.10 Projects
Chapter 7 ▪ Data Analysis
7.1 Summary Statistics
Mean and variance
Minimum and maximum
7.2 Wrangling Data
Smoothing data
A more efficient algorithm
Modifying lists in place
List operators and methods
List comprehensions
Tangent 7.1 NumPy arrays
7.3 Tallying Frequencies
Word frequencies
Dictionaries
Tangent 7.2 Hash tables
Finding the most frequent word
Bigram frequencies
Tangent 7.3 Sentiment analysis
7.4 Reading Tabular Data
Earthquakes
7.5 Designing Efficient Algorithms
7.6 Linear Regression
7.7 Data Clustering
7.8 Summary and Further Discovery
Tangent 7.4 Privacy in the age of big data
7.9 Projects
Chapter 8 ▪ Flatland
8.1 Tabular Data
Reading a table of temperatures
Tangent 8.1 Pandas
8.2 The Game of Life
Creating a grid
Initial configurations
Surveying the neighborhood
Performing one pass
Tangent 8.2 NumPy arrays in two dimensions
Updating the grid
8.3 Digital Images
Colors
Tangent 8.3 Additive vs. subtractive color models
Image filters
Tangent 8.4 Image storage and compression
Transforming images
8.4 Summary and Further Discovery
8.5 Projects
Chapter 9 ▪ Self-similarity and Recursion
9.1 Fractals
Trees
Snowflakes
9.2 Recursion and Iteration
Solving a problem recursively
Palindromes
Guessing passwords
9.3 The Mythical Tower of Hanoi
Is the end of the world nigh?
9.4 Recursive Linear Search
Efficiency of recursive linear search
9.5 Divide and Conquer
Buy low, sell high
Navigating a maze
9.6 Lindenmayer Systems
9.7 Summary and Further Discovery
9.8 Projects
Chapter 10 ▪ Organizing Data
10.1 Binary Search
Tangent 10.1 Databases
Efficiency of iterative binary search
A spelling checker
Recursive binary search
Efficiency of recursive binary search
10.2 Selection Sort
Implementing selection sort
Efficiency of selection sort
Querying data
10.3 Insertion Sort
Implementing insertion sort
Efficiency of insertion sort
10.4 Efficient Sorting
Merge sort
Internal vs. external sorting
Efficiency of merge sort
10.5 Tractable and Intractable Algorithms
10.6 Summary and Further Discovery
10.7 Projects
Chapter 11 ▪ Networks
11.1 Modeling With Graphs
Making friends
11.2 Shortest Paths
Breadth-first search
Finding the actual paths
11.3 It's a Small World…
Small world networks
Clustering coefficients
Scale-free networks
11.4 Random Graphs
11.5 Summary and Further Discovery
11.6 Projects
Chapter 12 ▪ Object-oriented Design
12.1 Simulating an Epidemic
Object design
Person class
Augmenting the Person class
World class
The simulation
12.2 Operators and Polymorphism
Designing a Pair ADT
Pair class
Arithmetic methods
Special methods
Comparison operators
Indexing
12.3 A Flocking Simulation
12.4 A Stack ADT
12.5 A Dictionnary ADT
12.6 Summary and Further Discovery
12.7 Projects
Bibliography
Index