Home Page Icon
Home Page
Table of Contents for
Half Title
Close
Half Title
by Jessen Havill
Discovering Computer Science
Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface
Acknowledgments
About the author
CHAPTER 1 What is computation?
1.1 PROBLEMS AND ABSTRACTION
1.2 ALGORITHMS AND PROGRAMS
1.3 EFFICIENT ALGORITHMS
Organizing a phone tree
A smoothing algorithm
A better smoothing algorithm
1.4 COMPUTERS ARE DUMB
Inside a computer
Machine language
Everything is bits
The universal machine
1.5 SUMMARY
1.6 FURTHER DISCOVERY
CHAPTER 2 Elementary computations
2.1 WELCOME TO THE CIRCUS
2.2 ARITHMETIC
Finite precision
Division
Order of operations
Complex numbers
2.3 WHAT’S IN A NAME?
2.4 USING FUNCTIONS
Built-in functions
Strings
Modules
*2.5 BINARY ARITHMETIC
Finite precision
Negative integers
Designing an adder
Implementing an adder
2.6 SUMMARY
2.7 FURTHER DISCOVERY
CHAPTER 3 Visualizing abstraction
3.1 DATA ABSTRACTION
3.2 VISUALIZATION WITH TURTLES
Drawing with iteration
3.3 FUNCTIONAL ABSTRACTION
Function parameters
Let’s plant a garden
3.4 PROGRAMMING IN STYLE
Program structure
Documentation
Descriptive names and magic numbers
3.5 A RETURN TO FUNCTIONS
Return vs. print
3.6 SCOPE AND NAMESPACES
Local namespaces
The global namespace
3.7 SUMMARY
3.8 FURTHER DISCOVERY
CHAPTER 4 Growth and decay
4.1 DISCRETE MODELS
Managing a fishing pond
Measuring network value
Organizing a concert
4.2 VISUALIZING POPULATION CHANGES
4.3 CONDITIONAL ITERATION
*4.4 CONTINUOUS MODELS
Difference equations
Radiocarbon dating
Tradeoffs between accuracy and time
Propagation of errors
Simulating an epidemic
*4.5 NUMERICAL ANALYSIS
The harmonic series
Approximating π
Approximating square roots
4.6 SUMMING UP
4.7 FURTHER DISCOVERY
4.8 PROJECTS
Project 4.1 Parasitic relationships
Project 4.2 Financial calculators
*Project 4.3 Market penetration
*Project 4.4 Wolves and moose
CHAPTER 5 Forks in the road
5.1 RANDOM WALKS
A random walk in Monte Carlo
Histograms
*5.2 PSEUDORANDOM NUMBER GENERATORS
Implementation
Testing randomness
*5.3 SIMULATING PROBABILITY DISTRIBUTIONS
The central limit theorem
5.4 BACK TO BOOLEANS
Short circuit evaluation
Complex expressions
*Using truth tables
Many happy returns
5.5 A GUESSING GAME
5.6 SUMMARY
5.7 FURTHER DISCOVERY
5.8 PROJECTS
Project 5.1 The magic of polling
Project 5.2 Escape!
CHAPTER 6 Text, documents, and DNA
6.1 COUNTING WORDS
6.2 TEXT DOCUMENTS
Reading from text files
Writing to text files
Reading from the web
6.3 ENCODING STRINGS
Indexing and slicing
Creating modified strings
Encoding characters
6.4 LINEAR-TIME ALGORITHMS
Asymptotic time complexity
6.5 ANALYZING TEXT
Counting and searching
A concordance
6.6 COMPARING TEXTS
*6.7 GENOMICS
A genomics primer
Basic DNA analysis
Transforming sequences
Comparing sequences
Reading sequence files
6.8 SUMMARY
6.9 FURTHER DISCOVERY
6.10 PROJECTS
Project 6.1 Polarized politics
*Project 6.2 Finding genes
CHAPTER 7 Designing programs
7.1 HOW TO SOLVE IT
Understand the problem
Design an algorithm
Implement your algorithm as a program
Analyze your program for clarity, correctness, and efficiency
*7.2 DESIGN BY CONTRACT
Preconditions and postconditions
Checking parameters
Assertions
*7.3 TESTING
Unit testing
Regression testing
Designing unit tests
Testing floating point values
7.4 SUMMARY
7.5 FURTHER DISCOVERY
CHAPTER 8 Data analysis
8.1 SUMMARIZING DATA
8.2 CREATING AND MODIFYING LISTS
List accumulators, redux
Lists are mutable
Tuples
List operators and methods
*List comprehensions
8.3 FREQUENCIES, MODES, AND HISTOGRAMS
Tallying values
Dictionaries
8.4 READING TABULAR DATA
*8.5 DESIGNING EFFICIENT ALGORITHMS
A first algorithm
A more elegant algorithm
A more efficient algorithm
*8.6 LINEAR REGRESSION
*8.7 DATA CLUSTERING
Defining similarity
A k-means clustering example
Implementing k-means clustering
Locating bicycle safety programs
8.8 SUMMARY
8.9 FURTHER DISCOVERY
8.10 PROJECTS
Project 8.1 Climate change
Project 8.2 Does education influence unemployment?
Project 8.3 Maximizing profit
Project 8.4 Admissions
*Project 8.5 Preparing for a 100-year flood
Project 8.6 Voting methods
Project 8.7 Heuristics for traveling salespeople
CHAPTER 9 Flatland
9.1 TWO-DIMENSIONAL DATA
9.2 THE GAME OF LIFE
Creating a grid
Initial configurations
Surveying the neighborhood
Performing one pass
Updating the grid
9.3 DIGITAL IMAGES
Colors
Image filters
Transforming images
9.4 SUMMARY
9.5 FURTHER DISCOVERY
9.6 PROJECTS
Project 9.1 Modeling segregation
Project 9.2 Modeling ferromagnetism
Project 9.3 Growing dendrites
CHAPTER 10 Self-similarity and recursion
10.1 FRACTALS
A fractal tree
A fractal snowflake
10.2 RECURSION AND ITERATION
Solving a problem recursively
Palindromes
Guessing passwords
10.3 THE MYTHICAL TOWER OF HANOI
*Is the end of the world nigh?
10.4 RECURSIVE LINEAR SEARCH
Efficiency of recursive linear search
10.5 DIVIDE AND CONQUER
Buy low, sell high
Navigating a maze
*10.6 LINDENMAYER SYSTEMS
Formal grammars
Implementing L-systems
10.7 SUMMARY
10.8 FURTHER DISCOVERY
10.9 PROJECTS
*Project 10.1 Lindenmayer’s beautiful plants
Project 10.2 Gerrymandering
Project 10.3 Percolation
CHAPTER 11 Organizing data
11.1 BINARY SEARCH
Efficiency of iterative binary search
A spelling checker
Recursive binary search
Efficiency of recursive binary search
11.2 SELECTION SORT
Implementing selection sort
Efficiency of selection sort
Querying data
11.3 INSERTION SORT
Implementing insertion sort
Efficiency of insertion sort
11.4 EFFICIENT SORTING
Internal vs. external sorting
Efficiency of merge sort
*11.5 TRACTABLE AND INTRACTABLE ALGORITHMS
Hard problems
11.6 SUMMARY
11.7 FURTHER DISCOVERY
11.8 PROJECTS
Project 11.1 Creating a searchable database
Project 11.2 Binary search trees
CHAPTER 12 Networks
12.1 MODELING WITH GRAPHS
Making friends
12.2 SHORTEST PATHS
Finding the actual paths
12.3 IT’S A SMALL WORLD...
Clustering coefficients
Scale-free networks
12.4 RANDOM GRAPHS
12.5 SUMMARY
12.6 FURTHER DISCOVERY
12.7 PROJECTS
Project 12.1 Diffusion of ideas and influence
Project 12.2 Slowing an epidemic
Project 12.3 The Oracle of Bacon
CHAPTER 13 Abstract data types
13.1 DESIGNING CLASSES
Implementing a class
Documenting a class
13.2 OPERATORS AND SPECIAL METHODS
String representations
Arithmetic
Comparison
Indexing
13.3 MODULES
Namespaces, redux
13.4 A FLOCKING SIMULATION
The World ADT
The Boid ADT
13.5 A STACK ADT
13.6 A DICTIONARY ADT
Hash tables
Implementing a hash table
Implementing indexing
ADTs vs. data structures
13.7 SUMMARY
13.8 FURTHER DISCOVERY
13.9 PROJECTS
Project 13.1 Tracking GPS coordinates
Project 13.2 Economic mobility
Project 13.3 Slime mold aggregation
Project 13.4 Boids in space
APPENDIX A Installing Python
A.1 AN INTEGRATED DISTRIBUTION
A.2 MANUAL INSTALLATION
APPENDIX B Python library reference
B.1 MATH MODULE
B.2 TURTLE METHODS
B.3 SCREEN METHODS
B.4 MATPLOTLIB.PYPLOT MODULE
B.5 RANDOM MODULE
B.6 STRING METHODS
B.7 LIST METHODS
B.8 IMAGE MODULE
B.9 SPECIAL METHODS
Bibliography
Index
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Cover
Next
Next Chapter
Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming
DISCOVERING
COMPUTER
SCIENCE
Interdisciplinary Problems,
Principles, and Python
Programming
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset