Discovering Computer Science

Interdisciplinary Problems, Principles, and Python Programming

Jessen Havill

• Publisher: Chapman and Hall/CRC
• Year: 2016
• Print ISBN: 9781482254143, 9781482254143
• eBook ISBN: 9781498786744
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

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.

CHAPTER 1

What is computation?

We need to do away with the myth that computer science is about computers. Computer science is no more about computers than astronomy is about telescopes, biology is about microscopes or chemistry is about beakers and test tubes. Science is not about tools, it is about how we use them and what we find out when we do.

Michael R. Fellows and Ian Parberry
Computing Research News (1993)

COMPUTERS are the most powerful tools ever invented, but not because of their versatility and speed, per se. Computers are powerful because they empower us to innovate and make unprecedented discoveries.

A computer is a machine that carries out a computation, a sequence of simple steps that transforms some initial information, an input, into some desired result, the output. Computer scientists harness the power of computers to solve complex problems by designing solutions that can be expressed as computations. The output of a computation might be a more efficient route for a spacecraft, a more effective protocol to control an epidemic, or a secret message hidden in a digital photograph.

Computer science has always been interdisciplinary, as computational problems arise in virtually every domain imaginable. Social scientists use computational models to better understand social networks, epidemics, population dynamics, markets, and auctions. Scholars working in the digital humanities use computational tools to curate and analyze classic literature. Artists are increasingly incorporating digital technologies into their compositions and performances. Computational scientists work in areas related to climate prediction, genomics, particle physics, neuroscience, and drug discovery.

In this book, we will explore the fundamental problem solving techniques of computer science, and discover how they can be used to model and solve a variety of interdisciplinary problems. In this first chapter, we will provide an orientation and lay out the context in which to place the rest of the book. We will further develop all of these ideas throughout, so don’t worry if they are not all crystal clear at first.

Figure 1.1 Some examples of computational problems.

1.1 PROBLEMS AND ABSTRACTION

Every useful computation solves a problem of some sort. A problem is fundamentally defined by the relationship between its input and its output, as illustrated in Figure 1.1. For each problem, we have an input entering on the left and a corresponding output exiting on the right. In between, a computation transforms the input into a correct output. When you listen to a song, the music player performs a computation to convert the digital music file (input) into a sound pattern (output). When you submit a web search request (input), your computer, and many others across the Internet, perform computations to get you results (outputs). And when you use GPS navigation, a device computes directions (output) based on your current position, your destination, and its stored maps (inputs).

Inputs and outputs are probably also familiar to you from high school algebra. When you were given an expression like

y = 18x + 31

or

f(x) = 18x + 31,

you may have thought about the variable x as a representation of the input and y, or f(x), as a representation of the output. In this example, when the input is x = 2, the output is y = 67, or f(x) = 67. The arithmetic that turns x into y is a very simple (and boring) example of a computation.

Reflection 1.1 What kinds of problems are you interested in? What are their inputs and outputs? Are the inputs and outputs, as you have defined them, sufficient to define the problem completely?

To use the technologies illustrated in Figure 1.1 you do not need to understand how the underlying computation transforms the input to the output; we can think of the computation as a “black box” and still use the technology effectively. We call this idea functional abstraction, a very important concept that we often take for granted. Put simply,

A functional abstraction describes how to use a tool or technology without necessarily providing any knowledge about how it works.

We exist in a world of abstractions; we could not function without them. We even think about our own bodies in terms of abstractions. Move your fingers. Did you need to understand how your brain triggered your nervous and musculoskeletal systems to make that happen? As far as most of us are concerned, a car is also an abstraction. To drive a car, do you need to know how turning the steering wheel turns the car or pushing the accelerator makes it go faster? We understand what should happen when we do these things, but not necessarily how they happen. Without abstractions, we would be paralyzed by an avalanche of minutiae.

Reflection 1.2 Imagine that it was necessary to understand how a GPS device works in order to use it. Or a music player. Or a computer. How would this affect your ability to use these technologies?

New technologies and automation have introduced new functional abstractions into everyday life. Our food supply is a compelling example of this. Only a few hundred years ago, our ancestors knew exactly where their food came from. Inputs of hard work and suitable weather produced outputs of grain and livestock to sustain a family. In modern times, we input money and get packaged food; the origins of our food have become much more abstract.

Reflection 1.3 Think about a common functional abstraction that you use regularly, such as your phone or a credit card. How has this functional abstraction changed over time? Can you think of instances in which better functional abstractions have enhanced our ability to use a technology?

We also use layers of functional abstractions to work more efficiently. For example, suppose you are the president of a large organization (like a university) that is composed of six divisions and 5,000 employees. Because you cannot effectively manage every detail of such a large organization, you assign a vice president to oversee each of the divisions. You expect each VP to keep you informed about the general activity and performance of that division, but insulate you from the day-today details. In this arrangement, each division becomes a functional abstraction to you: you know what each division does, but not necessarily how it does it. Benefitting from these abstractions, you are now free to focus your resources on more important organization-level activity. Each VP may utilize a similar arrangement within his or her division. Indeed, organizations are often subdivided many times until the number of employees in a unit is small enough to be overseen by a single manager.

Computers are similarly built from many layers of functional abstractions. When you use a computer, you are presented with a “desktop” abstraction on which you can store files and use applications (i.e., programs) to do work. That there appear to be many applications executing simultaneously is also an abstractio...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• Acknowledgments
• About the author
• CHAPTER 1 What is computation?
• CHAPTER 2 Elementary computations
• CHAPTER 3 Visualizing abstraction
• CHAPTER 4 Growth and decay
• CHAPTER 5 Forks in the road
• CHAPTER 6 Text, documents, and DNA
• CHAPTER 7 Designing programs
• CHAPTER 8 Data analysis
• CHAPTER 9 Flatland
• CHAPTER 10 Self-similarity and recursion
• CHAPTER 11 Organizing data
• CHAPTER 12 Networks
• CHAPTER 13 Abstract data types
• APPENDIX A Installing Python
• APPENDIX B Python library reference
• Bibliography
• Index