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 Binaryarithmetic
	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 Mynumber
		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 Summaryand 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 Astackadt
	*12.5 Adictionaryadt
	12.6 Summaryand Further Discovery
	*12.7 Projects
Bibliography
Index