Discovering Computer Science

Discovering Computer Science

by Jessen Havill
Released June 2015
Publisher(s): CRC Press
ISBN: 9781482254167

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Discovering Computer Science: Interdisciplinary Problems, Principles, and Python Programming introduces computational problem solving as a vehicle of discovery in a wide variety of disciplines. With a principles-oriented introduction to computational thinking, the text provides a broader and deeper introduction to computer science than typical introductory programming books.

Organized around interdisciplinary problem domains, rather than programming language features, each chapter guides students through increasingly sophisticated algorithmic and programming techniques. The author uses a spiral approach to introduce Python language features in increasingly complex contexts as the book progresses.

The text places programming in the context of fundamental computer science principles, such as abstraction, efficiency, and algorithmic techniques, and offers overviews of fundamental topics that are traditionally put off until later courses.

The book includes thirty well-developed independent projects that encourage students to explore questions across disciplinary boundaries. Each is motivated by a problem that students can investigate by developing algorithms and implementing them as Python programs.

The book's accompanying website — http://discoverCS.denison.edu — includes sample code and data files, pointers for further exploration, errata, and links to Python language references.

Containing over 600 homework exercises and over 300 integrated reflection questions, this textbook is appropriate for a first computer science course for computer science majors, an introductory scientific computing course or, at a slower pace, any introductory computer science course.

Table of contents

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

Product information

  • Title: Discovering Computer Science
  • Author(s): Jessen Havill
  • Release date: June 2015
  • Publisher(s): CRC Press
  • ISBN: 9781482254167