Computational thinking for the modern problem Solver

Chapman & Hall/CRC
TEXTBOOKS IN COMPUTING
Computationalthinking
for the modern
problem Solver
david d. riley
kennya. hunt

Computationalthinking
for the modern
problem Solver
CHAPMAN & HALL/CRC
TEXTBOOKS IN COMPUTING
Series Editors
Published Titles
Paul Anderson, Web 2.0 and Beyond: Principles and Technologies
Henrik Brbak Christensen, Flexible, Reliable Software: Using Patterns and Agile
Development
John S. Conery, Explorations in Computing: An Introduction to Computer Science
Ted Herman, A Functional Start to Computing with Python
Pascal Hitzler, Markus Krtzsch, and Sebastian Rudolph, Foundations of Semantic Web
Technologies
Mark J. Johnson, A Concise Introduction to Data Structures using Java
Mark J. Johnson, A Concise Introduction to Programming in Python
Lisa C. Kaczmarczyk, Computers and Society: Computing for Good
Mark C. Lewis, Introduction to the Art of Programming Using Scala
Bill Manaris and Andrew R. Brown, Making Music with Computers: Creative Programming
in Python
Uvais Qidwai and C.H. Chen, Digital Image Processing: An Algorithmic Approach with
MATLAB
David D. Riley and Kenny A. Hunt, Computational Thinking for the Modern Problem Solver
Henry M. Walker, The Tao of Computing, Second Edition
John Impagliazzo
Professor Emeritus, Hofstra University
Andrew McGettrick
Department of Computer
and Information Sciences
University of Strathclyde
Aims and Scope
This series covers traditional areas of computing, as well as related technical areas, such as
software engineering, artificial intelligence, computer engineering, information systems, and
information technology. The series will accommodate textbooks for undergraduate and graduate students, generally adhering to worldwide curriculum standards from professional societies. The editors wish to encourage new and imaginative ideas and proposals, and are keen to
help and encourage new authors. The editors welcome proposals that: provide groundbreaking
and imaginative perspectives on aspects of computing; present topics in a new and exciting
context; open up opportunities for emerging areas, such as multi-media, security, and mobile
systems; capture new developments and applications in emerging fields of computing; and
address topics that provide support for computing, such as mathematics, statistics, life and
physical sciences, and business.
Chapman & Hall/CRC
TEXTBOOKS IN COMPUTING
Computationalthinking
for the modern
problem Solver
david d. riley and kennya. hunt
University of Wisconsin
La Crosse, USA
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
2014 by Taylor & Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Version Date: 20140206
International Standard Book Number-13: 978-1-4665-8779-3 (eBook – PDF)
This book contains information obtained from authentic and highly regarded sources. Reasonable
efforts have been made to publish reliable data and information, but the author and publisher cannot
assume responsibility for the validity of all materials or the consequences of their use. The authors and
publishers have attempted to trace the copyright holders of all material reproduced in this publication
and apologize to copyright holders if permission to publish in this form has not been obtained. If any
copyright material has not been acknowledged please write and let us know so we may rectify in any
future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,
transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or
hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222
Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are
used only for identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com
v
Contents
Preface, xiii
Authors, xv
Chapter 1 What Is Computational Thinking? 1
1.1 COMPUTERS, COMPUTERS EVERYWHERE 2
1.2 COMPUTER, COMPUTER SCIENCE, AND
COMPUTATIONAL THINKING 2
1.3 FROM ABACUS TO MACHINE 5
1.4 THE FIRST SOFTWARE 11
1.5 WHAT MAKES IT A MODERN COMPUTER? 14
1.6 THE FIRST MODERN COMPUTER 17
1.7 MOORES LAW 21
1.8 SUMMARY 23
1.9 WHEN WILL YOU EVER USE THIS STUFF? 23
REFERENCES 23
TERMINOLOGY 24
EXERCISES 25
Chapter 2 How Real-World Information Becomes
Computable Data 27
2.1 INFORMATION AND DATA 28
2.2 CONVERTING INFORMATION INTO DATA 29
2.3 DATA CAPACITY 33
vi Contents
2.4 DATA TYPES AND DATA ENCODING 35
2.4.1 Numbers 35
2.4.1.1 Numeral Systems 35
2.4.1.2 Positional Numeral System 37
2.4.1.3 Integers as Binary Bit Strings 39
2.4.1.4 Real Numbers as Binary Bit Strings 40
2.4.1.5 Precision as a Source of Error 41
2.4.1.6 Underflow and Overflow as Sources of Error 41
2.4.2 Text 41
2.4.3 Colors 42
2.4.4 Pictures 44
2.4.5 Sound 45
2.5 DATA COMPRESSION 47
2.5.1 Run-Length Encoding 49
2.6 SUMMARY 51
REFERENCE 52
TERMINOLOGY 52
EXERCISES 53
Chapter 3 Logic 57
3.1 WHAT IS LOGIC? 58
3.2 BOOLEAN LOGIC 59
3.2.1 Writing Well-Formed Propositions 61
3.2.2 Evaluating Propositions 66
3.2.2.1 Conjunction (AND) 67
3.2.2.2 Disjunction (OR) 68
3.2.2.3 Implication (IMPLIES) 69
3.2.2.4 Equivalence () 71
3.2.2.5 Logical Negation (NOT) 71
3.2.2.6 Compound Propositions 72
3.2.2.7 Logical Equivalence 76
3.2.2.8 Tautologies and Contradictions 76
Contents vii
3.3 APPLICATIONS OF PROPOSITIONAL LOGIC 78
3.3.1 Search Queries 78
3.3.1.1 Conjunction in Search Queries 79
3.3.1.2 Disjunction in Search Queries 79
3.3.1.3 Negation in Search Queries 80
3.3.2 Digital Logic 80
3.3.3 Image Compositing 82
3.3.4 Database Queries 84
3.3.5 Software Requirements 87
TERMINOLOGY 89
EXERCISES 90
Chapter 4 Solving Problems 93
4.1 PROBLEM DEFINITION 94
4.2 LOGICAL REASONING 99
4.3 DECOMPOSITION: SOFTWARE DESIGN 104
4.4 DECOMPOSITION: OTHER USES 112
4.5 ABSTRACTION: CLASS DIAGRAMS 114
4.6 ABSTRACTION: USE CASE DIAGRAMS 119
4.7 SUMMARY 123
4.8 WHEN WILL YOU EVER USE THIS STUFF? 123
REFERENCES 124
TERMINOLOGY 124
EXERCISES 125
Chapter 5 Algorithmic Thinking 129
5.1 ALGORITHMS 130
5.2 SOFTWARE AND PROGRAMMING LANGUAGES 132
5.3 ACTIONS 133
5.3.1 Name Binding 133
5.3.1.1 Proper Naming 135
5.3.1.2 State 137
viii Contents
5.3.2 Selection 139
5.3.2.1 One-Way Selection 139
5.3.2.2 Two-Way Selection 142
5.3.2.3 Multiway Selection 144
5.3.3 Repetition 147
5.3.3.1 Infinite Loops 152
5.3.4 Modularization 153
5.3.4.1 Module Flexibility 156
TERMINOLOGY 159
EXERCISES 159
Chapter 6 Modeling Solutions 163
6.1 ACTIVITY DIAGRAMS 164
6.2 SELECTION IN ACTIVITY DIAGRAMS 166
6.3 REPETITION IN ACTIVITY DIAGRAMS 170
6.4 CONTROL ABSTRACTION IN ACTIVITY DIAGRAMS 173
6.5 STATES AND STATE DIAGRAMS 173
6.6 INCLUDING BEHAVIOR IN STATE DIAGRAMS 176
6.7 PROVIDING MORE DETAIL IN STATE DIAGRAMS 180
6.8 SUMMARY 183
6.9 WHEN WILL I EVER USE THIS STUFF? 183
TERMINOLOGY 184
EXERCISES 184
Chapter 7 Data Organization 189
7.1 NAMES 190
7.2 LISTS 193
7.2.1 Arrays 195
7.2.1.1 Storage 195
7.2.1.2 Accessing Array Elements 197
7.2.1.3 Deleting Array Elements 197
7.2.1.4 Inserting Array Elements 199
7.2.1.5 Array Summary 200
Contents ix
7.2.2 Linking 200
7.2.2.1 Storage 200
7.2.2.2 Accessing Linked List Elements 203
7.2.2.3 Deleting Linked List Elements 204
7.2.2.4 Inserting Linked List Elements 204
7.2.2.5 Linked List Summary 205
7.3 GRAPHS 206
7.3.1 Terminology and Properties 208
7.3.2 Storage 210
7.4 HIERARCHIES 211
7.4.1 Organizational Chart 211
7.4.2 Family Tree 212
7.4.3 Biology 213
7.4.4 Linguistics 214
7.4.5 Trees 215
REFERENCES 216
TERMINOLOGY 216
EXERCISES 217
Chapter 8 Algorithmic Thinking 221
8.1 VON NEUMANN ARCHITECTURE 222
8.2 SPREADSHEETS 223
8.2.1 Spreadsheet Structure 223
8.2.2 Formulas/Expressions 224
8.2.2.1 Numbers 224
8.2.2.2 Operators 225
8.2.2.3 Cell References 232
8.2.2.4 Functions 234
8.3 TEXT PROCESSING 237
8.3.1 String Basics 237
8.3.2 String Operations 238
8.3.2.1 Indexing 238
8.3.2.2 Length 239
x Contents
8.3.2.3 Concatenation 239
8.3.2.4 Naming 240
8.3.2.5 Substring 241
8.3.2.6 Searching 241
8.3.2.7 Case Study: Processing e-Mail Addresses 242
8.3.2.8 Case Study: Processing Dates 244
8.4 PATTERNS 245
8.4.1 How to Write a Pattern 246
8.4.1.1 Case Study: Hugs and Kisses Pattern 246
8.4.1.2 Case Study: MPAA Rating Pattern 247
8.4.1.3 Case Study: Social Security Numbers 248
8.4.2 Repetition Rules 248
8.4.3 Character Class Rules 250
8.4.4 Case Study: DNA Sequencing 251
8.4.5 Case Study: Web Searches and Enron Legal
Documents 253
REFERENCE 256
TERMINOLOGY 256
EXERCISES 257
Chapter 9 Lets Get It Correct 263
9.1 COMPUTER ERRORS USUALLY ARENT 264
9.2 SOFTWARE CORRECTNESS 267
9.3 VERIFICATION 269
9.4 SOFTWARE TESTING 272
9.5 WHITE BOX TESTING 275
9.6 BLACK BOX TESTING WITH EQUIVALENCE
PARTITIONING 279
9.7 BOUNDARY VALUE ANALYSIS 283
9.8 WHEN WILL YOU EVER USE THIS STUFF? 286
REFERENCE 287
TERMINOLOGY 287
EXERCISES 288
Contents xi
Chapter 10 Limits of Computation 291
10.1 HOW IS CAPACITY MEASURED IN COMPUTERS? 294
10.2 AN ESTIMATE OF THE PHYSICAL LIMITATIONS 296
10.3 BENCHMARKS 297
10.4 COUNTING THE PERFORMANCE 299
10.5 IMPRACTICAL ALGORITHMS 305
10.6 IMPOSSIBLE ALGORITHMS 310
10.7 METAPHYSICAL LIMITATIONS 313
10.8 WHEN WILL YOU EVER USE THIS STUFF? 316
REFERENCES 316
TERMINOLOGY 317
EXERCISES 317
Chapter 11 Concurrent Activity 321
11.1 PARALLELISM OR CONCURRENCY? 322
11.2 SCHEDULING 324
11.3 SORTING NETWORKS 327
11.4 MEASURING CONCURRENCYS EFFECT 330
11.5 CHALLENGES OF CONCURRENCY 332
11.6 WHEN WILL YOU EVER USE THIS STUFF? 339
REFERENCES 340
TERMINOLOGY 340
EXERCISES 341
Chapter 12 nformation Security 343
12.1 WHAT IS SECURITY? 344
12.2 FOUNDATIONS 347
12.3 COMMON FORMS OF CYBERCRIME 350
12.4 HOW TO SECURE? STEP 1: AUTHENTICATE 353
12.5 HOW TO SECURE? STEP 2: AUTHORIZATION 356
12.6 ALL A MATTER OF RISK 358
xii Contents
12.7 A FEW GOOD IDEAS 359
12.7.1 Encryption 359
12.7.2 Firewalls (Including Spam Filters) 365
12.7.3 Antivirus Software 367
12.7.4 Software Update 368
12.7.5 Backups 369
12.7.6 Log Files 370
12.8 GOOD STRATEGIES 370
12.8.1 Secure the Weakest Link 370
12.8.2 Reduce the Attack Surface 371
12.8.3 Defend Deeply 372
12.8.4 Compartmentalize 373
12.8.5 Trust Reluctantly 374
12.8.6 Use Open Software 375
12.9 WHEN WILL YOU EVER USE THIS STUFF? 375
REFERENCE 376
TERMINOLOGY 376
EXERCISES 377
INDEX, 381
xiii
Preface
Computational thinking is a fundamental skill for everybody, not
just for computer scientists. To reading, writing, and arithmetic, we
should add computational thinking to every childs analytic ability.
JEANNETTE WING*
Traditionally, general education courses in computer science have been
rooted in some combination of four topics: (1) computer programming,
(2) computer hardware, (3) societal issues of computing, and (4) computer
application skills. Computational thinking is different because the focus
goes beyond introductory knowledge of computing to treat computer science as an independent body of thought that is an essential part of what it
means to be educated today. Thinking algorithmically is uniquely important just as is scientific investigation, artistic creativity, or proof theory
in mathematics; and yet computational thinking is a distinct form of
thought, separate from these other academic disciplines. The diagrammatic techniques used in software engineering analysis are effective for
such efforts as strategic planning. The way that data is digitized has a profound impact on todays graphical art and music. Computer science modeling techniques are essential in many aspects of todays research in the
social sciences and business. Pattern-matching techniques are useful in
even the most rudimentary forms of DNA analysis. Understanding things
such as how to express software requirements and the limits of computing
are essential for all people who expect to live and work in a world where
information is stored, accessed, and manipulated via computer software.
This book adheres to the concept of computational thinking. Since
content such as this is typically taught in more advanced computer
* Dr. Jeannette Wing is assistant director, Computer and Information Science and Engineering
Directorate, National Science Foundation and former dean of the School of Computer Science at
Carnegie Mellon University.
xiv Preface
science courses, special attention is paid to the use of effective examples and analogies. In addition, every effort is made to demonstrate the
ways that these concepts are applicable in other fields of endeavor and
to keep this material both accessible and relevant to noncomputer science majors.
The primary topical threads of this presentation can be grouped into
foundational computer science concepts and engineering topics. The
foundational computer science threads include abstraction, algorithms,
logic, graph theory, social issues of software, and numeric modeling. The
engineering threads include execution control, problem-solving strategies, testing, and data encoding and organizing. Rather than organize
all chapters around these threads, a more logically connected approach is
employed. So, for example, algorithmic thinking is integral to at least six
different chapters as a part of problem solving, control structures, modeling, correctness, limits of computation, and concurrency.
It is expected that anyone teaching a computational thinking course
will include some instruction in computer programming. However, there
are many suitable programming languages and various depths of coverage
that might be appropriate. Therefore, this book does not include computer
programming instruction per se. However, the fundamental concepts of
programmingvariables and assignment, sequential execution, selection, repetition, control abstraction, data organization, and even concurrencyare presented. Particular care has been given to present algorithms
using language-independent notation.
This approach has been taught, using early manuscript versions of this
book, for several semesters to university students. Reactions have been
largely positive from both the students and the several faculty involved.
xv
Authors
David Riley has been committed to computer science education for more
than 35 years. He has authored eight other computer science textbooks,
along with numerous book chapters and research papers. His interest in
computational thinking spans countless experiences teaching computer
science majors and graduate students, as well as nonmajors, and even
a year as a high school teacher. He has taught a full array of computer
science courses. Jeannette Wings seminal paper, titled Computational
Thinking, and Wings subsequent discussions at the University of
WisconsinLa Crosse caused Riley to reconsider the priorities of a
computing-related education, especially as they pertain to students outside the computer science mainstream. For the past three years he has
taught several sections of computational thinking to students not intending to study any other computer science. This book is based upon these
experiences.
Kenny Hunt has more than 25 years of experience in the fields of computer science and engineering. His technical expertise spans a broad array
of the computational spectrum: from the design of research satellite electronics to the development of large-scale cloud-based web applications. He
has authored numerous research articles and published a text on image
processing. He has taught computer science and software engineering to
both graduate and undergraduate students for more than 15 years and is
greatly intrigued by the educational benefits of computational thinking.

1
Chapter 1
What Is Computational
Thinking?
Computational ThinkingIt represents a universally applicable attitude and skill set everyone, not just computer scientists, should be
eager to learn and use.
JEANNETTE WING
Is there any human invention that has changed the world more than the
computer? Certainly this is a question worthy of discussion. We live in
a time when not owning a computer puts a person at a disadvantage in
countless ways. Apart from desktop computers, laptop computers, and
tablet computers, many other of todays devices rely upon embedded
OBJECTIVES
To provide a working definition for the concept of computational thinking
To introduce the distinction between analog and digital representations
of data
To examine the origins of mechanical calculation using the abacus as
an example to represent, store, and process data
To examine key historical events that contributed to the invention of
modern computing hardware and software
To explain the stored program concept and the role it plays in software execution and the manipulation of data
To introduce the basic components and characteristics of a modern
computer
To explain Moores law and its impact
2 Computational Thinking for the Modern Problem Solver
computers. Traction control, antilock brakes, computer-assisted parking,
and even car repair all involve computers on board automobiles. Digital
cameras are little more than a computer with a lens attached and most cell
phones are really just handheld computers.
1.1 COMPUTERS, COMPUTERS EVERYWHERE
Computers impact nearly every aspect of life. Among the first occupations
to rely upon computers were accounting and engineering, utilizing the
speed and accuracy of computers for complex calculations. Later, writers, scholars, and journalists began to rely upon word processing for efficient ways to create and modify documents. Clearly, graphic artists and
motion picture animators depend heavily upon computers. Consider the
glass of milk you drank for breakfast. This milk most likely originated
with genetically engineered crops fed to cows in rations determined by a
computer chip around the cows neck, while a computer-controlled robot
milked the cows, and there were myriad computers involved with transporting, processing, and retailing the milk before you brought it home to
your computer-controlled refrigerator.
Today, our finances are computer managed, our wars are fought
increasingly by computer-controlled devices, and we frequently communicate with our friends through computer-reliant social networks.
Unfortunately, even the fastest growing form of criminal activity is categorized as computer crime.
The point is that you really dont have any choice about the limitless
impact computing has on your life. The only choice is how to respond; you
can choose to educate yourself about computers and learn to use them to
your advantage, or you can choose the path of the luddite. (The word luddite was included in the English language not so long ago, specifically to
label the person who is technology ignorant.)
1.2 COMPUTER, COMPUTER SCIENCE, AND
COMPUTATIONAL THINKING
We use the terms computer or computer system to refer to a collection of
computer hardware and software.*
Computer hardware includes all of
the physical devices that collectively constitute the item we think of as a
* Technically, it is more precise to use the term computer system to refer to hardware plus software,
and restrict the meaning of computer to hardware only. However, since computer hardware is of
little value without software, it is now common to use the term computer to mean either hardware only or hardware plus software.
What Is Computational Thinking? 3
desktop or a laptop computer. Such items as keyboards, LCD, computer
memory, disk drives, CD and DVD drives, mice and track pads, and processors are typical parts of computer hardware.
But the computer hardware of even the most sophisticated of all computers would be of no practical value were it not for computer software.
The term software refers to any group of computer programs. Perhaps the
most important difference between a computer and other machines is the
computers ability to respond to instructions, and the instructions for performing a certain task are called a program. It is also acceptable to use the
word code in place of software or program.
You have encountered numerous computer programs if you have used
a computer. When you went surfing about the Internet, you were using a
web browser program, such as Chrome or Internet Explorer or Firefox or
Safari. Among the first things people do with a newly purchased computer
is to configure the antivirus software. A computer program running on
your computer might allow you to play music that was downloaded by way
of a computer program running on another computer located somewhere
on the Internet. Computer programs do everything from managing your
bank account to formatting the pages of this book. Whenever you download any app to your cell phone, you have just installed a program.
Whereas most human inventions are designed to perform a specific
task, computers are set apart from other machines because of the variety
of tasks the computer can perform. So long as someone can create the
program, the computer can perform the associated task. Often, these programs are called applications in recognition that the program is simply a
way to apply the computer hardware to a specific purpose.
Not surprisingly, people whose career is creating programs have titles
such as programmer or software developer. Since every program is designed
to satisfy someones requirements, the program is in effect solving a problem. This means that programmers are really a kind of problem solver; and
given the importance of computers in our lives, computer programmers
are arguably the most important of all modern problem solvers.
So how does computer science fit into this discussion of computer hardware and software? It turns out that study of computer science includes all
issues surrounding computers from hardware to software, from the foundational theories of the technology to the end-user applications. Subfields
of computer science such as computer architecture explore the way in
which electrical circuits are designed, whereas software engineering
examines the preferred techniques for analyzing problems, and designing
4 Computational Thinking for the Modern Problem Solver
and implementing programs to solve them. Some subdisciplines of computer science, like graphics, robotics, information security, networking,
and artificial intelligence, study the concepts implied by their names. All
of these computer science topics, and others, play a role in this book.
The preceding discussion has been leading to the central issue of this
book, namely, computational thinking. The best way to characterize computational thinking is as the way that computer scientists think, the manner in which they reason (Figure 1.1).
Of course it is not possible to explore everything that is known to computer science. So we have selected computer science concepts, techniques,
and methods that have the widest utility to those individuals who most
likely will not be computer scientists. In other words, this is written to capture how computer scientists think for the rest of us. Some of the books
topics are necessary simply to be literate in a society that is so dependent
upon computers. Some of the concepts will allow you to more effectively
use computers in your own field. Many of these ideas are borrowed from
more advanced computer science courses. However, it is increasingly the
case that computing concepts are used everywhere. Words like multitasking, downloading, and flash memory illustrate how computer
science jargon has found its way into everyday speech. Discoveries in
many fields would not have been possible without computers. Human
genome sequencing requires the processing of thousands of genes made
from billions of base pairs. Motion pictures rely on computational techniques, such as wire frame models, to create lifelike images of fictional
Computational inking?
FIGURE 1.1 Computational thinking?
What Is Computational Thinking? 5
worlds. Modern medicine is practiced with minimal invasiveness due to
robotics.
The scientific community discovered roughly a decade ago that most
future scientific discovery would require computing knowledge among
the researchers. As a result, new specialties, such as computational biology and computational physics, have become common in institutions of
higher education.
But computational thinking is useful well beyond the scientific community. A computing subfield known as artificial intelligence has led
to significant discoveries in psychology. Many software engineering tools
used in software design have proven to be highly effective as business
management tools. Computer programs have revolutionized how music
is written, and architects use computer imagery to visually walk about
buildings long before they are built. In short, computers allow us to study
things that were previously too small, too large, too distant, too fast, or too
complex. But as every good carpenter knows, you cannot get the most out
of a tool unless you know how to use it.
1.3 FROM ABACUS TO MACHINE
We begin the history leading up to modern computers by considering calculating devices, because an important aspect of computer hardware is
the ability to perform calculations. Certainly, the earliest known calculating device is the abacus. Although it is believed that the abacus was used
in Mesopotamia centuries before, the oldest archaeological evidence of
an abacus dates back to approximately the fifth century BC and the oldest
known written description of an abacus is estimated to have been written
in China in the thirteenth century AD.
There are variations on the basic structure of this device; we shall
examine a version most commonly used in recent years and known as the
Chinese abacus (see Figure 1.2).
The abacus consists of beads strung onto spindles. Each spindle is supported from its ends, as well as through a bar offset from its center. The
number of spindles can differ from one abacus to another. The bar separates the beads into two groups. The key thing to remember while using
an abacus is that every bead should be pushed as far as possible toward
one end of the spindle or the other. In other words, no bead should ever be
positioned to allow more than one bare space (region of exposed spindle)
on each side of the bar.
6 Computational Thinking for the Modern Problem Solver
The beads have values that increase right to left, just like the value of
digits in a decimal number or a Roman numeral have increasing value
from right to left. The rightmost spindle of beads below the bar are called
the 1s beads because each has a value of 1, while the beads of the rightmost
spindle above the bar are the 5s beads. For the second spindle from the
right below the bar are 10s beads and above the bar are 50s beads. The
third bar from the right has 100s beads below and 500s beads above, and
so forth.
Only the beads pushed as close as possible to the bar contribute to the
value. This means that to make the abacus represent the value 4 you should
push four 1s beads against the bar and all other beads away from the bar.
Figure 1.3 illustrates both the value 4 and the value 2,639 as they could be
represented on an abacus.
Different kinds of abacus may have different numbers of beads on each
spindle, but the Chinese abacus always has two beads above the bar and
five below. This configuration allows the abacus to represent most numbers in multiple ways. For example, Figure 1.4 shows three different ways
to represent the number 10.
Beads above
the bar
Beads below
the bar
e bar
Spindles
FIGURE 1.2 The Chinese abacus.
Value: 4 Value: 2,639
FIGURE 1.3 Two abacus configurations and their values.
What Is Computational Thinking? 7
Modern computers borrow four concepts from the abacus:
1. Storage
2. Representation
3. Calculation
4. User interface
For any valid bead configuration we can think of the abacus as storing the associated numeric value. So long as the beads are not moved, the
abacus retains this same numeric value. A significant aspect of a modern
computer is its storage. Of course, your computer can store much more
than a single number, and it does not use beads, but both the abacus and
your computer are definitely capable of storage.
If there is storage, then there must be something to store. The items that
are stored are commonly referred to as data. An abacus can only store a
single datum at any point in time, while your laptop can store trillions of
pieces of data.
The second concept your computer borrows from the abacus is the
notion of representation. A representation occurs anytime the data from
one system is intended to model something else (the information being
represented). The abacus stores (represents) an integer, using beads on a
spindle to do so. The location of beads can be translated into a numeric
FIGURE 1.4 Three ways to represent 10 with a Chinese abacus.
8 Computational Thinking for the Modern Problem Solver
valuethe value that is represented. A modern computer is designed to
solve problems that involve real-world information. That information is
represented as data within computers using various technologies, many
of them electronic. The electronic signals inside your computers memory
can be translated into the information that they represent. We will discuss
just how computers represent information in more detail in Chapter 2.
The third property of a computer also present in an abacus is the ability to perform calculations. Truthfully, neither the abacus nor computer
hardware alone can perform calculations. In the case of the abacus something (usually a human) must push the beads around. Addition and subtraction are possible by adding or removing beads next to the bar. As
mentioned before, computer hardware also requires something, namely,
software, in order to perform calculations. Just like humans can cause an
abacus to perform arithmetic, software can cause computers to perform
computations.
As a final similarity to modern computers, the abacus illustrates the
first known user interface for a calculating device. The term user interface
refers to the way that humans communicate with the machine. In the case
of the abacus the user interface consists of the use of fingers and thumbs to
slide beads mounted on spindles and to visually interpret the represented
value by the location of beads. The user interface on your laptop computer
is much more sophisticated, using a keyboard and a trackpad together
with some kind of liquid crystal display (LCD). We say that you use a
graphical user interface (GUI) because most computer interaction involves
the manipulation of graphical images, such as icons, buttons, sliders, popup windows, and pull-down menus.
The abacus may exhibit some concepts still in use by todays computers,
but no one would use the word computer to describe an abacus. The abacus does not have enough storage, is designed to represent only integers, is
limited in the kind of calculations it can perform, and has a rather crude
user interface.
The importance of improving the calculation capabilities of human
inventions was evident for many centuries after the abacus. One example
device of note was Napiers bones invented by a Scottish mathematician
named John Napier and published in 1617. Napiers bones consist of small
rectangular sticks with numbers and lines on each stick. Different sticks
have numbers positioned in cleverly different ways (Figure 1.5). Arranging
the sticks in different ways makes it convenient to perform multiplication,
division, and even calculating square roots.
What Is Computational Thinking? 9
The next step toward computer hardware improved both the speed of
calculation and user interface, while bringing human invention into the
category of something that could validly be called a machine. Actually,
there were a few inventions that occurred in history during roughly the
same time. These first calculating machines were invented by mathematicians and from various countries in Europe. Perhaps the two most
significant of the earliest mechanical calculators were Pascaline, invented
in 1643 by Frenchman Blaise Pascal, and Leibniz calculator invented by
the German mathematician and philosopher Gottfried Leibniz around
1674. Figure 1.6 and Figure 1.7 show photos of these machines.
Pascaline and the Leibniz calculator advanced the user interface by
permitting the user to turn cranks and thumb wheels. These devices also
did a better job of assisting humans through the use of internal wheels,
gears, and levers that accomplished addition, subtraction, multiplication, or division. These machines also demonstrate the importance of
speed when performing calculations. Presumably, a knowledgeable user
could perform lengthy calculations more rapidly using these machines
rather than an abacus or Napiers bones. These were early devices that
already illustrated mans conquest of finding machines capable of accelerating calculations.
FIGURE 1.5 Napiers bones.
10 Computational Thinking for the Modern Problem Solver
FIGURE 1.6 Pascaline.
FIGURE 1.7 Leibniz calculator.
What Is Computational Thinking? 11
Not every historical calculating device was used to perform arithmetic.
The device that is the first known example of using gears for calculation
is the Antikythera mechanism (Figure 1.8). Dated to the first century BC,
this machine contained at least 30 interconnected brass gears of various
dimensions. It is believed that positioning a crank on the Antikythera
mechanism caused the device to accurately identify the location of the
sun, moon, and planets.
The Antikythera mechanism has been called a computer by some people. However, it is probably more accurate to think of it as a special purpose calculator, somewhat related to time-keeping machines. Remarkably,
fifteen to sixteen centuries would pass before the gearing technology of
the Antikythera mechanism would reappear in the watch-making industry and early calculators, such as Pascaline.
1.4 THE FIRST SOFTWARE
None of the devices described in Section 1.3 were truly programmable.
Yes, it is possible to rearrange beads, relocate bones, or turn wheels and
cranks, but these are merely ways to configure devices to perform calculations. In order to perform a different calculation any prior configuration is
lost. A truly programmable device is one in which the program is divorced
from the hardware so that it can be stored for reuse at a different time. In
other words the program instructs the device in how to perform, and
different programs produce different results.
FIGURE 1.8 Fragment of Antikythera mechanism.
12 Computational Thinking for the Modern Problem Solver
The first known programmable machine is not a calculator; it is a loom
for weaving cloth. Around 1805, a French inventor named Joseph-Marie
Jacquard built the first known programmable machine. The Jacquard
loom (Figure 1.9) was similar to other looms of the day except that it used
a loop of stiff paper cards as a program. The cards had holes punched in
them. Changing the number and placement of holes in these cards would
cause the loom to weave a different pattern. The loom was built so that the
loop and cards could be removed and replaced by a different loop of cards;
thereby programming the loom to weave different patterns. This kind of
punch card program is still used on textile looms today.
Although punched cards might represent programmability, weaving
on a loom is quite different from computer-like calculations. The first
example of what might be termed computer software (or at least calculator software) did not occur until approximately 1843. This important
event in history came from an English mathematician and inventor named
FIGURE 1.9 Model of a Jacquard loom.
What Is Computational Thinking? 13
Charles Babbage. Babbage had already built a mechanical calculator capable of more advanced logarithmic and trigonometric calculations, but he
did not add the notion of programmability until the design of his second,
and more significant, inventionthe Analytical Engine (Figure 1.10).
The Analytical Engine adopted the concept of punched cards to store
and input a program into the hardware. But programs for the Analytical
Engine were capable of performing a sequence of mathematical operations
in the same way that modern computers can perform complex mathematical operations as directed by a proper computer program. Sadly, because
of the complexity of the device, the manufacturing capabilities of the day
made it impossible to construct a complete Analytical Engine during
Babbages lifetime.
An interesting side note in history often told about the Analytical
Engine involves a woman named Ada Lovelace (Figure 1.11). The Countess
Lovelace was the daughter of the famous poet, Lord Byron. She was quite
interested in the work of Charles Babbage and is known to have written
programs for the Analytical Engine. Some people have called Ada Lovelace
the first programmer, but this cannot be confirmed and is most likely not
true, since several individuals (Babbage included) wrote programs at about
the same time. Nonetheless she is clearly among the first programmers.
FIGURE 1.10 A piece of the Analytical Engine.
14 Computational Thinking for the Modern Problem Solver
1.5 WHAT MAKES IT A MODERN COMPUTER?
One widely accepted definition of modern computer requires three properties of this calculating device:
1. It must be electronic and not exclusively mechanical.
2. It must be digital and not analog.
3. It must employ the stored program concept.
As it happens, even the Analytical Engine invented by Babbage fails to
satisfy every one of these three requirements.
To find the first invention that is believed to satisfy at least one of these
three properties, we skip to the 1890s. The United States has a long history of taking census every ten years. In 1880 the census was tabulated,
like every decade prior, by hand. This process of counting citizenry and
categorizing them by geographic region was becoming difficult because
of rapid population growth. In fact the 1880 census was barely completed
before 1890 when the next census was to begin.
A man named Herman Hollerith invented a calculating device built
specifically for tabulating the US census. Holleriths machine completed
the 1890 census in less than one year. More important for computing,
Holleriths machine ran on electricity. The Hollerith tabulating machine
can fairly be labeled as the first calculating (i.e., computer-like) hardware
that satisfies any of the properties that distinguish a modern computer.
FIGURE 1.11 Charles Babbage and Ada Lovelace were among the first computer
programmers.
What Is Computational Thinking? 15
Hollerith later founded a Tabulating Machine Company to build these
devices, and his company merged to form IBM Corporation in 1924; IBM
remains today as one of the worlds largest manufacturers of computers.
Holleriths tabulating machine also provides convincing evidence of the
future capacity of computers to assist in solving human problems.
Before revealing the candidates for the first modern computer, there
are two of the preceding properties of a modern computer that have yet to
be mentioned. The first issue is that a modern computer must be digital.
Prior to the 1930s, machines that stored data typically did so as represented using mechanical gears or electrical signals. Gears can generally be
rotated to an infinite number of different angles. Similarly, electrical signals are infinitely variable in terms of voltage, amperage, capacitance, and
inductance. This kind of continuous change is called analog. For example,
an analog wristwatch often has a sweep second hand and can position the
minute hand at an infinite number of positions around the dial.
A digital system, unlike analog systems, is one in which there are not
an infinite number of possibilities and change is not continuous. Instead,
digital systems restrict values to be one of a few choices. For example,
hours and minutes on a digital watch are displayed as numbers. It is not
possible for the minute number to display anything between 9:30 and 9:31.
Most of our automobile speedometers are analog with a needle that rotates
gradually as the car accelerates. However, a few cars have digital speedometers that display the current speed as a single number in either whole
miles or meters per hour.
An explanation of the stored program concept requires a brief look at
the major units of hardware in a modern computer. Figure 1.12 diagrams a
simple desktop-style computer with three components: a keyboard, a display, and a system unit. These three components can be used to illustrate
FIGURE 1.12 The basic parts of a simple desktop computer.
16 Computational Thinking for the Modern Problem Solver
the four essential parts of a computer. Every modern computer must have
at least one of each of the following:
1. Input device
2. Output device
3. Memory
4. Processor
An input device, as its names implies, provides a way to get data into
the computer. The input device shown in Figure 1.12 is a keyboard. Other
kinds of input devices include computer mice, track pads, and microphones. Smartphones and tablet computers use the surface of the LCD as
an input device.
Output devices provide ways for the computer to share the results of
its computation with the user. On personal computers the most common
output device is the computer display. Other output devices include printers and speakers. Together, input devices and output devices provide the
computer hardware that supports the user interface.
Some devices are connected to computers in order to support both
input and output. For example, the data (i.e., the images) for viewing
your favorite motion picture may be input to your computer from a DVD
player/recorder, but that same DVD device can be used for output when
you archive the photo collection on your computer. The term I/O, pronounced eye oh, is commonly used by computer scientists to refer to the
combination of input and output. Disk drives, flash memory cards, CD
units, and DVD units are all examples of I/O devices.
Data that is input needs to be stored. Such storage occurs within the
system unit in a component known as memory. Unlike human memory,
the memory chips inside a computer almost never fail to correctly store
and retrieve data. Chapter 2 explores more about how computer memories
are measured and how they store data in digital form.
Youve typed in your user name and password, and the computer has
stored these data somewhere in its memory. One more thing needs to happen in order for the computer to be of any valuethe computer must process your input. So a processor is the fourth essential part of a computer.
Like the mechanical calculators from the seventeenth century, computer
processors can perform numeric calculations; but the range of potential
computer calculations clearly goes far beyond these early machines. In
What Is Computational Thinking? 17
addition, todays computer processors typically perform trillions of operations per second.
Computer memory and computer processors are less visible than I/O
devices. Generally, memory and processors consist of small integrated circuits approximately 1 cm2. Both memory and processor are located within
the system unit box of Figure 1.12. However, the fact that integrated circuits are so small also makes it possible to locate them more compactly.
For example, the memory and processor(s) of a laptop are positioned in
the same box just underneath the keyboard. Some desktop computers
place the processor(s) and memory inside the same case as the display.
Tablet computers and smartphones package all four componentsinput
device, output device, memory, and processor(s)in a single case.
You know that computer data is stored in the computers memory
and is manipulated by the computers processor, but how is the processor instructed regarding the particular calculations to perform? In other
words, how does computer software (the program and the instructions)
work together with the computer hardware components? The answer is that
computer processors respond to particular instructions, known as machine
instructions. Different processors respond to different machine instructions, just like different human cultures use different natural languages.
Input devices can supply the instructions to the computer. A user who
knows the instructions could input them via the keyboard, or the software
could be downloaded (input) from the Internet. The program will not be
available to the processor until it has been loaded (moved) into computer
memory. This is known as the stored program conceptthe third, and last,
requirement of a modern computer. The point is that computer memories today are used for two things: (1) they store data, and (2) they store
the instructions that process that data. The stored program concept also
requires circuitry for the computer to transfer instructions from memory
to the processor so that they can be executed. Typically, the processor
not only executes the instructions but also controls their retrieval from
memory.
1.6 THE FIRST MODERN COMPUTER
Section 1.5 defines a modern computer to be a calculating machine that is
(1) electronic, (2) digital, and (3) employs the stored program concept. In
this section we examine why it is not so easy to determine which invention
actually qualifies as the very first modern computer.
18 Computational Thinking for the Modern Problem Solver
The transition from mechanical calculators to electronic computers took place most significantly with machines known as differential
analyzers. Differential analyzers were devices designed to solve differential equations, and mechanical versions of these calculators can be
traced back to the early to mid-1800s. In 1912 a mechanical differential calculator powered by electricity was designed for use in British
naval gunnery. In 1931 Vannevar Bush of the Massachusetts Institute
of Technology published a journal paper describing how to construct
a differential analyzer that was basically an electronic, as opposed to a
largely mechanical, device [1]. However, all of these earlier devices were
not modern computers, because those that used electricity did so with
analog circuitry.
Influenced by these and other work on differential analyzers, two
researchers from the University of PennsylvaniaJohn Mauchly, a physicist, and Peter Eckert, an electrical engineerconducted a project that
completed ENIAC (Electronic Numerical Integrator and Computer) for
the US Army in 1946. In 1947 a patent was filed with the US Patent Office
that declared ENIAC to be the first electronic computer. Figure 1.13 is a
photograph of ENIAC.
FIGURE 1.13 ENIACan early modern computer.
What Is Computational Thinking? 19
Clearly, ENIAC satisfies the earlier criteria for a modern computer. It
was a calculating device that ran on electricity and was digital. The original version of ENIAC did not truly follow the stored program concept, but
this capability was later incorporated. By todays standards ENIAC was
enormous, physically filling an entire room. Its circuitry relied on 19,000
vacuum tubes (see Figure 1.14) and 1,000 relays. Vacuum tubes can be used
as memory devices, but they are large (each roughly the size of a human
thumb) and unreliable relative to todays computer memory. Relays are a
form of electrical switch that are mechanical and also large (about the size
of half a cell phone).
Despite the patent, ENIAC is not considered the first modern computer.
In fact the US Patent Office invalidated the 1947 patent in 1973. The primary reason for this invalidation was the discovery of some earlier work
that was not fully patented.
In 19371938 two physicistsJohn Atanasoff and Chuck Berryat
Iowa State University built a machine they called the ABC Computer (see
Figure 1.15). During the patent dispute, it was discovered that the Des
Moines Register had printed an article regarding the ABC Computer in
1941. It was also claimed that Atanasoff discussed his design with Mauchly
in 1940 and had visited a US Patent Office that same year.
Unfortunately, the ABC Computer may not truly qualify as the first
modern computer, because it failed to use the stored program concept, nor
was it truly programmable for general purposes, as it was only designed to
FIGURE 1.14 Vacuum tubes.
20 Computational Thinking for the Modern Problem Solver
solve systems of linear equations. Still, the ABC Computer is considered
to be first in three important ways:
1. The first fully electronic and programmable calculator
2. The first to incorporate an electronic memory
3. The first to use binary numbers (explained in Chapter 2)
A German engineer, named Konrad Zuse, is sometimes credited with
creating the first general-purpose electronic digital computer. It was called
Z4 and built in 1945. Z4 was also the worlds first commercial digital computer. However, like the ABC Computer, Z4 did not use the stored program concept. Zuse is also well known as the creator of a programming
language, known as Plankakul, that became the forerunner of a family of
programming languages that dominated software development in Europe
for more than two decades.
Perhaps the title of first modern computer belongs to a lesser known
invention: the Manchester Small-Scale Experimental Machine, also known
as SSEM or Baby. SSEM was finished in June 1948 at Victoria University
FIGURE 1.15 ABC Computer.
What Is Computational Thinking? 21
of Manchester, England, and the first computer to use the stored program
concept. However, it was never intended to be a practical computer but
rather part of a test bed for other hardware. By September of the same
year, ENIAC had been modified to use stored programs, making it a contender for first modern computer.
Regardless of which invention should be considered to be most significant, what is clear is that during the late 1930s and throughout the 1940s
there was a flurry of research taking place around the world to create early
computing devices.
Within a few years computer scientists had grown weary of the tedious
activity of using machine instructions, which led to the invention of highlevel programming languages. A high-level language is one that relies
upon instructions that are much more English-like instead of the cryptic numeric form of most machine instructions. The revolution leading to
computer systems like todays changed to more of an evolutionary history
by the mid-1950s, except for one major change to the hardware.
1.7 MOORES LAW
No discussion of todays computer hardware would be complete without
the inclusion of one more discovery. In the 1950s and 1960s several physicists, most notably Jack Kilby and Robert Noyce, were working on a technology that would soon replace the use of vacuum tubes and relays with
smaller, faster, and far more reliable electronics.
The idea was to use silicon wafers that are manufactured in such a way
that thousands, and later trillions, of electronic switches, known as transistors, can be combined onto a single chip. Such devices are referred to
as integrated circuits and the technology that permits silicon to function in
this way is called semiconductor technology.
Figure 1.16 is a photograph of an integrated circuit. The blackened
square region in the center is the silicon wafer with wires (the lines) connecting it to the metal legs on the outside of the device. These legs typically plug into a socket for connection to the remainder of the computer
circuitry. The entire package is commonly referred to as a chip.
Robert Noyce was awarded the Nobel Prize in Physics for his work in
the creation of semiconductors. Together with Gordon Moore, he founded
Intel Corporationthe largest manufacturer of computer processors in the
world.
Integrated circuits make it possible for us to carry computers in a briefcase or a pocket that are millions of times faster than the room-sized
22 Computational Thinking for the Modern Problem Solver
computers of the 1950s and 1960s. Gordon Moore observed this performance trend in a paper he published in 1965 [2]. What has now become
famously known as Moores law was a prediction that manufacturing
capabilities would advance so that the number of components within an
integrated circuit would roughly double every 18 months. Moores law
has been amazingly accurate for over 40 years, explaining why computers have grown so small that they are now embedded in countless devices
from wristwatches to MP3 players.
Doubling over a fixed time is a growth rate, known to mathematicians
and computer scientists as exponential growth. In this case the growth in
an exponent (or power) of 2. Following is a table showing how this exponential growth works for a base of 2:
After 18 months Improvement factor = 21
= 2
After 3 years Improvement factor = 22
= 2 2 = 4
After 4.5 years Improvement factor = 23
= 2 2 2 = 8
After 6 years Improvement factor = 24
= 2 2 2 2 = 16
After 7.5 years Improvement factor = 25
= 2 2 2 2 2 = 32
After 9 years Improvement factor = 26
= 2 2 2 2 2 2 = 64
After 10.5 years Improvement factor = 27
= 2 2 2 2 2 2 2 = 128
After 12 years Improvement factor = 28
= 2 2 2 2 2 2 2 2 = 256
After 13.5 years Improvement factor = 29
= 2 2 2 2 2 2 2 2 2 = 512
After 15 years Improvement factor = 210 = 2 2 2 2 2 2 2 2 2 2 = 1,024
FIGURE 1.16 An integrated circuit.
What Is Computational Thinking? 23
An important side effect of Moores law has been that as more components are squeezed into the same integrated circuit space, electricity
travels a shorter distance. This means that the circuits are faster. This
rapid increase in the speed of our computers, often considered to be a
corollary of Moores law, is taken for granted today. In fact our computers have been doubling in speed roughly every 1.5 years for several
decades. This explains why the computer purchased by a college freshman is roughly eight times less capable than those available four and a
half years later. Moores law can also be used to explain why computers
have increased in speed and capacity by about 1,000 times in the past
decade and a half. Chapter 10 examines a bit more about Moores law
and its implications in the future.
1.8 SUMMARY
The thinking of computer scientists is often dictated by the technologies
they employ. This chapter explores the basic inventions that led to the
computer hardware and software in use today. It is interesting to note that
during the last 50 years arguably the most significant thing to happen with
computers is their ability to solve ever more problems. This increase in
computer application is a direct result of Moores law, resulting in computers that are smaller, faster, and cheaper.
1.9 WHEN WILL YOU EVER USE THIS STUFF?
Two things explain why computers have become so prominent in our
modern world: (1) we have discovered ways to store and manipulate information via computers and (2) we have created extremely fast computers.
Moores law describes the pace of change in computing historya pace
unmatched by other human inventions. No one can pinpoint the future
of human discovery, but based upon history computers are likely to play a
pivotal role in whatever the future brings.
REFERENCES
1. Bush, V. The Differential Analyzer: A New Machine for Solving Differential
Equations. Journal of the Franklin Institute 212, no. 4 (1931): 447488.
2. Moore, Gordon E. Cramming More Components onto Integrated Circuits.
Electronics Magazine, April 19, 1965, vol. 38, no. 8, p. 4.
24 Computational Thinking for the Modern Problem Solver
abacus
ABC Computer
analog
Analytical Engine
Antikythera device
app
application
Attanasoff, John
Babbage, Charles
Berry, Chuck
calculation
chip
code
computational thinking
computer
computer science
computer system
data
differential analyzer
digital
Ekert, Peter
ENIAC
electronic (computer)
exponential growth
graphical user interface (GUI)
hardware
high-level programming
language
Hollerith, Herman
I/O
input
integrated circuit
Jacquard, Joseph-Marie
Jacquard loom
Kilby, Jack
Leibniz, Gottfried
Lovelace, Ada
machine instruction
modern computer
Moore, Gordon
Moores law
Napier, John
Napiers bones
Noyce, Robert
output
Manchester Small-Scale
Experimental Machine
(SSEM)
Mauchly, John
TERMINOLOGY
What Is Computational Thinking? 25
memory
Pascal, Blaise
Pascaline
processor
program
programmable
programmer
punched cards
representation
semiconductor technology
software
software developer
stored program concept
storage
user interface
Z4 Computer
Zuse, Konrad
EXERCISES
1. What are the three qualities required of a calculating device in order
for it to qualify as a modern computer?
2. What is the difference between computer hardware and computer
software?
3. Describe the significance of each of the following inventions, as it
eventually led to the creation of the first modern computer.
a. The abacus
b. The Analytical Engine
c. Jacquard loom
d. Holleriths machine for tabulating the US census
4. Digital cameras are one kind of modern computer. In this sense,
answer the following questions.
a. How does the user supply input to a digital camera?
b. What would you consider to be the cameras output device(s)?
c. What is the purpose of the cameras memory?
26 Computational Thinking for the Modern Problem Solver
5. In what sense might you consider a portable music player to be
programmable?
6. In what ways do the GUI elements of a smartphone or tablet computer typically differ from those of a laptop or desktop computer?
7. Applying Moores law, how much larger would you expect a computer from 30 years ago to be by comparison to the computer you
currently use?
27
Chapter 2
How Real-World Information
Becomes Computable Data
It is a capital mistake to theorize before one has data.
ARTHUR CONAN DOYLE
Since computer programs process real-world information, the first step
of computational problem solving is to encode real-world information as
data that can be processed by a computer. Real-world information comes
from many sources and in a variety of forms. Converting information into
data that a computer can store and understand presents many challenges.
For example, how can an audio recording, or a seventeenth-century Dutch
oil painting or a full-color page from a textbook or even a fingerprint be
stored inside of a computer?
OBJECTIVES
To define the terms information and data
To describe how data is encoded as bit strings within a computing system
To define measures of data capacity and how much capacity is
required to store certain types of real-world information
To describe positional numeral systems
To describe how integer and real numbers can be encoded
To show that computers can be imprecise
To describe how complex information such as text, colors, pictures,
and sound can be encoded as bit strings
28 Computational Thinking for the Modern Problem Solver
This chapter will describe the underlying encoding system used by
most computing systems and will show how complex types of information
such as images and sound can be encoded by using this encoding system.
This chapter will also discuss the techniques for minimizing the encoding
of information such that the data is more compact and efficient.
2.1 INFORMATION AND DATA
The Industrial Revolution was a period of time where extensive changes in
manufacturing and technology brought about equally extensive changes to
the global economic and cultural environment. Starting in the late 1800s,
the economies of Europe and later the United States began to move from a
largely manual and animal-based agricultural system toward a machinebased manufacturing system. Commerce and trade expanded greatly due
to the construction of canals, roads, and especially railways. The revolution was fueled primarily by steam, coal, and by the development of iron
and metal machines for industrial use. Almost every aspect of daily life
was affected as more sophisticated technologies and equipment were used
throughout society.
Recent times have seen another tremendous upheaval in the global economic and cultural environment. The major economies of our time have
shifted from a primarily industrial base toward an economy that is based
on the generation, capture, and analysis of digital information. The resulting social and economic climate is known as the Information Age; a period
of time that is characterized by massive amounts of digital data that are
easily accessible, quickly transmitted, and subject to meaningful analysis.
The transition to an information-based economy and culture was propelled
primarily by advances in electronic computing and networking. Personal
computers gained widespread adoption in the late 1970s and this, coupled
with the rapid development of the Internet in the mid-1990s, served to
bring digital data and digital computation into the cultural mainstream.
The terms information and data are largely overlapping ideas, but in
this book we will make a distinction between them. The Oxford English
Dictionary (OED) defines data as the quantities, characters, or symbols
on which operations are performed by computers and other automatic
equipment, and which may be stored or transmitted in the form of electrical signals, records on magnetic tape or punched cards, etc. The OED also
makes a distinction between information and data when it defines information as knowledge communicated concerning some particular fact,
subject, or event; that of which one is apprised or told; intelligence, news
How Real-World Information Becomes Computable Data 29
and adds that information is that which is obtained by the processing of
data. Throughout this book we will use the term information to denote
a fact or piece of knowledge about the real world, whereas we will use the
term data to denote an encoding of information such that the information can manipulated by a computing system.
Consider the following examples that distinguish between information
and data. Your credit card number is information that is turned into data
when it is stored on the back of your card. The encoding of this information may take the form of a strip of magnetically charged particles, a onedimensional bar code, a two-dimensional bar code, or even as a pattern
of etchings in a radio-frequency identification (RFID) chip. Your name
is also a piece of information that is turned into data when it is stored in
a computing system. The encoding may be electrical charges stored on a
digital circuit or even as a one- or two-dimensional bar code on the back
of an identification badge. The idea that computational thinking is for
everyone is a piece of information that can also be turned into data by
encoding. Figure 2.1, for example, shows a two-dimensional encoding of
this very phrase.
2.2 CONVERTING INFORMATION INTO DATA
One of the challenges of the information age is the transformation of
real-world information into data. How can a painting such as the Mona
Lisa be stored in a computer? How can an orchestral performance by the
London Philharmonic Orchestra be stored on a computer and transmitted
around the globe? How can your voice be recorded as data on a voicemail
FIGURE 2.1 A two-dimensional encoding of the phrase Computational thinking is for everyone.
30 Computational Thinking for the Modern Problem Solver
system or how can your smartphones password be stored as electronic
data within the system?
We first note that there are two different types of data: continuous and
discrete. Data is continuous if there are an infinite number of possible values for an individual datum, whereas data is discrete if there are a finite
number of possible values. Continuous data is usually associated with
measurements involving the physical or real world, whereas discrete data
is usually associated with things that can be counted.
As an example, consider measuring the weight of an orange. Although
the orange could weigh exactly 200 grams, it might also weigh 229.3
grams or 229.31533 grams or even 229.31533480185993 grams. In other
words, the weight of an orange is an example of continuous data since
there are an infinite number of possible values that might describe the
weight of an orange. On the other hand, consider asking your friends
how many biological parents they have who are still living. They may
respond with the numbers 0 or 1 or 2. Since no person has more than 2
biological parents, numbers larger than 2 are not possible and it should
be obvious that it is not possible to have a fractional number of living
parents. The number of living parents is an example of discrete data
since there are only a finite number of values that describe this situation.
In electronics, a signal may be either analog or digital. An analog signal
is an encoding of continuous data, whereas a digital signal is an encoding
of discrete data. In earlier times, electronics were systems that processed
analog signals, but modern computing systems almost exclusively utilize
digital electronics. The reason that digital systems are generally preferred
to analog systems is that there are a finite set of possible values to process
in a digital system.
In digital systems, the smallest unit of data is known as a binary digit, or
bit. At any point in time, a bit can only take on one of two possible values:
ON or OFF. You can think of a bit as an extremely small battery that can
How Real-World Information Becomes Computable Data 31
be very quickly charged or discharged. When charged, the bit is ON and
when discharged, the bit is OFF. Mathematically speaking, a bit is usually
denoted as the value 0 when OFF and the value 1 when ON. Determining
whether a bit is ON or OFF is straightforward. Consider, for example, how
easy it is to determine wither a lightbulb is on or whether an electric fence
is off! Throughout the remainder of this text, we will denote the OFF state
as a 0 and the ON state as a 1.
You might be surprised to discover that computing systems encode all
information as a sequence of bits. Pictures, sound, textbooks, and video
are encoded as long sequences of bits. A sequence of bits is commonly
referred to as a bit string. Since the bits in the string are able to vary in the
values that they hold, some bits being 1 while other bits are 0, a bit string
is able to display a great number of different patterns. For a single bit (i.e.,
a bit string of length one), there are only two patterns that the string could
exhibit at any one point in time. The bit could either be 0 or 1. Consider,
however, a string of two lightbulbs. How many different patterns could
the string exhibit? Two of the patterns are obvious: both lightbulbs could
be 0 or both lightbulbs could be 1. Two other patterns are also possible.
The first lightbulb could be 0 and the second lightbulb could be 1. It is also
possible that the first lightbulb could be 1 and the second lightbulb could
be 0. These four patterns are illustrated in Figure 2.2 where lightbulbs are
used to depict a single bit.
Now consider longer bit strings. How many different patterns can a bit
string of length three exhibit at any one point in time? If the additional bit
is placed as the first bit in the string, it is easy to see that there are twice as
many patterns as before. If the first bit is 0 then there are four patterns that
the remaining bits can exhibit. If the first bit is 1 (the only other possibility
for that bit) there are four patterns that the remaining bits can take on. We
conclude that there are eight patterns that a bit string of length three can
exhibit at any one point in time. This is illustrated in Figure 2.3.
0 0 0 1 1 0 1 1
FIGURE 2.2 The four patterns that a string of two bits can exhibit are 00, 01,
10, and 11.
32 Computational Thinking for the Modern Problem Solver
Every bit that is added to a bit string doubles the number of patterns
that the string can exhibit. This leads us to a very useful generalization to
the question of how many patterns a bit string can exhibit. More specifically, we note that the number of patterns that a bit string of length N can
exhibit is 2N. Figure 2.4 gives insight into this pattern.
Real-world information can then be encoded as data by arbitrarily
associating pieces of information with a particular bit pattern. We might,
for example, associate the color red with the pattern 100, the color green
with the pattern 010, and the color blue with the pattern 001 in a bit string
of length three. As another example, consider encoding all of the symbols on a keyboard; including letters, digits, and punctuation symbols.
We would make a list of every possible keyboard symbol and then begin
to associate each symbol with a unique bit string pattern. We might, for
Length of Bit String Number of Patterns
1 21 = 2
2 22 = 4
3 23 = 8
4 24 = 16
5 25 = 32
8 28 = 256
N 2N
FIGURE 2.4 The number of patterns generated by bit strings.
0 0 0 0 0 1 0 1 0 0 1 1
1 0 0 1 0 1 1 1 0 1 1 1
FIGURE 2.3 There are eight patterns that a string of three bits can exhibit.
How Real-World Information Becomes Computable Data 33
example, associate the letter A with the 8 bit string 01000001 and a period
with the 8 bit string 00101110.
2.3 DATA CAPACITY
Data encoding requires us to know how many bits are required to store a
piece of information. When storing the symbols on a keyboard, for example, we must know how many bits would be required to store any one of
the symbols. Would it be possible to encode a keyboard symbol as a 3 bit
string or a 4 bit string rather than an 8 bit string?
Consider the following scenario. You are given a list of all keyboard
symbols and you are also given a bit string of length three. Your task is
to generate a unique bit pattern for each of the symbols in your list. You
begin with the symbol A and decide to encode this symbol as 000. As
you move through the alphabet, you choose to encode B as 001, C as
010, D as 011, E as 100, F as 101, G as 110, and H as 111. At this
point you realize that there are no patterns left to encode the remaining
symbols of the keyboard and hence a bit string of length three is not sufficient to encode one keyboard symbol.
In general, the number of bits required to store a piece of information
is proportional to the number of values that the information may take.
A single day of the week can be encoded as a bit string of length three
since there are seven days in a week and there are eight patterns available. A single month of the year can be stored in a bit string of length four
since there are 12 months in a year and 16 patterns available. Information
that involves a large set of possible values will therefore require longer bit
strings to encode while information of little content can be encoded in
shorter bit strings. Figure 2.5 illustrates how the number of bits that are
required to encode information of a certain type is related to the number
of values associated with that type.
The data capacity of a computing system is the amount of information that can be encoded by the system. Since the data capacity is directly
related to the number of bits that are available on the system, the data
capacity is simply a count of the number of bits. Data capacity is not usually based on a direct count of the number of bits, but rather is based on
the unit of measure known as a byte. A byte is a bit string of length eight.
A single byte, therefore, is able to store 28
or 256 unique patterns.
One other measure of data capacity is known as a word, which is a unit
of data capacity that is based on the hardware of a computing system. A
word is a fixed-length sequence of bits that are processed as a single item
34 Computational Thinking for the Modern Problem Solver
by the processor. The number of bits in a word varies by computing system but will typically be a multiple of eight. You may have heard of 32 bit
processors or 64 bit systems. These phrases describe the word-length of
a particular computing system. Common word lengths include 8, 16, 32,
and 64.
Prefixes are used as multipliers to measure very large data capacities
and the symbol B is used to denote a single byte. The computing industry
uses terms such as kilobyte, megabyte, and gigabyte, and corresponding
symbols KB, MB, and GB as common measures of data capacity. Figure 2.6
shows the most common prefixes and their meaning as both a power of 2
and an approximate decimal value.
Prex Symbol Power of 2 Decimal
Kilo K 210 ~103
Mega M 220 ~106
Giga G 230 ~109
Tera T 240 ~1012
Peta P 250 ~1015
FIGURE 2.6 Data capacity prefixes.
Type of Information Number of Values Number of Bits
coin toss 2 1
day of week 7 3
month of year 12 4
day of month 31 5
keyboard symbol ~104 7
day of year 365 9
FIGURE 2.5 The approximate number of bits required to store various types of
information.
How Real-World Information Becomes Computable Data 35
Computing systems are used to store vastly different types of information. Digital music players can record, store, and play back vast libraries
of audio recordings. Cell phones can store and display high-quality video
streams, while other systems gather and analyze massive amounts of scientific data for weather prediction or advancing scientific knowledge. The
data capacity required by various types of information varies since the
richness of the information content varies by type. Figure 2.7 shows how
much data capacity is required to store certain types of information.
2.4 DATA TYPES AND DATA ENCODING
We have already asserted that all digital data is encoded as a sequence of
bits and that information is associated with the various patterns that these
bits may exhibit. This section gives further insight into how specific types
of information are encoded and describes some of the inner workings of a
computing system. We begin by discussing how numbers are encoded and
then give a brief overview of how colors, pictures, and sound can be encoded.
2.4.1 Numbers
2.4.1.1 Numeral Systems
A numeral system is a way of representing numbers in written form.
Consider, for example, the three numbers shown in Figure 2.8. If these
markings are interpreted using the numeral system known as tally
Type of Information Data Capacity (Bytes)
keyboard symbol (letter) 1 B
10 page paper 40 KB
five minute MP3 audio recording 5 MB
high resolution digital picture 5 MB
CD audio disk 800 MB
DVD 8.5 GB
all of Wikipedia
* Wikipedia allows users to download the content of the entire web site. At the time of this
writing, the content consisted of approximately 6 TB of data.
6 TB*
FIGURE 2.7 Amount of memory required to store certain types of information.
36 Computational Thinking for the Modern Problem Solver
marking, they correspond to the numbers one, two, and three. Under tally
marking, a number is represented by making one tally mark for each unit
in the number. You may have used tally marking when keeping score in a
game of tic-tac-toe or when counting the number of days you have spent
in jail.
If these markings are interpreted using the Roman numeral system, they
also correspond to the numbers one, two, and three. While the Roman
numeral system has well-defined rules for representing integer numbers,
the system is not widely used today because it is difficult to understand all
of the rules and to decode larger numbers.
If these markings are interpreted using the decimal numeral system,
they correspond to the numbers one, eleven, and one hundred and eleven.
While the rules of the Roman numeral system are rather complicated, the
rules of the decimal numbering system are simple enough to easily decode
even large numbers. The decimal numeral system is a base 10 positional
numbering system.
If the markings of Figure 2.8 are interpreted using the binary numeral
system, they correspond to the numbers one, three, and seven. The binary
system is very similar to decimal in that it is a positional numbering system such that any integer number is given by a sequence of digits where
the position of each digit denotes a power of 2 and the value represents a
multiplier. The only real difference between decimal and binary is that
while decimal is a base ten numbering scheme, binary is a base two numbering scheme.
Of course these different numeral systems begin to look different
once the numbers become larger. Figure 2.9 shows how the number five
FIGURE 2.9 Four representations of the number five.
FIGURE 2.8 Three numbers.
How Real-World Information Becomes Computable Data 37
is represented in each of these four numeral systems: tally marking, the
Roman numeral system, the decimal system, and the binary system.
In the tally marking system, all tally marks carry the same meaning: a
value of one. The number represented by a particular tally is simply the sum of
all the tally marks. In positional numbering systems, however, the digits of a
number carry a meaning that is dependent upon where the digit is positioned
within the number. Take the decimal number 323 for example. In this number, the first digit means three hundreds and the last digit means three ones.
2.4.1.2 Positional Numeral System
A positional numeral system must first specify a base, also known as the
radix, that describes how many digits exist in that particular system. In
the decimal numeral system, for example, the base is 10 since it uses the
10 digits 0 through 9. The smallest digit of a positional numeral system
is always zero while the largest digit is always one less than the base. The
decimal system is the most common system used by people, perhaps since
we each have ten fingers that can be used to reason about numbers! But
while the decimal system is the most commonly used system for human
beings, the binary numeral system is the most commonly used in computing. The binary numeral system, as the name implies, uses only two digits.
Digital electronics are well suited for binary systems since digital circuitry
can be readily designed around numbers composed of only two digits. The
standard positional numeral systems differ from one another only in the
base they use.
Any positive integer greater than one can be used as a base in a positional numeral system. Since there are an infinite number of bases there
are an infinite number of positional systems. Nonetheless, there are only
a handful of commonly used numbering systems and these are listed in
Figure 2.10. Notice that for numeral systems having a base greater than
10, the symbols used for digits will include glyphs other than those of the
Name Base Digits
Binary 2 0,1
Octal 8 0,1,2,3,4,5,6,7
Decimal 10 0,1,2,3,4,5,6,7,8,9
Hexadecimal 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
FIGURE 2.10 Common positional numbering systems.
38 Computational Thinking for the Modern Problem Solver
decimal system. As an example consider the hexadecimal system, which
uses the symbol A to denote the value 10, the symbol B to denote the value
11, and onward through F to denote the value 15.
In a positional number system, a value is represented by a sequence of
digits where the position of each digit in the sequence is associated with an
integral power of the base and the digit is a multiplier for that base term.
The position of each digit is numbered starting from zero on the right and
increasing as the digits move right to left. The right-most digit is therefore
always at position 0, the next digit moving left is at position 1 and so forth.
Consider the example of Figure 2.11 that shows how to interpret the
decimal number 925. For this number we see that the digit 5 is at position
0, the digit 2 is at position 1 and the digit 9 is at position 2. The radix is
assumed to be 10 and hence the positional terms will be integral powers
of 10. We then understand that the digit 5 is a multiplier for 100, the digit
2 is a multiplier for the 101
, and the digit 9 is a multiplier for 102. In other
words, the number 925 is understood as (9 102
) + (2 101
) + (5 100
) and
since any positive integer that is raised to the 0th power is equal to 1 this
reduces to (9 100) + (2 10) + (5 1).
The most common powers of ten have names that allow us to more easily describe decimal numbers. These names are shown in Figure 2.12. Note
Number 9 2 5 Base 10
Position 2 1 0
Power of Base 102 101 100
Meaning 9102 + 2101 + 5100
FIGURE 2.11 Example of using the decimal numeral system.
Name Value
Ten 101
Hundred 102
ousand 103
Million 106
Billion 109
Trillion 1012
Googol 10100
FIGURE 2.12 Common names given to various powers of 10.
How Real-World Information Becomes Computable Data 39
that a googol corresponds to the 100th power of 10 and is the namesake for
the Internet search engine powered by Google.
People almost always use the decimal numbering system when writing
numbers and therefore usually assume that the base is 10. In situations
where the radix may not be clear, however, it is useful to express the base
by using a subscript notation. For example, the subscript in 10110 indicates
that the number is expressed in the decimal system, whereas 10116 is a
number that is expressed using a base of 16 and 1012 is a number that is
expressed in binary. Be careful to note that these numbers are not different ways of writing the same number but are different numbers! Because
computational thinkers often use numbers that are represented in different base systems, we will use subscript notation to make the radix clear.
Whenever we write a number without a subscript we assume that it is
expressed in the decimal numeral system.
Consider, for example, the two numbers 10110 and 1012 as shown in
Figures 2.13 and 2.14, respectively. The number 10110 has the value one
hundred and one while the binary number 1012 does not.
Since the radix is 2 we understand this to mean (1 22
) + (0 21
) +
(1 20
) which is equal, in the decimal system, to 4 + 0 + 1, or 5.
2.4.1.3 Integers as Binary Bit Strings
Computing systems represent integer numbers as binary bit strings. The
binary system is a fitting choice for computers because there are only two
values in the binary system and hence a single bit has sufficient data capacity to store a single binary digit. If we assume that the patterns of the bit
Number 1 0 1 Base 10
Position 2 1 0
Power of Base 102 101 100
Meaning 1102 + 0101 + 1100
FIGURE 2.13 Interpretation of 10110.
Number 1 0 1 Base 2
Position 2 1 0
Power of Base 22 21 20
Meaning 122 + 021 + 120
FIGURE 2.14 Interpretation of 1012, which is equal to 510.
40 Computational Thinking for the Modern Problem Solver
string correspond directly with how the number is written in the binary
(or base 2) numeral system, it is straightforward to see how an integer is
stored. Figure 2.15 shows the bit patterns and corresponding numeric values for a select number of numeric values.
An 8 bit string can only represents 256 numbers since an 8 bit string
can only exhibit 28
unique patterns. This implies that the largest number
that can be encoded as an 8 bit binary number is 28
1 or 255. This statement can be generalized by stating that any binary bit string of length N
can only encode the numbers 0 through 2N 1.
2.4.1.4 Real Numbers as Binary Bit Strings
Although we can represent an integer as a sequence of bits, is it possible to
represent a real number such as 2.31 or 2.125 or even 3.1415926? Consider
extending the meaning of a positional numbering system to the right of
the decimal such that the positions start at 1 and decrease with distance
from the decimal. For example, in base 10, the value 1.625 means (1 100
)
+ (6 101) + (2 102) + (5 103). We can then represent real numbers as
binary bit strings assuming that we can determine the decimal location.
Consider, for example, the meaning of 1.1012.
1 101 1 2 1 2 0 2 1 2
111 1
2
0 1
4
1 1
8
1 1
2
1
8
1.625
2
0 1 2 3 = = + + +
= + + +
= + +
=

Bit String Decimal Value
00000000 0
00000001 1
00000010 2
00000011 3
00000100 4

11111110 254
11111111 255
FIGURE 2.15 Understanding binary bit strings.
How Real-World Information Becomes Computable Data 41
2.4.1.5 Precision as a Source of Error
One difficulty that arises when encoding real numbers is that there may be
an arbitrary number of digits on the right side of the decimal value to represent even small numbers. If we write 1/3 as a real number, for example,
we begin to write 0.33333333333333333333333333 but soon realize that we
will never be able to write as many digits as are required for a completely
accurate representation. Most real numbers cannot be exactly encoded by
the encoding scheme described earlier and are therefore represented as
an approximate value. Computer applications typically, therefore, allow
rounding errors to occur and hence computers often produce incorrect,
although highly accurate, results. Precision is a measure of the accuracy of
a stored quantity. The precision is usually measured as the number of available bits. If a computer uses 16 bits to store real numbers, we say that the
computer is precise up to 16 bits, or that the computer uses 16 bit precision.
2.4.1.6 Underflow and Overflow as Sources of Error
Other kinds of error can be introduced into a computing system through
underflow and overflow. Recall that an 8 bit binary string can only hold
values between 0 and 255. An example of overflow occurs when a computer is instructed to add 1 to the value 255 and store the result as an 8 bit
binary string. Of course the result should be 256 but since 256 cannot be
encoded as an 8 bit binary string the result will either be an error of some
sort or, on many computing systems, the result will actually wraparound
to 0! In general, overflow occurs when a computer instruction produces
a value that is too large to be encoded by the number of bits available.
Underflow occurs when a computer instruction produces a value that is
too small in magnitude (i.e., very close to zero) to be encoded by the number of bits available.
2.4.2 Text
All data that is stored in a computing system is encoded as bit strings. You
might wonder, then, how can a bunch of bits be made to look like text?
Even the words that you are now reading are stored in binary form and
this information is then presented to you as text. The text you are reading
even has different fonts using different sizes and weights.
First, it is important to understand that a textual character, when drawn
on either a page of text or on a computer screen, is really just a picture.
Figure 2.16 illustrates the graphical nature of text by showing the letter Q
as it appears in different font families. Although the pictures that are used
42 Computational Thinking for the Modern Problem Solver
to represent the letter Q are each different, they nonetheless each represent
the same thing: the letter Q.
Textual characters are usually encoded as integer values using the encoding schemes discussed earlier in this chapter. Each number is arbitrarily associated with the image that should be used when the character is drawn on a
page or shown on the computer screen. The associations between numbers
and text are known collectively as a character encoding scheme. The most
common character encoding scheme is the ASCII table, shown in Figure 2.17,
which defines associations between numbers and English textual characters.
In the ASCII table, the number 65 is associated with uppercase A, whereas
the number 97 is associated with lowercase a. The number 38 is associated
with the ampersand (&) and the number 126 is associated with the tilde (~).
Since English has relatively few characters, the ASCII table only has about
128 entries. Other languages, such as Japanese or Chinese, use thousands of
characters and hence the association tables are much larger.
Some text contained in the ASCII table is not really pictorial but rather
a command that a text editor or text processor must follow. These characters are known as nonprintable text characters because they cannot be
drawn. The backspace key, for example, is not printable since you do not
see anything when you strike that key, but you would expect that a text
processor would take some action whenever the user enters a backspace.
Nonprintable characters are shown in Figure 2.17 as an empty cell.
In addition, the images associated with the textual characters are
dependent on the specific font or typeface. Many fonts use the same basic
symbols, but draw the glyphs in different ways (serif, sans serif, boldface,
italics, Helvetica, Times, etc.). Applications that process text must usually
associate a font with a textual character but this association is beyond the
scope of our discussion.
2.4.3 Colors
The human eye perceives color through three types of biological photosensors known as cones. Each cone is attuned to one of three wavelengths that
correspond roughly to red, green, and blue light. The individual responses
FIGURE 2.16 The letter Q is shown using five different font families.
How Real-World Information Becomes Computable Data 43
of all cones combine to form the perception of a single color at a single
point within the field of view. The design of this biological system suggests
that color is a three-dimensional entity.
The RGB color model is the most common way of representing color
in image-processing systems. The RGB model uses red (R), green (G), and
blue (B) as the primary colors such that any color can be created by combining different amounts of these three primaries. By way of example,
consider a flashlight that has a slider allowing you to choose the strength
of light emitted. In setting the slider to 0, the flashlight is turned completely off and generates no light, whereas in setting the slider to 255 (the
maximum setting) the flashlight generates as much light as it is capable of
generating. Now consider three such flashlights: the first emits purely red
light, the second emits purely green light, and the third emits purely blue
light. If all three flashlights are aimed at the same spot on a white wall any
color can be projected onto the wall by adjusting the slider values on the
three lights in different ways. If all sliders are set to 0, black is projected
onto the wall. If all sliders are set to 255, white is projected onto the wall,
and if all sliders are set to 128 then gray is projected.
In computing systems, a color is usually encoded as three integer numbers where each number is in the interval 0 to 255. In addition, since each
value can be one of only 256 different values, a bit string of length eight is
0 1 2 3 4 5 678 9 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 31 32
!
33
”
34
#
35
$
36
%37
&38

39
(
40
)
41
*
42
+
43 44 –
45
.
46
/
47
0
48
1
49
2
50
3
51
4
52
5
53
6
54
7
55
8
56
9
57
:
58
;
59
<
60
=
61
>
62
?
63
@64
A65
B
66
C67
D68
E
69
F
70
G71
H72
I
73
J
74
K
75
L
76
M77
N78
O79
P
80
Q81
R
82
S
83
T
84
U85
V86
W87
X88
Y
89
Z
90
[
91

92
]
93
^
94

95
`
96
a
97
b
98
c
99
d
100
e
101
f
102
g
103
h
104
i
105
j
106
k
107
l
108
m109
n
110
o
111
p
112
q
113
r
114
s
115
t
116
u
117
v
118
w119
x
120
y
121
z
122
{
123
|
124
}
125
~
126 127 128 129 130 131 132 133 134 135 136 137 138 139
FIGURE 2.17 The ASCII table associations between numbers and textual
characters.
44 Computational Thinking for the Modern Problem Solver
sufficient for encoding each value. This implies that a single color will be
encoded as a bit string of length 24 since there are three values and each
value is encoded with 8 bits. Figure 2.18 shows how the three colors red,
green, and yellow (which is a mixture of red and green) would typically be
encoded as 24 bits within a computing system. The corresponding interpretation of the three decimal values is given in the right-most column.
2.4.4 Pictures
The most common encoding of a digital image is that of a two-dimensional
grid of colors. Each element of the grid is known as a pixel (this term is an
abbreviation of the phrase picture element) and represents a very small rectangular region of the image that is comprised of a single color. When the grid
of pixels is viewed at an appropriate distance, the individual pixels recede from
view while collectively appearing as a naturally colored and smooth image.
Images are typically encoded as a sequence of pixels where each pixel
corresponds to a single color. Since a color is normally encoded as a 24 bit
string, the total bits required to encode a digital image is on the order of
24 bits times the number of pixels in the image. A small number of extra
bits are also required to store useful information such as the width and the
height of the image. This extra information is referred to as a header, and
because the header can be encoded using an extremely small number of
bits relative to the pixel data, we will not consider it further.
High-definition video uses individual images that have up to 1920
columns and 1080 rows of pixels for a total of 1920 1080 or 2,073,000
pixels. Since each of these pixels is encoded as a bit string of length 24,
the image can be encoded as a bit string of length 1920 1080 24 or
49,766,400 bits. Alternatively, using a byte as a measure of data capacity,
the image can be encoded using 1920 1080 3 or 6,220,800 bytes or
approximately 6 megabytes. Digital cameras take images that use on the
Color Name Bits
red green blue Decimal
red 111111110000000000000000 (255,0,0)
green 000000001111111100000000 (0,255,0)
yellow 111111111111111100000000 (255,255,0)
FIGURE 2.18 How colors are typically encoded as binary bit strings.
How Real-World Information Becomes Computable Data 45
order of 10 megapixels and images of this resolution can be encoded as a
string of 30 megabytes.
Sometimes a picture does not contain many colors. Black-and-white
images, for example, use only two colors, whereas grayscale images use at
most 256 colors; each color being a unique achromatic gray. While a color
image generally uses 24 bits per color, other image types may use fewer
than 24 bits per color since there are many fewer possible color values.
Since grayscale images may use no more than 256 colors, we can encode a
grayscale color using 8 bits and since there are only two colors in a blackand-white image, we can encode the colors using a single bit!
Figure 2.19 shows a black-and-white image having eight columns and
eight rows for a total of 64 pixels. Since there are only two colors, we use
a single bit to encode a color. In this figure we use 0 to denote white and
1 to denote black. When these bits are used to encode the image the bits
are arranged as a single linear unit in memory and not organized as the
two-dimensional structure illustrated in Figure 2.8. More specifically, the
image pixels could be encoded as the bit string 00111100010000101010010
11000000110100101100110010100001000111100.
2.4.5 Sound
Digital audio is used almost exclusively today when recording, processing,
and distributing sound. Online music stores contain hundreds of thousands of hours of digital sound; the soundtracks and audio of DVD movies are encoded digitally; and your voice is digitally encoded by your cell
phone prior to being delivered to the person at the other end of the call.
0 0 1 1 1 1 0 0
0 1 0 0 0 0 1 0
1 0 1 0 0 1 0 1
1 0 0 0 0 0 0 1
1 0 1 0 0 1 0 1
1 0 0 1 1 0 0 1
0 1 0 0 0 0 1 0
0 0 1 1 1 1 0 0
FIGURE 2.19 A black-and-white image could be encoded using the bits shown
on the right.
46 Computational Thinking for the Modern Problem Solver
Sound is a physical phenomenon caused by waveforms that propagate
through the air. A microphone is used to transform the waveform into an
analog electric signal after which the analog signal is sampled to produce
a digital encoding. Sampling is a process where the strength of a changing
signal is measured at regular time intervals and those measurements are
then recorded. In this way, the sound wave is converted into a sequence of
numeric values.
Frequency is the rate at which sound waves change and is measured in
terms of the hertz. The hertz is denoted as Hz and is defined as the number
of cycles (or changes) per second. Sound waves that change at a slow rate
are perceived as a low pitch while sound waves that change at a high rate
are perceived as higher in pitch. The average person can hear sound waves
20 Hz up through about 20,000 Hz or 20 kHz.
Figure 2.20 shows how the strength of a sound wave is sampled at regular periods of time to obtain a sequence of samples. In this example, the
sound wave has a frequency of approximately 4 Hz (although this is not
obvious) and must therefore be sampled at least eight times per second
to adequately record the signal. The actual sampling rate is 10 Hz, or ten
times per second. Every tenth of a second the strength of the sound wave
is measured and recorded. The resulting digital sound is depicted as the
sequence of measurements shown on the right of Figure 2.20. It should be
apparent that higher sampling rates will yield more accurate encodings of
the analog signal.
The NyquistShannon sampling theorem, named after Harry Nyquist
and Claude Shannon, states that the rate at which samples are taken must
be at least twice that of the highest frequency signal that is to be measured.
This theorem implies that a sampling rate of at least 40 kHz is required
when capturing sound waves that span the entire 20 to 20,000 Hz range of
human hearing. This fact explains why compact discs (CDs) are sampled
2
Wave Strength
1
1
2
2
Wave Strength
1
1
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Time Time
0.9 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
2
FIGURE 2.20 A sound wave is sampled ten times per second to obtain the
sequence plotted on the right.
How Real-World Information Becomes Computable Data 47
at a rate of 44.1 kHz, digital audio tapes (DATs) are sampled at 48 kHz,
and a 96 kHz sampling rate is used for digital video discs (DVDs).
Consider a song that is five minutes long and is sampled at a rate of
48 kHz for recoding on a digital audio tape. To determine the number of
samples required to encode the song we must note that there are 48,000
samples taken every second and that the song lasts for 300 seconds. Thus,
the song will be encoded as a sequence of 48000 5 60 or 14,400,000
samples. For this example, we will assume that a single sample is encoded
as an 8 bit string, which means that the song can then be encoded in
14,400,000 bytes or about 14 MB. Of course if the number of bits required
to encode a single sample is greater than 8, the number of bytes required
to encode the song also changes. Compact discs, for example, use 16 bits
for each sample and DVD mastering usually requires 24 bits per sample.
2.5 DATA COMPRESSION
The previous section described techniques for converting real-world information into digital data and did not make any attempt to minimize the
number of bits used for encoding. Data compression is a technique that is
used to encode real-world information using fewer bits than a straightforward encoding requires. In this section we will briefly describe why data
compression is useful and how data compression can reduce the number
of bits required to encode information.
Data compression is often very useful because it reduces the consumption of resources such as hard disk space or the time it takes to send files
across the Internet. If a digital image can be compressed from 10 MB in
size to 1 MB in size, for example, the compressed image can be sent across
the Internet ten times more quickly than the uncompressed image. Also,
if a photo album that consumes 200 GB of image data can be compressed
to 20 GB, then you may not need to buy a new hard drive to store your
photo album!
There is a cost to using data compression, however, since a great deal of
computational work is required for a computer to take the uncompressed
file and find a way to eliminate some of the bits. Also, when a file is stored
in compressed form, the computer must take time to uncompress the file
for further processing. This computational work also takes time to perform
and sometimes the cost of compression outweighs the benefits. Video compression, for example, takes a great deal of time to perform and may even
require specialized hardware to perform fast enough for live streaming.
48 Computational Thinking for the Modern Problem Solver
By way of example, consider the reasonably complicated sport of
American football. Two teams of eleven players compete to move the
football downfield into the opponents end zone. The game consists of a
series of individual plays where every player on a team must know what
to do on the play. Teams will often try to gain an advantage by executing
plays more quickly than their opponent can respond. The problem is that
a single play may take many words to fully convey since every play must
describe things like the blocking scheme, the snap count, the position of
the running backs, and the direction and nature of the play itself. A full
play might, for example, be described as The snap count is 3. We will use
a zone-blocking scheme to the right. The fullback must line up to the right,
the halfback will motion to the left, and the quarterback will hand off to
the right. Calling such a play by fully describing it with full sentences
is simply too time consuming for effective game play. As a result, teams
have developed ways to communicate the same information by using
many fewer words. A simple play-calling scheme might use four digits to
communicate a single play. The first digit might indicate the snap count,
the second the blocking scheme, the third will define the alignment and
motion of the backs, and the fourth will describe the nature of the play
itself. The play 3518, for example, might be understood as 3-snap count;
5-zone blocking to the right; 1-fullback aligns right, halfback motions left;
8-quarterback hands off to the right. This compression technique takes
work by the players to memorize and learn what the numbers actually
mean but this cost occurs before the game is played. The payoff comes
How Real-World Information Becomes Computable Data 49
during the game when the play calling can be quickly communicated
(transmitted) and decoded.
The obvious and central idea in data compression is that unnecessary
bits should be eliminated from the encoding scheme. While this is an
obvious idea, identification and elimination of unnecessary bits is often
a very difficult task and largely depends on the type of information being
compressed: text, images, or audio.
2.5.1 Run-Length Encoding
Run-length encoding is one of the simplest types of compression techniques that can be used on images and even text. We will describe how
run-length encoding can be used to encode multiple pixels as a single
value rather than recording each pixel individually. Consider, for example,
a binary image in which each pixel is encoded as a single bit that is either 0
(denoting black) or 1 (denoting white). One row of the image may contain
the 32 pixel sequence
11111111110001111111111111111111
This row contains three runs: 10 white pixels followed by 3 black followed by 19 white. This information can be encoded as the 3 byte sequence
{10, 3, 19} by assuming that the data begins with white runs. Note that the
raw representation uses 32 bits of memory while the run-length encoding
uses only 24 bits of memory if we assume that 8 bit bytes are used to store
each run.
Figure 2.21 gives a complete example of how run-length encoding can
be used to compress binary image data. The heart image has 18 columns
and 14 rows. Raw encoding, where a single bit is used to encode each pixel,
requires 18 14 or 252 bits. Run-length encoding, where we encode each
row by recording the lengths of each run in the row, uses significantly
fewer bits. The first row, for example, is encoded by the five numbers {3, 3,
5, 4, 3} since the first row starts with three white pixels followed by three
black pixels and so on. If we count the total number of runs in the entire
image, we find that there are a total of 43 runs. Since the longest run is 18,
we realize that we can encode each run using five bits. Therefore, the total
number of bits required to run-length encode this image is given as 43
runs times 5 bits per run for a total of 43 5 or 215 bits.
You may notice that some runs, rows 3 to 7 for example, begin with
runs of length zero. This is because when we decompress the run lengths
50 Computational Thinking for the Modern Problem Solver
we must assume that we are starting with either white or black runs. In this
example, the assumption is that each row starts with a run of white pixels.
Since there are no white pixels at the beginning of these rows, we encode
the runs as being length zero. When decompressing the run-length data,
we must also know how many columns and rows are in the image. These
two pieces of information must be stored in the image header.
Compression schemes can be classified as either lossless or lossy. A lossless compression scheme encodes an exact representation of the original
data, whereas a lossy compression scheme encodes an approximate representation. The central idea behind lossy compression is to identify pieces of
information that are of little importance and simply discard those pieces
of information in order to use fewer bits. Such compression schemes are
known as lossy because real information is actually lost in the process.
There are hundreds of image file types in common use. Among the
most popular are the PNG, JPEG, and GIF formats that are most often
used to display images on the Internet. Image file types typically use some
compression scheme to reduce the overall size of the image file. The PNG
image format uses lossless compression to reduce the overall file size,
whereas JPEG and GIF typically use lossy compression. While the JPEG
and GIF file formats do include limited support for lossless compression,
almost all of the JPEG and GIF images on the Internet have been compressed using a lossy technique.
3 4
6 7
8 9
1 3
1
1
1
1
1
1
2
3
4
6
8
2
3
4
6
8
3 5 3
18
18
18
18
0,8,1,9
1,6,3,7,1
1,16,1
1,16,1
2,16,2
3,12,3
4,10,4
6,6,6
8,2,8
3,3,5,4,3
0,18
0,18
0,18
0,18
16
16
14
12
10
6
2
FIGURE 2.21 A black-and-white image could be encoded using the numbers
shown on the right.
How Real-World Information Becomes Computable Data 51
Figure 2.22, a digitized image of a famous painting by James McNeill
Whistler [1], illustrates the difference between lossy and lossless compression. The digital image consists of 513 columns and 668 rows and is stored
in uncompressed form using 24 bits per pixel. The uncompressed image
therefore requires 513 668 24 or 8,224,416 bits. JPEG compression
reduces the memory requirement to 55384 bits but significantly reduces
the image quality. PNG compression reduces the memory requirements
to 5,668,304 bits without any reduction in quality. JPEG can be controlled
to provide much higher quality results but with a corresponding loss of
compression effectiveness.
Sound information can also be compressed by recognizing that certain sound waves are less important than others when listening to music
or voice recordings. The MP3 standard, for example, will discard higher
frequency sound waves (or portions thereof) in order to encode the sound
using fewer bits.
2.6 SUMMARY
If computers are used to process information about the real world, this
information must first be converted into a computable form. This chapter
has given an overview of how real-world information of various types:
numbers, text, images, and sound can be converted into computable form.
Bit strings are used to encode all computable data. The length of a bit
Uncompressed image:
8,224,416 bits
JPEG
(Lossy): 55384 bits
PNG
(Lossless): 5,668,304 bits
FIGURE 2.22 Lossy and lossless image compression.
52 Computational Thinking for the Modern Problem Solver
string gives a measure of the amount of information that the bit string can
hold such that each unique pattern generated by the bit string corresponds
to some piece of real-world information.
REFERENCE
1. Wikipedia, http://en.wikipedia.org/wiki/Symphony_in_White,_No._1:_The_
White_Girl (accessed January 2013).
TERMINOLOGY
analog
ASCII table
base
binary digit
binary numeral
bit
bit string
byte
color
cones
continuous
data
data capacity
data compression
decimal numeral
digital
discrete
frequency
hertz
information
lossless
lossy
numeral system
Nyquist-Shannon sampling
theorem
overflow
pixel
positional numeral system
precision
radix
RGB
Roman numeral
run-length encoding
sound
tally marking
underflow
word
How Real-World Information Becomes Computable Data 53
EXERCISES
1. Take the initials of your first and last name and write them down.
These are initials, so they should be capitalized! Write down the 16
bits that a computer would most likely use to store these two initials
in a computer. (Hint: The encoding is given by the ASCII table.)
2. What text is encoded in the following? (Hint: The encoding is given
by the ASCII table.)
a. 0011001000101011001100110011110100110101
b. 01000010011010010111010001110011
c. 001111000011001100110011
3. Write the number 4 using the following systems.
a. tally mark number system
b. Roman number system
c. binary system
4. Write the equivalent decimal (base 10) number for each of the following binary numbers.
a. 10011
b. 11000
c. 10010
d. 00000
e. 11111
5. For each quantity listed, indicate whether the quantity is continuous
or discrete.
a. Day of the week
b. Flying speed of a hummingbird
c. Number of peas in a pea pod
d. Length of a commencement speech
e. Number of chapters in a book
54 Computational Thinking for the Modern Problem Solver
f. Number of commas in a book
g. Weight of a book
h. Age of a book
6. For each pair of the following items, circle the one that would most
probably require more bits to represent.
a. The book Peter Rabbit or a single JPEG image from a modern
digital camera
b. One pop song or one page of the textbook
c. One color image saved as a JPEG from your digital camera or the
complete works of William Shakespeare (Make sure to give the
average size of a JPEG image from your camera OR assume that
each JPEG image consumes 1.5M bytes.)
7. How many unique patterns does a sequence of 5 bits generate?
8. How many unique patterns does a sequence of N bits generate?
9. For each quantity listed, give the number of bits that would be
required to store the data in a computing system.
a. The month
b. A class grade. Class grades must be one of A, B, C, D, F, or I
(for incomplete).
c. An MPAA movie rating. The MPAA rates movies as one of the
following: G, PG, PG-13, R, NC-17.
d. The track number of a song on an MP3 album. The most tracks
that can be put on an MP3 album is 100.
e. The day of the year. There are 365 days in a year (except for leap
years in which there are 366 days). For example, January 1 would
always be day 1 while December 31 would be day 365 for nonleap years and day 366 for leap years.
f. One nucleobase of a DNA string. There are only four nucleobases
in this example: adenine (A), guanine (G), cytosine (C), and thymine (T).
How Real-World Information Becomes Computable Data 55
10. Consider a song that is two minutes long and is sampled at a rate of
24 kHz for recoding on a digital audiotape. We will assume that a
sample is encoded as an 8 bit string. How many bits are required to
store this song without compression?
11. Consider a black-and-white picture that consists of 9 columns and 12
rows of pixels. The picture is encoded using the following run-length
encoding where a forward slash (/) denotes the end of a row. Draw
the picture.
0,8/1,3,4/2,2/2,2/2,2,3,1/2,6/2,2,3,1/2,2/2,2/2,2/2,2/1,4
12. Consider the following black-and-white picture. Give the run-length
encoding of the picture.

57
Chapter 3
Logic
Logic is the anatomy of thought.
JOHN LOCKE
Your life is full of daily decisions that, over time, determine the trajectory of your personal history. Many of these decisions involve making
significant choices about who to marry, what career path to undertake,
what to eat, how to best manage your finances, or what political cause
to support. Every decision that you make in your life is based on some
belief about the nature of the universe and, perhaps, the very meaning of
life itself. It is apparent if we adopt beliefs that are false, then decisions
that are based on those beliefs will be misguided at best and destructive at the worst. Even if our belief system includes only true beliefs,
we might still make decisions through illogical or haphazard reasoning
about those beliefs and again, end up making misguided or potentially
destructive choices.
OBJECTIVES
To understand that logic is necessary and useful for correct and rational
thought
To describe how the logic of natural language is expressed
symbolically
To define logical values and the logical operators AND, OR, NOT, IMPLIES
To define truth tables, tautologies, and contradictions
To describe how logic can be applied to solve a variety of real-world
problems
58 Computational Thinking for the Modern Problem Solver
In this chapter we will see that logic serves as the basis for all correct
and rational thought. We will discover that certain patterns of thinking
will form a path of truth, whereas other patterns will inevitably lead to
falsehood. We will also discover that these patterns of thought can be
expressed in ways that a computer can understand and process. Finally,
we will show that these patterns of thought are pervasive and can be used
to solve a wide variety of real-world problems.
3.1 WHAT IS LOGIC?
You may be surprised to hear that numerous mathematicians and philosophers have defined human reasoning as a logical system. Logic, in its broadest sense, deals with correct and incorrect ways to reason. Logic provides a
way to tell the difference between incorrect and correct thinking, and can
therefore be defined as the science of correct thinking. The study of logic can
be broken into two categories: inductive logic and deductive logic.
Inductive logic is a type of reasoning that begins with a set of observations or experiences from which conclusions can be derived with some
degree of certainty. As an example of inductive reasoning, consider a
scenario where you have eaten brussels sprouts only twice in your life.
Unfortunately, you became physically ill within hours of eating them and
therefore conclude you are allergic to brussels sprouts. Although the conclusion that I am allergic to brussels sprouts is reasonable, it is not the
only conclusion that could be reasonably reached and is therefore not certain. Perhaps you were coincidently exposed to a contagious virus shortly
before eating the brussels sprouts and this virus was the actual cause of
your illness. Conclusions reached in an inductive system are necessarily
uncertain and are directly related to the number of experiences on which
the conclusion is based. For example, the certainty of the conclusion that
I am allergic to brussels sprouts would be increased if you ate them three
more times and became physically ill in each case.
Logic 59
Deductive logic, by contrast, begins by assuming that certain things are
absolutely true from which other facts must also be absolutely true. Any conclusions that are reached under deductive logic are absolutely, irrefutably,
and certainly true if the assumptions are true. You may, for example, assume
that all men are mortal and that Aristotle is a man. From these two assumptions you may deduce with absolute certainty that Aristotle is mortal.
Aristotle was an ancient Greek philosopher who lived around 350 BC.
Aristotle described the logical rules of deduction that must be followed in
order to draw correct conclusions from a set of assumptions. Aristotelian
logic is a deductive system that uses human language to form premises
from which a conclusion can be deduced if certain rules of logic are followed. A premise is a statement that is assumed to be true and that is
used to justify a conclusion. A conclusion is a statement of truth that must
logically flow from the premises. More specifically, Aristotle described a
syllogism as a logical argument that contained two premises and a true
conclusion that must logically follow if the two premises are actually true.
As an example, consider the following syllogism.
Premise: Computational thinking is beneficial for all students.
Premise: Jemimah Farnsworth is a student.
Conclusion: Computational thinking is beneficial for Jemimah
Farnsworth.
Symbolic logic is a modern extension of Aristotelian logic where symbols, rather than phrases drawn from human language, are used to
represent statements of truth. Logical operators, also known as logical
connectives, are used to express logical thought. Boolean logic is a symbolic logic system that was created by a mathematician named George
Boole around 1850. Modern computing systems rely heavily on the rules
of Boolean logic for generating correct and reliable results. The following
sections describe the elements of Boolean logic and show how Boolean
logic can be understood and processed by computing systems.
3.2 BOOLEAN LOGIC
Propositions form the basic units of Boolean logic. A proposition is a statement that can be either true or false. Stated another way, a proposition is
a statement that has a value of either true or false. Consider, for example,
the following true statement.
60 Computational Thinking for the Modern Problem Solver
Mount Everest is the tallest mountain in the world.
Since it makes sense to say that it is true that Mount Everest is the tallest mountain in the world we know that this statement is a proposition
because it is an expression of truth. It is very important to understand
that although some propositions have a value that is true, propositions
can also have a value that is false. For example, consider the following
statement.
The Mississippi is the longest river in the world.
The Nile is the longest river in the world and hence the statement that
the Mississippi is the longest river in the world is a false statement. Just
because the sentence is false, however, does not mean that the sentence is
not a proposition. In fact, just the opposition conclusion holds. The sentence is shown to be a proposition precisely because it has a value of false.
In other words, the value of this sentence is false.
Some sentences do not have a truth value and are therefore not propositions at all. Consider, for example, the following sentences.
Brush your teeth.
How tall is Mount Everest?
The first sentence is a command, written in the imperative voice,
and therefore has no truth value. We could not meaningfully say, for
example, that Brush your teeth is true. The second sentence is a question
and therefore has no truth value. Again, we cannot meaningfully say that
How tall is Mount Everest? is false.
In Boolean logic there are only two values: true and false. These two
values are known as logical values or truth values. Boolean logic does not
allow for uncertainties or for probabilities. A proposition is either completely true or it is completely false. A proposition cannot be probably true
or probably false. Nor can a proposition be both true and false at the same
time. The notion that there are only two truth values in a logical system is
referred to as the law of the excluded middle.
Propositions can be either simple or compound. A simple proposition is
one that cannot be broken into parts. A compound proposition is formed
by combining simple propositions with logical connectives, also known
as logical operators. There are four fundamental logical operators that are
Logic 61
best described by the words and, or, implies, and not. Consider, for example, the following two simple propositions that are connected using the
and operator to form a compound proposition.
Simple: I am hungry.
Simple: I am cold.
Compound: I am hungry and I am cold.
This compound proposition is a statement that has a truth value since the
statement that I am hungry and I am cold is either true or it is false.
Boolean logic allows us to concisely and precisely express lengthy propositions by (1) abbreviating simple propositions and (2) precisely defining
each of the four logical connectives.
Simple propositions are often abbreviated, or labeled, in order to make
logical expressions more concise and readable. The labels serve as an
abbreviation for the entire proposition and are always given as a single
capital letter to make things simpler. We might, for example, use the letter P as an abbreviation for the proposition I am hungry. Throughout
our text we will use an equal sign (=) to indicate the abbreviation that is
being used for a particular proposition. Following are examples of abbreviating propositions.
P = I am hungry.
Q = I am cold.
S = Mount Everest is the tallest mountain in the world.
We can then create new propositions by using the logical operators to
connect existing propositions. Given the aforementioned abbreviations
shown, we can create the proposition I am hungry and I am cold as
shown by the following.
P and Q
3.2.1 Writing Well-Formed Propositions
Propositions must be well formed (i.e., properly written) to have meaning. When writing a proposition, certain rules must be exactly followed
in order to construct a meaningful proposition. If these rules are not
62 Computational Thinking for the Modern Problem Solver
followed you may write something that appears to be a proposition but is
actually just a meaningless jumble of labels and operators.
Perhaps you are familiar with the famous poem Jabberwocky written
by Lewis Carroll. The poem looks and sounds like an English poem, but is
in reality just a series of nonsensical syllables (when written) and melodic
sounds (when spoken). The opening stanza is reproduced next.
Twas bryllyg, and ye slythy toves*
Did gyre and gymble in ye wabe:
All mimsy were ye borogoves;
And ye mome raths outgrabe.
Although Jabberwocky appears to be a meaningful poem, it is nonsense. There is no real meaning, because the phrases are not composed of
well-defined words and the normal rules of grammar are not followed. Just
as a poem must follow rules of grammar and spelling, a well-formed logical proposition must also follow specific rules. These rules guarantee that
the proposition has meaning and is not merely a jumble of nonsense. The
grammatical rules for writing a well-formed proposition are listed next.
Rule 1Each of the following is a simple proposition.
a. Any single letter
b. True
c. False
* The slithy tove image is derived from an illustration by John Tennel in Carrolls original
publication.
Logic 63
Rule 2Let a box () stand for a proposition (either simple or compound). Assuming that each box is some proposition, then each of
the following are also propositions.
a. and
b. or
c. implies
d.
e. not
f. ()
These rules establish patterns of grammatical structure that all propositions must possess. The various parts of Rule 2 specifically show how to
make compound propositions by using logical operators to combine simpler propositions into a larger whole. With these rules in mind, consider
the mixture of letters, operators, and parenthesis listed below.
P and not (Q or R)
We might naturally ask if P and not (Q or R) is a well-formed
proposition (and therefore a meaningful proposition) or if it is merely
a nonsensical jumble of letters and words. For this example we can
prove that the expression is well-formed by carefully applying the two
grammatical rules that well-formed propositions must follow. Our process of reasoning will move from the simplest substructures within the
entire proposition up to the more complex propositions that comprise
the whole.
Step 1We can first apply Rule 1a to the capital letters P, Q, and R. In our
proof, we will use a box symbol, , to denote a portion of the text that
has been proven to be a proposition by applying one of the rules. To
prove that the entire expression is a well-formed proposition, we must
show that the entire expression can be reduced to a single box.
Step 2By applying Rule 1a to each of the letters P, Q, and R we can
rewrite the expression as shown next. We use a right arrow () to
indicate that one of the rules has been applied to show that some part
64 Computational Thinking for the Modern Problem Solver
of the expression has been proven to be a proposition. Notice that we
are not trying to determine what the propositions means but merely
trying to determine if the proposition is properly written.
P and Not (Q or R) and not ( or )
Step 3We must now see if any further rules can be applied to what
remains of the expression. At this point in our proof, there is only a
single rule that can be applied. Rule 2b says that or is a proposition and hence we can replace the expression or with a box.
and not ( or ) and not ()
Step 4We must continue to find further rules to apply to what
remains of the expression. Again, there is only a single rule that can
be applied. Rule 2f says that () is a proposition and hence we can
replace the expression () with a box since it is a proposition.
and not () and not
Step 5We now notice that we can replace not with a box since
not is a proposition as defined by Rule 2e.
and not and
Step 6Finally, it should be obvious that Rule 2a can be applied to
complete our proof. We can replace and with a box to yield.
and
At this point we have collapsed the original expression into a single
box. This shows that the original combination of letters, words, and parentheses is, in fact, a well-formed and meaningful proposition. When constructing our proof, every time that we applied one of the rules to replace
a phrase with a box we identified a proposition that was a smaller part of
the larger whole. Figure 3.1 shows how our proof can be drawn as a series
of boxes that are nested within one another.
Some mixtures of letters and operators might appear to be meaningful
Boolean propositions but are really just meaningless jumbles of symbols.
Consider, for example, the following expression.
P not Q
Logic 65
If we apply the same process of using rules to replace elements of
the expression, we will eventually show that this expression is not well
formed.
Step 1We first recognize that Rule 1 can be applied to the letters P
and Q.
P not Q not
Step 2We then recognize that Rule 2d can be applied to not .
Replacing not with a box yields the following.
not
Step 3At this point we conclude that P not Q is not a proposition
since there is no rule that will allow us to reduce to a single
box.
The phrase P not Q is actually a sequence of two separate propositions rather than a single proposition. Although each of the two propositions may be meaningful when considered in isolation, the sequence
itself does not have a truth value. We can illustrate the nonsensical nature
of P not Q by expanding the abbreviations into a propositional statement. If, for example, we understand P to abbreviate I am hungry and
Q to abbreviate I am cold we understand the expression P not Q to be
something like I am hungry I am not cold. Just as the rules of English
grammar require us to insert a semicolon or perhaps a period between
these two propositions, Boolean logic expects to see a logical connective
such as and joining the two propositions. Since there is no connective,
the resulting phrase is nonsensical. Joining the two propositions with a
logical operator such as and would yield the meaningful proposition I
am hungry and I am not cold.
P and not ( o Q r R )
FIGURE 3.1 The Boolean proposition P and not (Q or R) is shown to be well
formed such that each dotted box corresponds to some proposition that is an element of the whole.
66 Computational Thinking for the Modern Problem Solver
3.2.2 Evaluating Propositions
When we evaluate a proposition, the goal is not to make sure that it is
well written but rather to determine the truth value of the proposition.
Consider, for example, the following simple propositions.
P = I am hungry.
Q = I am cold.
If we are then asked to evaluate the truth value of the compound proposition given next, we must very carefully apply certain rules of logic to
determine the answer.
P and Q
The truth value of the compound proposition P and Q depends upon
the truth values of both P and Q. Perhaps I have just finished eating a
very large dinner of sushi, turkey, fruit salad, and organic beets. In this
case, we understand that the statement I am hungry and I am cold is
false because the simple proposition that I am hungry is false. Similarly,
perhaps I am resting on the beach during a sizzling summer afternoon. In
this case, we understand that the statement I am hungry and I am cold
is false because the simple proposition that I am cold is false. In Boolean
logic, simple propositions are variables that affect the truth value of any
compound proposition that contains them.
Although it is not overly difficult to determine the truth value of a
proposition such as P and Q, more complex propositions require careful
thought to evaluate. The following two propositions illustrate that logical
expressions can be complex enough to require significant effort to evaluate.
not P or not Q and R
not P or Q and R or (P and Q)
Fortunately, Boolean logic defines evaluation rules that, when carefully
followed, will allow us to determine the truth value of any compound
proposition. These rules of evaluation are centrally related to understanding the logical operators and, or, implies, and not.
An operator is something like a machine that accepts inputs, processes
those values, and produces a single output value. The arity of an operator
Logic 67
is the number of inputs into the operator. Each of the operators also has
a technical name that describes the underlying function of the operator.
Figure 3.2 gives the arity and technical name for each of the logical operators. Operators that have an arity of two are known as binary operators and
operators that have an arity of one are known as unary operators. The truth
value that is generated by a logical operator is dependent only on the input(s).
3.2.2.1 Conjunction (AND)
For the binary operators there are only two inputs and since each of these
two inputs has only two possible values there are only four situations
that the operator must handle. Each of the binary operators can be fully
described by naming the truth value that the operator generates for each
of the four input conditions. Consider, for example, the following definition of logical conjunction.
1. The logical conjunction of false with false is false.
2. The logical conjunction of false with true is false.
3. The logical conjunction of true with false is false.
4. The logical conjunction of true with true is true.
Although this is a perfectly reasonable way to define the operators, the
definition is more wordy than necessary. To be concise, the logical operators are usually defined as a truth table. Each row of a truth table corresponds to one combination of inputs, every column except for the last
gives the input values for the operator, while the final column gives the
truth value for that input combination.
Operator Technical Name Arity Example of Use
and conjunction 2 (binary) P and Q
or disjunction 2 (binary) P or Q
implies implication 2 (binary) P implies Q
equivalence 2 (binary) P Q
not negation 1 (unary) not P
FIGURE 3.2 The logical operators.
68 Computational Thinking for the Modern Problem Solver
Consider, for example, converting the prose definition of logical conjunction into the truth table as shown in Figure 3.3. Since there are four
combinations of P and Q, there are four rows in the table. Since there are
two variables, the table has three columns. The first two columns name
the first and second inputs, whereas the final column gives the truth value
generated by the logical conjunction of the two inputs.
Logical conjunction yields a value of true only when both of the
inputs are true. This result is intuitive since it closely follows the way
we informally use the term and when speaking. We intuitively understand statements like I am hungry and I am cold to be true only
when the statement I am hungry is true and I am cold is also true.
In every other case, we understand that I am hungry and I am cold
is false.
3.2.2.2 Disjunction (OR)
Logical disjunction, however, is not as intuitive since our informal use of
the word or is not as closely connected to the way it is formally defined.
We often pose two mutually exclusive possibilities and ask which of
those two possibilities actually occurred. We might, for example, ask
our friend Did you watch television or did you eat dinner? We would
expect them to tell us which of these two actions they actually took,
and not expect them to reply I did both or I did neither. We would
be even more surprised to hear them respond with Yes. I did watch
television or eat dinner. Logically, however, the correct answer to the
question you posed would be either yes or no. The answer would be yes
if your friend performed either or both of the two actions. The answer
would be no if your friend neither watched television nor ate dinner but
rather went jogging in the park. Logical disjunction is formally defined
by the truth table of Figure 3.4.
Conjunction
P Q P and Q
False False False
False True False
True False False
True True True
FIGURE 3.3 Truth table for logical conjunction.
Logic 69
Note that we define the result to be true if either of the inputs is true.
Said another way, logical disjunction yields a false value only when both
of the inputs are false. Given this definition, we now understand a statement such as I am hungry or I am cold to be false only when I am neither
hungry nor cold. If, for example, I am both hungry and cold, the statement
I am hungry or I am cold is understood to have a value of true.
3.2.2.3 Implication (IMPLIES)
Logical implication is perhaps the most challenging operator to master.
This operator captures the idea that if one thing is true, then some other
thing must also, by logical necessity, be true. For example, if the proposition
my car battery is dead has a value of True, this implies that the proposition my car wont start must also be true. In Boolean logic we would say
that My car battery is dead implies my car wont start. We might phrase
this informally as whenever my car battery is dead, my car wont start.
Generally, of course, we would use abbreviations to represent the simple propositions in which case we would write P implies Q where P is an
abbreviation of the proposition My car battery is dead and Q abbreviates
My car wont start. The truth table defining logical implication is given
in Figure 3.5.
Logical implication is a very important operator since it has properties that precisely express correct human reasoning. Unfortunately, logical
implication is perhaps the most poorly understood of the logical operators. We therefore describe a few important properties of logical implication in the following paragraphs.
In the proposition P implies Q we refer to P as the antecedent and
Q as the consequent. Consider the following two simple propositions and
their abbreviations.
Disjunction
P Q P or Q
False False False
False True True
True False True
True True True
FIGURE 3.4 Truth table for logical disjunction.
70 Computational Thinking for the Modern Problem Solver
P = My car battery is dead.
Q = My car wont start.
Consider the following compound proposition that establishes simple
proposition P as the antecedent to consequent Q.
P implies Q
This compound proposition has a value that is either True or False, and
the value of the proposition is dependent on the value of the two simple
propositions P and Q. We will carefully consider each of the four possible
combinations of inputs starting from the bottom of the truth table and
working our way to the top of the table.
1. P is True and Q is True. Consider the situation where we observe that
my car battery is dead and we also observe that my car wont start.
Given these observations it is logically consistent to claim that P implies
Q since it appears that the car wont start because the car battery is
dead. In this scenario, we understand that is logically consistent with the observed facts and therefore has a value of True.
2. P is True and Q is False. We now observe that the car will start (since
Q is False) and that the car battery is dead. The proposition that P
implies Q must therefore be false since this proposition is claiming that the car wont start whenever the car battery is dead. In this
scenario we understand that P implies Q is logically inconsistent
with the observed facts. Therefore, has a value of
False since it expresses the provably incorrect proposition that whenever the car battery is dead the car wont start.
Implication
P Q P implies Q
False False True
False True True
True False False
True True True
FIGURE 3.5 Truth table for logical implication.
Logic 71
3. P is False and Q is True. When the antecedent is false, there is no conclusion that can logically be drawn with respect to the consequent.
In this case, the statement that P implies Q has not been disproven
and therefore has a value of True. For example, the observation that
my car battery is not dead and that my car wont start does not
contradict the statement that whenever my car battery is dead my
car wont start. Perhaps the car wont start for some reason unrelated
to the car battery. Perhaps the spark plugs are polluted or the gas tank
is empty. Since there is no logical contradiction between the observed
situation and the statement that My car battery is dead implies my
car wont start we understand that is true.
4. P is False and Q is False. Again, since the antecedent is False, we understand that is True. In this situation, we observe
that my car battery is not dead and we also observe that my car will
start. It should be apparent that the implication is True since there is
no logical contradiction between what we observe and the proposition
that My car battery is dead implies my car wont start.
We define the converse of P implies Q to be Q implies P. The converse of a proposition is essentially the logical opposite. One of the properties of implication is that if an implication is true, the converse may not
be true. If, for example, it is true that my car battery is dead implies that
my car wont start we cannot logically conclude that my car wont start
implies that my car battery is dead. There are many reasons that my car
may not start and only one of those reasons is that my car battery is dead.
Consider the implication that Humphrey is a dog implies Humphrey is
a mammal. It is obvious that the converse is not necessarily true since
Humphrey is a mammal does not imply that Humphrey is a dog.
Although Humphrey might be a dog, Humphrey might also instead be a
cat, a lion, a whale, or even a person.
3.2.2.4 Equivalence ()
Variables P and Q are said to be equivalent if they have the same truth
value. The truth table for logical equivalence is given in Figure 3.6.
3.2.2.5 Logical Negation (NOT)
Logical negation is the only unary operator. This operator expresses the
obvious thought that if something is not true then it must be False, and
72 Computational Thinking for the Modern Problem Solver
if something is not False then it must be True. The truth table for logical
negation is shown in Figure 3.7.
3.2.2.6 Compound Propositions
When we evaluate a proposition, the goal is to determine the truth value
of the proposition. If the proposition involves only a single operator, we
can simply look up one row of a truth table to obtain the answer. Consider
evaluating the proposition
P or Q
for the situation when P = False and Q = True. We can evaluate the value
of P or Q by scanning through the disjunctions truth table, finding the
line that corresponds to P = False and Q = True and then reading the truth
value under the column heading P or Q.
To evaluate propositions that involve more than one operator, we can
apply the same process, but it must be applied once for every operator in
the proposition. Consider, for example, the proposition
P and (Q or R)
Negation
P not P
False True
True False
FIGURE 3.7 Truth table for logical negation.
Equivalence
P Q P Q
False False True
False True False
True False False
True True True

FIGURE 3.6 Truth table for logical equivalence.
Logic 73
for the situation where P = True, Q = False, and R = True. We first note
those parentheses are used to group the subproposition (Q or R). For this
reason, we first use the disjunction table to evaluate (Q or R) where Q
= False and R = True. The truth table for disjunction states that if the left
value is False and the right value is True, then Q or R has a value of True.
Once we have evaluated (Q or R) to True we can replace that subproposition by its value and continue our process of evaluation. We now
have the proposition
P and True
There is now a single logical operator and we complete our evaluation
by using the truth table for conjunction to find the value corresponding
to the case where the left value is true and the right value is true. We note
that the value is true. In other words, the truth value of True and (False
or True) is true.
When evaluating a proposition that involves more than one logical
operator you should normally proceed from left to right. The only exception to this general rule is when parentheses are used to group elements in
some other natural order. Consider, for example, the proposition
P and Q implies R
for the situation where P = True, Q = True and R = False. There are two
operators in this proposition and they should be evaluated from left to
right. The first step is to evaluate the subproposition P and Q for P =
True and Q = True. We find that True and True has a value of True. We
now evaluate the expression True implies R for R = True. We find that
True implies True has a value of True and hence the entire proposition
P and Q implies R has a value of True.
We can use parenthesis to group the operators differently and this
affects the order in which the operators should be evaluated. Consider, for
example, the different grouping of operators shown next for the situation
where P = True, Q = True, and R = False.
P and (Q implies R)
Since the implication operator is in parentheses, we must evaluate
that operator first. In our case we discover that True implies False
74 Computational Thinking for the Modern Problem Solver
has a value of False. We then evaluate the conjunction operator in the
proposition P implies False, or, since P = True, we evaluate True
implies False, which yields a value of False. From this example we see
that the meaning of a proposition can be changed by different groupings of the operators.
Truth tables can be used to express the meaning of any logical proposition.
To construct a truth table for some proposition you must do the following.
1. Make a list of each logical variable (abbreviation) that appears in the
proposition. If one variable occurs more than once in the proposition it should be included only once in your list.
2. Place a column in the truth table for every variable list your list. The
column heading should be the variable itself.
3. For the heading of the last column you should write the entire
proposition.
4. If there are N variables in your list, you must create 2N rows. Each
row represents a unique combination of values for the N variables.
5. For each row, determine the value of the proposition and place that
value in the last column.
Consider, for example, the proposition
P and not (Q or R)
We construct the truth table by first making a list of the logical variables
listed in the proposition. The logical variables P, Q, and R are the only
variables that occur and so our list contains only those three variables.
We now construct a truth table that has one column for each of these variables. In addition, the final column corresponds to the whole proposition.
Since there are three variables, we now construct 23
or 8 rows such that
each row corresponds to a unique combination of values over the variables
P, Q, and R. This table is shown in Figure 3.8.
It is preferable to arrange the rows in some orderly fashion. In this
example, you should note that the rightmost column alternates repeatedly
between True and False. The next column to the left alternates in a pattern
of two False values followed by two True values. The next column to the
left alternates at a rate that is half as frequent as the previous column.
Logic 75
The challenge is to complete the table such that the value of the proposition P and not (Q or R) is known for each possible combination of P, Q,
and R. In order to determine these values it is convenient to temporarily
include columns for each of the logical operators that must be evaluated
to determine the value of the whole proposition. These subparts should
be arranged according the order in which the operator will be evaluated.
Figure 3.9 gives an example of such a table.
P Q R P and not (Q or R)
False False False
False False True
False True False
False True True
True False False
True False True
True True False
True True True
FIGURE 3.8 Truth table for a logical proposition.
P Q R (Q or R) not (Q or R) P and not (Q or R)
False False False False True False
False False True True False False
False True False True False False
False True True True False False
True False False False True True
True False True True False False
True True False True False False
True True True True False False
FIGURE 3.9 The process of generating the truth table.
76 Computational Thinking for the Modern Problem Solver
The proposition contains three logical operators and hence there are three
columns to the right of the variables. Two of these columnsthe columns
corresponding to disjunction and negationare temporary and will not be
retained as part of the final table. The final column is generated by the conjunction operator and this column will be retained since the conjunction
operator is the last operator evaluated and generates the value of the proposition. Eliminating the temporary columns yields the truth table of Figure 3.10.
3.2.2.7 Logical Equivalence
Two propositions are said to be equivalent if they have the same truth
table. Consider, for example, the two propositions
not (P and Q)
(not P) or (not Q)
The truth table for each of these propositions is listed in Figure 3.11.
Since these two tables are identical, we know that the proposition not
(P and Q) is equivalent to the proposition (not P) or (not Q). When two
propositions are equivalent, they have the same meaning and are therefore interchangeable.
3.2.2.8 Tautologies and Contradictions
Any proposition that has a value of True regardless of the inputs is said to
be a tautology. Any proposition that has a value of False for all inputs is said
P Q R P and not (Q or R)
False False False False
False False True False
False True False False
False True True False
True False False True
True False True False
True True False False
True True True False
FIGURE 3.10 Final truth table for the proposition P and not (Q or R).
Logic 77
to be a contradiction. Since a tautology is always True, a tautology can be
understood as simply a long-winded way of expressing something that is
self-evident. Of course, a contradiction can be understood as a statement
that is always logically invalid no matter how you look at it. Tautologies
and contradictions should be avoided when writing propositions and they
should also be avoided in the normal course of human conversations since
such statements do not express any sort of productive line of reasoning. The
following propositions give examples of a tautology and a contradiction.
Tautology: P or not P
Contradiction: P and not P
Tautologies are often used in political debate and political rhetoric.
Consider, for example, the statement, If you elect me to be president
then I will serve as the elected president. This statement is simply a longwinded statement of the obvious. When expressed as a logical proposition,
the statement reduces to P implies P, which can be easily shown to be a
tautology by constructing the truth table.
When we think that our friend (or even our teacher) is saying something that does not make sense it is often because we think that they are
making a contradictory statement. Consider the following conversation
between two students in a computational thinking course.
Matthew: My new Internet connection is blazingly fast. I watched HD
movies all night.
Susan: Have you finished your computational thinking homework?
Matthew: No. My Internet connection is so painfully slow that I cant
download the one-page assignment.
P Q not (P and Q)
False False True
False True True
True False True
True True False
P Q (not P) or (not Q)
False False True
False True True
True False True
True True False
FIGURE 3.11 Two different propositions have the same truth table. These two
propositions are therefore said to be equivalent.
78 Computational Thinking for the Modern Problem Solver
We intuitively understand that Matthew is not making sense because
he has expressed a contradiction. The source of the contradiction is his
statement that his Internet connection is both blazingly fast and painfully slow at one and the same time. We can express this contradiction
as the contradiction P and not P where P abbreviates the statement
My Internet connection is fast. If a line of human reasoning is ever
shown to exhibit a contradiction, it is certain that the line of reasoning
is logically flawed. Valid reasoning requires that a proposition cannot be
both true and false at the same time; this requirement is referred to as the
law of noncontradiction.
3.3 APPLICATIONS OF PROPOSITIONAL LOGIC
Although you might expect physicists, mathematicians, and accountants
to use formal logic in their daily profession, you may be surprised to discover that a much wider range of disciplines also make common use of
propositional logic. In this section we will describe how propositional
logic is used by anyone who searches the Internet, electrical engineers,
database designers, and even graphic artists!
3.3.1 Search Queries
A web search engine is a software system to search for information on the
World Wide Web. Search engines work by downloading web pages and
recording each word or phrase that occurs on the page. Whenever users
want to know where they can find information about a topic, say logic,
they can type in the word logic and the search engine will return a list of
all web pages that contain the word logic.
A search query is a phrase that describes the information that the
user seeks to obtain. Many search queries are a single word such as
rose, logic, or platypus. Although single-word queries are sometimes effective, they often fail to produce the right type of information
because the word may be ambiguous or frequently used across many
different contexts.
Consider a situation where you live in a city that has a grocery
store named People. You would like to use a search engine to find the
phone number and the hours of operation for this store. You naturally
use the term people as a search query but find that your query does not
produce useful results. When this text was written, the top search engines
returned results such as the People Magazine website, Yahoos People
search page, the website of Peoples Bank, a Wikipedia article titled
Logic 79
People, a Wikipedia article devoted to a band named Peoples, and a
link to a web page devoted to the People of Walmart.
Simple single-word queries are often not specific enough to provide
useful results. Most search engines therefore allow you to construct more
specific search queries that narrow the focus of your query in a more useful manner. The Boolean operators AND, OR, and NOT are one technique
that is commonly used to narrow a search query.
3.3.1.1 Conjunction in Search Queries
By default, all search queries that use more than one word use conjunction. In other words, the search query returns web pages that contain all
the terms or phrases in the query. As an example, consider searching for
information about a high school classmate named Hannah Garcia. You
first decide to use the search query Hannah but the query returns a flood
of web pages related to Hannahs of all kinds; none of whom are related
to the Hannah Garcia that was your high school friend. You decide to
narrow your search by forming the two-word query Hannah Garcia. The
search engine understands this query to be the conjunction of the two
words. In other words, the search engine understands the query to mean
Hannah AND Garcia. The only pages that are returned by the search
engine are those web pages that contain both the word Hannah and the
word Garcia.
3.3.1.2 Disjunction in Search Queries
Unfortunately, you still cannot find any web page related to your high
school classmate Hannah Garcia. As you think about how to improve your
search results, you remember that she married someone with the surname
Mason. You realize that although she may still use the surname Garcia in
certain business contexts, she may instead use the surname Mason. You
therefore attempt to construct a search query that expresses the possibility that her last name is either Garcia or Mason. You initially think that
the search query Hannah Garcia Mason would be appropriate, but this
search query would be overly narrow since only pages containing all three
words would be returned as the search engine would interpret this query
to mean find all web pages that contain the words Hannah AND Garcia
AND Mason.
After some study you discover that search engines use an OR operator to express alternatives. The alternatives in this case are Garcia
and Mason. You therefore construct the search query Hannah AND
80 Computational Thinking for the Modern Problem Solver
(Garcia OR Mason). This query correctly expresses your desire to find web
pages that contain only one of the surnames Garcia or Mason but not both.
3.3.1.3 Negation in Search Queries
Perhaps the search query Hannah AND (Garcia OR Mason) returns
many web pages related to a well-known soccer player. You are certain
that your high school classmate is not a soccer player and therefore you
attempt to construct a search query that prevents soccer-related pages
from appearing.
Search engines use the NOT operator to exclude pages that contain certain words. You therefore construct the following search query: Hannah
AND (Garcia OR Mason) AND NOT soccer. This query will find all
pages that contain either the words Hannah and Garcia or the words
Hannah and Mason, while preventing any web page containing the
word soccer.
Negation is expressed in some search engines as a dash () immediately preceding the word that should be excluded. In this case, the search
query Hannah AND (Garcia OR Mason) AND NOT soccer would be
expressed as Hannah AND (Garcia OR Mason) AND soccer. Also note
that most search engines require the logical operators to be entered in all
capital letters. If the word is typed in lowercase, the search engine will
likely return all web pages related to the word and, for example, rather
than interpreting AND as an operator!
3.3.2 Digital Logic
Digital circuits are the physical components of a computing system. A
digital circuit is an electronic system that enables a computer to perform
arithmetic operations such as addition and multiplication among many
other operations. These digital circuits are typically constructed by combining logic gates in various ways. A logic gate is an electronic device that
implements a Boolean operator. In other words, a logic gate will have
inputs and produce a single output corresponding to the operator that it
implements.
Figure 3.12 shows two electrical circuits that implement the Boolean
operators AND and OR. For each case, a battery is connected to a lightbulb
and two switches. For the AND circuit, it is apparent that both switches
must be closed in order to light up the bulb. If either one of the switches in
the OR circuit is closed, the lightbulb will be illuminated.
Logic 81
Logic gates are usually implemented using transistors as switches. In
the context of digital logic, a battery can be thought of as a power source
with a voltage level of 1. Since the switches either supply full power or no
power to the output device, there are only two signal levels present in the
circuit. These two signals are usually denoted using 0, which corresponds
to no power or False and 1, which corresponds to full power or True. These
logic gates are usually drawn using the symbolic forms of Figure 3.13.
While a simple proposition can be represented by one of these logic
gates, compound propositions can be represented as a combination of
these simple logic gates. Digital circuits are therefore equivalent to compound Boolean propositions. Consider using logic gates to implement the
compound predicate
P and not (Q or R)
Since the or operator is enclosed in parenthesis, that part of the
expression is performed first. In a logic circuit, this implies that the or
gate occurs first in the path of the signal. The resulting expression, (Q or R)
is then inverted and finally fed into the and gate to produce the result
shown in Figure 3.14.
When designing an electronic circuit we would prefer to use as few
gates as possible. Since each gate increases the cost of the system, minimizing the number of logic gates results in a less expensive system. Also,
fewer gates often also means that the circuitry is faster since a digital signal
A B
A
A and B A or B
B
FIGURE 3.12 Electrical circuits where switches describe the logical input and
the state of the lightbulb denotes the output.
P
Q
P
Q
P
P and Q P or Q not P
FIGURE 3.13 Schematic notation for the Boolean logic gates AND, OR, and
NOT.
82 Computational Thinking for the Modern Problem Solver
does not need to travel through as many gates. Since digital circuits are
expressions of Boolean propositions, it is natural to use Boolean algebra to
design and analyze complex digital circuitry.
One final example of a basic digital circuit is a circuit that performs an
equivalency check on two inputs. Figure 3.15 has an output of True whenever P = Q, otherwise the output is False. This circuit encodes the concept
that P is only equal to Q whenever (a) both P and Q are True or whenever
(b) both P and Q are False.
3.3.3 Image Compositing
A graphic designer is a professional who works with images and fonts to
create the graphics for such things as textbooks, brochures, movies, and
web content. Since the core responsibility of the designers job is to present
visual information in a compelling manner, graphic designers are highly
skilled at creating and editing digital images. Many important editing
functions used daily by the graphic designer are direct applications of formal logic.
Digital images can be thought of as a grid of small, colored cells known
as pixels that when viewed from a sufficient distance will blend together
to form a high-quality picture. Binary images are digital images composed
of only white or black pixels. Although binary images are not colorful,
they nonetheless can convey a great deal of information and visual detail.
P Q
FIGURE 3.15 Equivalence circuit. The output is 1 (True) whenever P is equivalent to Q.
P
Q Q or R not (Q or R)
P and not (Q or R)
R
FIGURE 3.14 Using logic gates to implement the predicate P and not (Q or R).
Logic 83
For example, consider the image of Figure 3.16 that shows a binary image
derived from the Mona Lisa.
Since there are only two colors in a binary image and only two logical values, we can associate a color with a logical value. For this discussion we will associate the color black with logical value True and the color
white with the logical value False. We can now apply logical operations
on colors using the logical operators AND, OR, IMPLIES, EQUALS and
NOT. Since the logical values are associated with colors, the truth tables
for these operators can be expressed using the colors black and white as
shown in Figure 3.17.
Graphics software systems give artists the ability to construct complex shapes and pictures by combining simpler shapes. Digital compositing is the process of combining two shapes or images to create a more
FIGURE 3.16 Binary image of the Mona Lisa.
P Q (P and Q) (P or Q) (P implies Q)(P equals Q) (not Q)
FIGURE 3.17 Truth tables using colors.
84 Computational Thinking for the Modern Problem Solver
complex image. Some compositing techniques are direct applications of
propositional logic where colors are used in place of truth values.
If we assume that P and Q are binary images, we can then create composite images by writing a proposition that includes logical variables P and
Q. These composite images are constructed by applying some logical operator to every pixel in the images that are being composited. Figure 3.18
gives an example of this technique. Images P and Q can be composited
and expressed as predicates to form a variety of other binary images.
3.3.4 Database Queries
Databases are software systems designed to efficiently store enormous
amounts of data such that pieces of data in the database can be very quickly
located and retrieved. Most databases store information in tables such that
each row of the table contains a set of data that belongs to a single record.
Each column of the table defines a field and every cell of the table contains
one field for one record of data.
Database systems are an indispensable component of almost every software system and used in almost every profession. For example, the No
Fly List is a large database of individuals who are not allowed to board
a commercial aircraft, the National Do Not Call Registry is a database
containing the names of individuals that telemarketers are not allowed
to solicit, the National Sex Offender Registry is used by law enforcement
to track the location of convicted sex offenders, every bank and financial institution maintains a database of clients and accounts, Wikipedia
P not P P and Q not P or Q
Q not Q P or Q P or not Q
FIGURE 3.18 Image compositions using logical operators.
Logic 85
maintains a database of articles, biologists maintain large databases of
DNA sequences, and politicians maintain large databases of registered
voters.
Consider the case of a political lobbyist who wants to raise funds for
some political cause. The lobbyist wants to concentrate all of their fundraising efforts on a narrow group of likely donors and has been given
access to a database of individuals who have made similar donations in
the past.
The structure of the database is given in Figure 3.19. Since there are six
columns we understand that each record consists of six fields. Those fields
are named First, Last, Age, Amount, State, and Party. There are seven rows
and hence we understand that the table contains seven records. In this case,
each record contains a persons name, the amount donated, their state of
residence, and their party affiliation. The political party is denoted as D for
Democrats, R for Republicans, T for the Tea Party, and I for all independents.
Perhaps the lobbyist wants to solicit individuals who have made similar
donations of at least $500. The list of potential donors can be generated by
selecting a subset of the individual donors in the database. In this case,
the lobbyist will generate this list by scanning down the column labeled
Amount and selecting those rows having a value of at least 500 in the
amount column. Since there are only seven records in our nave example,
generating the list of potential donors is easily done, but most real-world
databases contain many millions of records. The enormous size of data in
Donor Table
First Last Age Amount State Party
William Shell 61 1,300 WI D
Lisa Dough 19 125 WY T
Helen Lobby 35 1,200 CA R
Reggie Green 33 800 NY R
Harvey Levirage 41 500 NY I
Robin Round 32 200 NY D
Jennifer Dichali 38 650 WI D
FIGURE 3.19 A relational database table.
86 Computational Thinking for the Modern Problem Solver
most real-world databases requires sophisticated software to extract and
analyze data of interest.
Fortunately, databases are designed to efficiently locate records in
response to well-formed queries. Although somewhat similar to a web
search, a database query requires more precise structure and is generally
written in a language known as SQL, which is short for Structured Query
Language. Records in a database are located by issuing a select statement.
The general form of a select statement is given as
SELECT field1, field2, , fieldN FROM table WHERE criteria
where the italicized elements represents the details that control what data
is retrieved. Consider writing an SQL query to select the names of donors
who have contributed at least $500. Since we are only interested in the
names of the individuals, we would select only the First and Last fields. We
are selecting data from the Donor table and the criteria that determines
which elements to select is expressed as Amount >= 500. The proper SQL
query is given as
SELECT First, Last FROM Donor WHERE Amount >= 500
The criterion of this select statement is a simple logical predicate that
locates and retrieves only those records of interest to the lobbyist. The
result of the select statement is a list of five donors: William Shell, Helen
Lobby, Reggie Green, Harvey Levirage, and Jennifer Dichali. Consider,
however, a scenario where the lobbyist wants to specifically target only
those donors who are under 40 years of age and have contributed at least
$500 in the past. This requires a more sophisticated criterion; a criterion
that is expressed as a compound logical predicate and produces a list of
the three donors: Helen Lobby, Reggie Green, and Jennifer Dichali.
SELECT First, Last FROM Donor WHERE Amount >= 500 AND Age
< 40
Perhaps the lobbyist wants to specifically target only those donors who
live in either the coastal states of New York or California regardless of their
age or their past donations. The appropriate SQL query is expressed as
SELECT First, Last FROM Donor WHERE State = NY OR State = CA
Logic 87
Note that the terms NY and CA must be enclosed in quotations to distinguish those elements as merely textual elements. This query produces
a list of four donors: Helen Lobby, Reggie Green, Harvey Levirage, and
Robin Round.
For our final example, consider an SQL query to locate every donor
that is under 40 years of age, has donated at least $500 in the past, and
lives in either New York or California. The table contains only two such
donors: Helen Lobby and Reggie Green. The SQL query to generate this
list is given as
SELECT First, Last FROM Donor WHERE Age < 40 AND Amount >=
500 AND (State = NY OR State = CA)
The ability to precisely express database queries as logical predicates is
a vital skill for anyone who works with large amounts of structured data.
3.3.5 Software Requirements
When a software engineer is hired by a client to write software, the first and
often the most difficult aspect of the job is to define as precisely as possible
what the software should do. The process of defining what a piece of software should do is known as requirements engineering. Typically, the software engineer will schedule a series of meetings with the client and spend
hours talking to everyone interested in the software that is being created.
The software engineer will make sure that every detail of everything that is
discussed in these meetings is written down and precisely defined so that
there is one common understanding of every aspect of the system.
The end result of requirements engineering is a document known as
the software requirements document. This document is a very precise definition of what the software should do once it has actually been written.
The software requirements document often serves as a formal contract
between the client and the software engineer, and hence both the client
and the software engineer must both agree that the software requirements
document is a precise definition of what the software should do. This
necessitates that the document should also written in such a way that both
the client (often a nontechnical person or company) and the engineer are
able to fully understand.
Logical propositions are often used to define important functions of a
large software project. Consider, for example, a corporate client that has
hired a software engineer to write software to control an elevator system
88 Computational Thinking for the Modern Problem Solver
for a small four-floor office building. The elevator has two doors that are
known as the front and the rear door. The front doors are usable only
on the first two floors, and the rear doors are usable only on the top two
floors. An interview session between Germaine, the software engineer,
and Aditi, the main corporate contact, might go something like the following dialogue.
Germaine: What should happen when the open door button is pressed?
Aditi: The door should open.
Germaine: The front door or the rear door or both?
Aditi: The front door should open if the elevator is on either floor 1 or 2, otherwise the rear door should open.
Germaine: What if the open door and close door buttons are pressed
at the same time?
Aditi: Hmmm. I hadnt thought about that. I guess nothing should happen.
Germaine: What if the elevator is moving between two floors and the
open door button is pressed?
Aditi: Nothing should happen.
Germaine: What if emergency personnel have inserted a key to manually
override the software control system. In that case, what should
happen when the open door button is pressed?
Aditi: Hmmmm. Thats a good question. I guess that both the front and
rear doors should open regardless of which floor the elevator is
on or even if the elevator is moving between floors.
After several discussions, Germaine will then include a specification for
the open door function of the elevator. This function will likely involve
a number of logical predicates that very precisely define what should happen when the open door button is pressed. The functionality might be
described in the following manner.
Description: The elevator contains both an open door button and
a key slot that is intended for the use of emergency personnel. The
following specification defines what the control software should do
when the open door button is pushed.
(FLOOR=1 OR FLOOR=2) AND (NOT MOVING) AND
BUTTON_PUSHED IMPLIES FRONT_DOOR_OPENS
Logic 89
(FLOOR=3 OR FLOOR=4) AND (NOT MOVING) AND
BUTTON_PUSHED IMPLIES REAR_DOOR_OPENS
(EMERGENCY_KEY_INSERTED AND BUTTON_
PUSHED) IMPLIES (FRONT_DOOR_OPENS AND
REAR_DOOR_OPENS)
In all other cases, the system must do nothing
Software systems that might cause significant harm if they operate
improperly are known as safety-critical systems and are specified using
very precise mathematics. Software that controls an artificial heart, an
insulin pump, a medical CT scanner, a national air-traffic control system, the automatic pilot software on a large commercial jetliner, or the
control software of a nuclear power plant are all known as safety-critical
systems. Formal methods are a set of mathematically rigorous techniques
for the specification and development of safety-critical software systems.
Although most software systems are specified using a mixture of mathematical formalisms and nonmathematical descriptions, the more critical
the system, the more formal the specification must be.
TERMINOLOGY
and
antecedent
binary image
binary operator
Boolean logic
compound proposition
conclusion
conjunction
consequent
contradiction
converse
database
deductive logic
digital compositing
digital image
disjunction
equivalence
evaluate
field
implication
implies
inductive logic
90 Computational Thinking for the Modern Problem Solver
EXERCISES
1. Name the two logical values.
2. For each item, identify whether the item is a well-formed proposition.
a. P NOT Q
b. NOT P OR Q
c. NOT P NOT Q
d. P AND NOT Q
e. P AND OR Q
f. NOT P AND NOT Q
3. Give a well-formed proposition that is equivalent to (P IMPLIES Q).
law of noncontradiction
law of the excluded middle
logic
logic gate
logical values
negation
not
operator
or
premise
proposition
record
requirements engineering
search query
simple proposition
software requirements
document
SQL
structured query language
syllogism
symbolic logic
tautology
truth table
truth values
unary operators
well-formed propositions
Logic 91
4. Give the truth table for each of the following propositions.
a. P AND (Q IMPLIES R)
b. (P OR Q) AND R
c. P OR (Q AND R)
d. NOT (P AND (Q OR R))
5. Give an interesting web query that uses logical conjunction, disjunction,
and negation in a substantive manner to produce an interesting result.
6. Draw a digital circuit for each of the following propositions.
a. (P OR Q) AND R
b. P OR (Q AND R)
c. NOT (P AND (Q OR R))
7. Draw a digital circuit for the proposition that (P IMPLIES Q)
8. Consider the following database table. The database is used by a
local falconry club to track its members. The Paid column indicates
whether a person has paid dues for this year, the Gender column
has the entry U for those members who have signed up but not yet
provided their gender information. For each of the following criteria,
write an SQL query, following the examples given in this chapter, to
generate the desired result.
a. The first and last name of all female members
b. The e-mail addresses of those members who have paid their dues
c. The e-mail addresses of those members under 21 who have not
paid their dues
d. The first and last name of all members who are either male or
have an unknown gender
e. The e-mail address of all dues-paying members who have an
unknown gender
92 Computational Thinking for the Modern Problem Solver
Member Table
First Last e-Mail Paid Gender Age
Jason Lin [email protected] Y M 32
Hannah Flynn [email protected] N F 19
Jordyn Ash [email protected] Y U 59
Reginald Holt [email protected] Y M 31
Sophia Grace [email protected] Y F 29
Ella Peters [email protected] .edu N F 23
Dakota Flynn [email protected] N U 19
Aaron McGregor [email protected] Y M 59
93
Chapter 4
Solving Problems
Its not that I am so smart, its just that I stay with problems longer.
ALBERT EINSTEIN
OBJECTIVES
To examine problem definition as the beginning of all good problem
solving
To explore functional requirements as the core of algorithmic problem definitions
To examine several ways that logical reasoning is applied to software
development, including cause-effect relationships, deductive reasoning, and inductive reasoning
To understand that programming is an activity that often relies upon
knowledge of patterns and that the five basic patterns of control
flow are sequences, selection, repetition, control abstraction, and
concurrency
To understand the central role algorithms play in computational
problem solving and explore many forms of algorithms
To examine divide and conquer as a key problem-solving strategy,
useful in outlining and top-down design
To explore prototyping as a form of decomposition that is well suited
to solving many of todays problems
To consider the impact of alternative approaches to data decomposition, such as linear searching as opposed to binary searching
To explore many forms of abstraction that are significant to computer science, including control abstraction, class diagrams for data
abstraction, and use-case diagrams for definition abstraction
94 Computational Thinking for the Modern Problem Solver
It has been said that computer scientists are modern-day problem solvers.
So it is impossible to understand computational thinking without understanding the problem-solving skills and techniques of the computer scientist. Of course, problem solving did not begin with computers, nor are
computers essential to solve many problems; and, of course, the problemsolving skills common to computer scientists are useful far outside the
world of computers.
It would be impossible to capture all the ways that computer scientists solve problems, but there are four strategies regularly employed by
computer scientists that are at the core of this modern style of problem
solving:
1. Problem definition
2. Logical reasoning
3. Decomposition
4. Abstraction
In addition to their significant utility in computational problem solving,
each of these techniques has numerous applications aside from computer
science.
4.1 PROBLEM DEFINITION
Like the scientific investigation process begins with a hypothesis, software development begins with a careful problem definition. The problem
definition specifies what task(s) are to be performed by the associated
software. The problem definition also serves as the software developers
goal. Without such a goal it is impossible to know whether the problem
has been solved, impossible to say whether a computer application is
correct.
Software engineers recognize at least three major phases to the process
of developing software:
1. Analysis
2. Design
3. Implementation
Solving Problems 95
The latter two phases involve the creation of a problem solution, but
analysis is all about defining the problem. In some sense analysis is the
most important phase, because, as every good software engineer knows,
successful design and implementation is only possible given adequate
analysis.
Problem definition involves more than just computer scientists. Anyone
who contracts the creation of software (that person is known as the customer in software engineering terminology) must assist in analysis in
order to convey the intended problem definition. In fact a problem definition is the core of the legal agreement between customer and software
developer.
A properly engineered software problem definition consists primarily
of a list of requirements. As the name implies, a requirement specifies one
essential aspect of the software. Requirements are further divided into
two types: (1) functional requirements to specify the particular task(s) the
software must perform and (2) nonfunctional requirements to define other
characteristics and constraints related to the software. Nonfunctional
requirements include expectations for things like reliability, safety,
security, performance, delivery, and help facilities. These nonfunctional
requirements are useful; however, this presentation focuses on functional
requirements because these form what most of us think of as the software
problem definition.
As an example of functional requirements, consider a computer application to play videos. We will call this application Video Player. Informally,
this application plays a video with buttons that allow the user to play or
pause the video, as well as to raise or lower the sound volume. Figure 4.1
contains some of the functional requirements for this video player. The
sample functional requirements are numbered V1 through V4. In this
case each functional requirement corresponds to the action of a single
user button shown to the right of the requirement.
A good list of functional requirements must be
Clear
Consistent
Complete
96 Computational Thinking for the Modern Problem Solver
A clear requirement is one that is easily understood in the same way
by all customers, users, and developers. Clear requirements need to be
unambiguous and precise. Generally, a good functional requirement can
be translated into a logical proposition. For example, in requirement V2
the statement, If the video has already finished playing, then this button
has no effect can be translated into the expression F implies N, where F
denotes the condition that the video has finished playing and N denotes a
no change kind of action.
Related to the property of clarity is the need for functional requirements that are consistent. Consistent requirements are those that do not
Index: V1
Name: Play
Action: Clicking the play button (see image to the right) causes
the video to begin playing. If the video was just paused, then
playing the video resumes at the point of pausing. If the video
has yet to start playing, then a new computer window is created and the video begins playing in the window. So long as
the video is playing the pause/play button functions as a pause button,
displaying a pause button image.
Index: V2
Name: Pause
Action: Clicking the pause button (see image to the right) causes
the video to pause at the current play location. If the video has
already finished playing, then this button has no effect. Clicking
the pause button causes the pause/play button to function as a
play button, displaying a play button image.
Index: V3
Name: Increase Volume
Action: Clicking the increase volume button while the volume is less
than the maximum 80 dB level causes the volume to increase by
5 dB Clicking the increase volume button while the volume is at
the 80 dB level does nothing.
Index: V4
Name: Decrease Volume
Action: Clicking the decrease volume button while the volume is
greater than the silent (0 dB) level causes the volume to decrease
by 5 dB Clicking the decrease volume button while the volume is
at the silent level does nothing.
FIGURE 4.1 A few functional requirements for a video player app.
Solving Problems 97
contradict one another. In the example, it would be inconsistent to include
a fifth requirement that states, When the video is playing and reaches the
end, it immediately restarts playing with the play/pause button functioning as a play button. This statement is inconsistent with V1, because it
contradicts V1s specification that the play/pause button should function
as a pause button when videos are playing.
The third property of good functional requirementscompletenessis
perhaps the most elusive. It takes careful consideration to be certain that
every possible scenario has been considered and explained in one or more
requirement. Two scenarios that should always be included for completeness are how the application begins and ends its execution. The requirements from Figure 4.1 could be considered incomplete for overlooking
these situations. Figure 4.2 provides two more functional requirements to
rectify this deficiency.
Another way that functional requirements may lack completeness
is when they fail to consider all possible combinations of situations. A
good way to analyze for adequate completeness is to construct a stateactivity table that lists all possible application states against all possible user actions. Figure 4.3 illustrates with such a table for the Video
Player.
Index: V5
Name: Run Application
Action: e Video Player application starts executing
automatically whenever the user double-clicks on an
associated video file. As this execution begins, the
application displays a window containing the control
panel, like the image to the right. is control panel
remains until the user chooses to quit the application. If the application is executing, other video file
double-clicks are ignored.
Index: V6
Name: Quit Application
Action: Anytime that the Video Player application is executing the user may
double-click within the region of the video display. Such a double-click causes
QUIT and CONTINUE. If the user clicks the QUIT button, then the application quits executing. If the user clicks the CONTINUE button, then the video continues
FIGURE 4.2 Functional requirements to start and quit the video player app.
98 Computational Thinking for the Modern Problem Solver
The rows of a state-activity table come from potential user actions. The
user can click any of the four buttons (i.e., play, pause, increase volume, or
decrease volume). The other two user actions are to double-click a video
file icon or to double-click an active video display window.
The columns of the table represent the different potential states of the
application. The table in Figure 4.3 identifies four different states: (1) the
Video Player application has not yet started to execute; (2) the application
is executing but currently paused; (3) the video is playing; or (4) the video
has been playing but reached the end of the video.
The state-activity table sometimes contains cells that are impossible. In
the table of Figure 4.3 such impossible cells are indicated by a gray color.
For example, the Video Player control panel is not visible until the application begins to execute. Therefore, it is impossible for the user to click any of
the buttons of the control panel while in the App Not Executing state. The
remaining impossible states occur because of the way the control panel
works. Functional Requirement V1 specifies that when a video is playing
the pause function is active, making it impossible to click the play button.
Similarly, Requirement V2 states that clicking the pause button causes the
App Not
Executing
Video
Paused
Video
Playing
Video
Finished
Click Play V1
Click Pause V2 V2
Click Increase V3 V3 V3
Click Decrease V4 V4 V4
Double-click video
file
V5 V5 V5 V5
Double-click
video window
V6 V6 V6
User Actions Application States
FIGURE 4.3 A state-activity table for the video player app.
Solving Problems 99
control panel to display on the play button, making another click of the
pause impossible.
Once the impossible cells of the state-activity table have been determined, the remaining cells should all be fully defined by one or more
functional requirement. Figure 4.3 illustrates by entering the number for
each requirement within the cell(s) to which it applies. In other words
Requirement V6 defines what occurs when the user double-clicks the
video display window when the video is paused, playing, or finished.
A state-activity table for a complete set of functional requirements contains requirements in every cell except those that are impossible. Figure 4.3
shows that there is something incomplete about the requirements for the
Video Player application, because the upper right cell is blank. The problem is that the requirements do not really explain what occurs when the
video has played to completion and the user clicks the play button. (This
is possible, because the user could have clicked the pause button after the
video finished, and Requirement V2 specifies that this would cause the
control panel to display the play button.) Perhaps the play button should
restart the video; perhaps it should terminate the application; or perhaps
the play button should do nothing in the video finished state. The issue
is that the Video Player functional requirements need to be altered to
explain the desired functionality in order for these requirements to be
considered complete.
4.2 LOGICAL REASONING
The second of the four important problem-solving strategies for a computer scientist is logical reasoning. In Chapter 2 we discovered the close
relationship of logic and computing in part resulting from representing
true or false as a single bit of computer memory. But the usefulness of logical reasoning extends well beyond the obvious connection to computer
hardware. In fact, logic plays a role throughout the problem-solving process of software development.
As explained in Section 4.1, the functional requirements of a good
problem definition are English forms of logical statements. This is evident
in the use of English constructs such as if then that translates into the
logical implies operation.
Logic, as used in functional requirements and essential at the start
of software problem solving, is equally necessary at the end. Virtually
all computer software depends upon some form of logical instructions
100 Computational Thinking for the Modern Problem Solver
because an executing program must make choices. The program controlling an online website must choose when to bill a customer. The
program in your digital camera chooses how long to leave the shutter
open when taking a picture. The program controlling your portable
music player chooses which song to play next. Each of these choices is
accomplished with computer instructions that are a programmatic form
of logic. Most programming languages use a so-called IF instruction for
this purpose:
IF the user has struck the Confirm Purchase button, THEN initiate
billing procedures.
IF the camera sensor detects adequate exposure, THEN close the
camera shutter.
IF a song has just finished playing, THEN begin playing the next
song in the playlist.
IF instructions force a programmer to think in logical ways, to consider
a computer program as a complex collection of cause-effect relationships.
A cause-effect relationship consists of a logical condition (the cause) that
forces the program to perform some task (the effect). Figure 4.4 contains
four cause-effect relationships commonly used by computer programs.
Much of the work of computer programming is identifying these kinds of
cause-effect relationships and translating them into instructions.
The ability to apply general rules to particular situations is known as
deductive reasoning. This kind logical reasoning was made famous in the
Cause Effect
User name and password have been entered Check to see if users name and password are
valid
User clicks the close button on a window Remove the closed window from the display
Laptop battery charge below 10% Pop up a window warning user of low power
A new e-mail message arrives from the
Internet
Ring a bell to notify the user
FIGURE 4.4 Some typical cause-effect relations from programs.
Solving Problems 101
fiction of Sir Arthur Conan Doyle regarding a master at deduction named
Sherlock Holmes. Following is an excerpt from The Sign of Four [1]. In
this quote, Sherlock Holmes is talking to Dr. Watson explaining how he
deduced that Watson had been to the post office recently.
It is simplicity itself, he [Holmes] remarked, chuckling at my
surprise,so absurdly simple that an explanation is superfluous; and yet it may serve to define the limits of observation and of
deduction. Observation tells me that you have a little reddish mold
adhering to your instep. Just opposite the Seymour Street Office
they have taken up the pavement and thrown up some earth which
lies in such a way that it is difficult to avoid treading in it in entering. The earth is of this peculiar reddish tint which is found, as far
as I know, nowhere else in the neighborhood. So much is observation. The rest is deduction.
In this example, Holmes has deduced that Watson went to the post office
by using rules such as (1) walking on freshly thrown earth tends to stick to
shoes and (2) eliminating all other possibilities makes the remaining one
true. Holmes applied these rules to this specific case, as do modern-day
forensic experts who apply laws of science.
Deduction is often used when applying a mathematical axiom, law, or
theorem to a particular case. For example, when considering a right triangle the Pythagorean theorem states that A2
+ B2
= C2, where A and B
are the lengths of the triangle legs and C is the length of the hypotenuse.
From the Pythagorean theorem we can deduce the distance from opposing corners of a rectangular room that is 12 feet wide and 16 feet long is
20 feet. Since 122
+ 162
= 400 = 202
deduction allows us to conclude that
the distance is 20 feet.
Computer scientists use deduction in many ways. For example, a common rule in algorithms is that for certain problem solutions it is critical
that one task occur before a second task; this idea of one thing following another is called a sequential form of execution because the tasks
must occur in sequence. A software developer applies knowledge of this
sequencing when encountering a problem such as the software to send an
e-mail message. The task of sending a message must be preceded by the
task of specifying the recipients address. A valid algorithm must ensure
such task ordering.
102 Computational Thinking for the Modern Problem Solver
For example, consider the integer variables itemCost and priceWithTax, and an algorithm consisting of the following sequence of three
instructions:
priceWithTax 0
itemCost 100
priceWithTax itemCost + itemCost *.055
Executing these three instructions in sequence, that is to say from
first to last and one at a time, results in the value 105.5 assigned to priceWithTax. However, rearranging the order of the same three instructions
changes the algorithm. For example, consider the following algorithm,
using the same three instructions:
itemCost 100
priceWithTax itemCost + itemCost *.055
priceWithTax 0
When this second algorithm executes, the resulting value assigned to
priceWithTax is 0. Such subtleties point out the importance of understanding even something as simple as the order of a sequence.
Often the rules used by computer scientists are more like patterns. As
a first illustration of an algorithmic pattern, consider the problem of swapping the content of two variables. Figure 4.5 contains a pattern for a swap
algorithm that swaps (interchanges) the content of two variablesvarA
and varBusing a third variable, temp.
To illustrate how a programmer can use this pattern as a kind of
rule, suppose we have two variables: myDog and yourDog. Lets further
assume that myDog stores the name Fido initially, while yourDog stores
Rover. Now suppose we want to swap these variables so they store the
opposite names. We can use the pattern from Figure 4.5 as a general rule
and deduce a correct algorithm by substituting variable names (myDog
is substituted for varA and yourDog for varB). This substitution results in
the following algorithm:
temp varA
varA varB
varB temp
FIGURE 4.5 The swapping pattern.
Solving Problems 103
temp myDog
myDog yourDog
yourDog temp
Lest you think that patterns are unimportant. Think what would happen if
programmers did not know about the swap pattern and incorrectly assumed
that the following algorithm would work to swap myDog and yourDog:
myDogyourDog
yourDog myDog
Swapping illustrates one kind of algorithmic pattern. Another, more
general, pattern of software execution is known as repetition. Repetition is
used anytime a task needs to be repeatedly performed. Repetition is common in computer programs because one of the things that the computer
can do well is to repeat some process, no matter how mundane, over and
over. Software developers might recognize a pattern of repeating something five times and apply this pattern to selecting a basketball team or to
dealing a five-card poker hand.
Patterns are not restricted to forms of program execution. There are
patterns for successful software testing, patterns for ways to provide better software security, patterns of different software performance. Indeed,
most of this book can be viewed as an examination of foundational patterns of computation, including the patterns of logic found in Chapter 2.
Another way to think about deduction is to consider it a form of specialization. In deduction we apply our knowledge of more general rules,
theorems, or patterns in order to solve a specific problem. So deduction
works from the general to the specific. But it is equally important for a
computer scientist to be able to work from the specific to the general; this
is another application of logic, known as inductive reasoning.
Inductive reasoning occurs during the process of recognizing the generalities. For example, many software designs use the idea of separating an
algorithm into three components:
1. Software for communicating with the user
2. Software for retrieving and storing data
3. Software for calculating results based on user input and/or
retrieved data
104 Computational Thinking for the Modern Problem Solver
This pattern is so common that it is known as a 3-tiered software architecture. How did we discover this pattern? Such patterns are usually
noticed by astute observation that different successful solutions actually
use the same general framework
Why is it important to begin to think in terms of 3-tiered software? The
answer to this question lies in part with modern computer hardware divisions. Typically, you use your computer to perform a task such as change
your personal data on a social networking site. You are communicating
with your personal computer (Tier 1), while the changes must occur on
the computer owned by the social network company (Tier 3). For efficiency and other reasons, large computer installations store most data on
separate database computers (Tier 2). Since three different computers are
likely to be involved in processing your social network pages, it makes
sense that the software be subdivided into three parts or tiers.
Knowledge of the patterns used in computer science is not only important to computer scientists. For example, knowing about 3-tiered architectures is helpful in understanding that performance of a computer
application depends upon the performance of three different systems; any
one of these systems could be a bottleneck. Similarly, the 3-tiered architecture has significant implications for data confidentiality.
4.3 DECOMPOSITION: SOFTWARE DESIGN
When software engineers spend time seeking out cause-effect relationships, as discussed in the previous section, they are also using another
common problem solving strategy: decomposition. They are decomposing
the problem into individual relationships.
Decomposition techniques are often called divide and conquer strategies. The idea is to approach a single problem by separating (dividing) it
into its constituent subproblems, and then to solve (conquer) each subproblem individually, as depicted in Figure 4.6. Often the subproblems
can also be considered as individual problems, and the strategy can be
repeated to divide and conquer them.
As an example of this divide and conquer strategy, consider the problem of making a pizza, depicted in Figure 4.7. Notice that the larger problem of making a pizza can be thought of as a collection of six subproblems:
(1) making a crust, (2) making and spreading sauce, (3) spreading cheese,
(4) spreading toppings, (5) baking, and (6) slicing. A divide and conquer
strategy could begin by identifying these six subproblems, then solving
the larger problem by solving each of the individual smaller subproblems.
Solving Problems 105
Computer scientists did not discover the concept of divide and conquer.
Evidence of this idea is found in the oft-quoted Aesops fable regarding the
bundle of sticks. This fable dating back to ancient Greece, around 600 BC,
tells the story of a father who teaches his sons a lesson. The father asks each
son to break a large bundle of sticks that are bound together with string.
When the sons discover they are not strong enough to break the bundle
as a unit, the father tells them to untie the bundle and break the sticks
individually, which they are able to do. The moral of the fable is that many
times it is easier to solve a large task by separating it into smaller tasks and
solving the smaller tasks, by dividing and conquering.
Some of the reasoning behind the wisdom of divide and conquer was
explained in a paper written in 1956 by a psychologist named George
Miller [2]. The essence of Millers work is that the human brain is rather
limited in its reasoning abilities and that for some kinds of thinking the
human memory is limited to 7 2 items. In practical terms this means
that many problems are too complex for the human mind, unless they are
approached in terms of simpler partial problems.
Decomposition is frequently taught as a technique for writing, known
as outlining. The basic notion of outlining is to organize a work beginning
Problem
Sub-problem 1 Sub-problem 2 Sub-problem N
FIGURE 4.6 Divide and conquer means to separate a problem into subproblems.
Make Pizza
Make and
Spread Sauce Make Crust Spread Cheese Spread Toppings Bake Slice
FIGURE 4.7 Decomposing the problem of making a pizza.
106 Computational Thinking for the Modern Problem Solver
by decomposing the entire work into its main ideas. Each of the main tasks
might be divided into subpoints, like dividing problems into subproblems.
Outlining can continue by decomposing any appropriate subpoint into its
own subpoints. The standard notation for outlining uses Roman numerals
to index the main tasks, capital letters for the first-level subpoints, numbers for second-level subpoints, small letters for third-level subpoints, and
so forth. Figure 4.8 illustrates this.
Section 4.1 explained that software engineering involves three primary
activities: analysis, design, and implementation. As described earlier,
analysis seeks to define the problem. The implementation activity seeks to
create the final software. Design work has always been a bit more difficult
to explain. In essence the design work is any part of software development
intended to progress from the problem definition, or part of the definition,
toward but not including writing the final code. Sometimes the design
process creates parts of the program; sometimes it results in diagrams.
Frequently, the goal of design is to produce an algorithm that can be translated into the final program.
An algorithm is defined to be a collection of instructions for performing some task. Computer programs are clearly algorithms, but not all
algorithms can be executed by computers. For example, consider cookie
recipes. If you search the Internet for the recipe for your favorite cookie,
you will discover many algorithms; a good cookie recipe (algorithm) is a
I. Main idea
A. Sub-point of idea I.
1. Sub-point of I.A.
2. Sub-point of I.A.
B. Sub-point of I
1. Sub-point of I.B.
2. Sub-point of I.B.
3. Sub-point of I.B.
a) Sub-point of I.B.3.
b) Sub-point of I.B.3.
II. Main idea
A. Sub-point of idea II.
B. Sub-point of idea II.
III. Main idea
FIGURE 4.8 Standard outline form.
Solving Problems 107
collection of explicit instructions for how to mix and bake these sweets.
The directions for assembling a childs tricycle is another example of an
algorithm. These directions can be a combination of English and pictures
intended to provide the necessary instructions for solving the assembly
task. Neither the recipe for your favorite cookie nor the assembly instructions for a tricycle can be executed directly by a computer; they are not
computer programs. However, both are valid algorithms, and both are
valuable because they use English or diagrams to convey the task.
One design technique used by software developers is called top-down
design. Top-down design starts with a summary of the problem and
proceeds by successively refining vague instructions into more explicit
instructions. For example, consider designing an algorithm to draw the
image of an off-road vehicle shown in Figure 4.9.
A top-level design is a refinement (decomposition) of the problem
into an algorithm of a few instructions. These top-level instructions are
necessarily extremely vague. For the off-road vehicle problem a suitable
top-level design would be something like the following five-instruction
algorithm:
1. Draw a green grille.
2. Draw bumper just below the grille.
3. Draw the tires behind the grille and bumper.
4. Draw the windshield just above the grille.
5. Draw two auxiliary lights on top of the windshield.
FIGURE 4.9 An off-road vehicle.
108 Computational Thinking for the Modern Problem Solver
The second step in top-down design is to consider each of the instructions from the top level and one by one refine each instruction into parts.
In our off-road vehicle example, drawing the grill involves headlights
and black grill openings that can be included to provide more detail.
Similarly, the tires, windshield, and auxiliary lights can be further refined.
Figure 4.10 shows a suitable second-level algorithm.
Notice that top-down design produces an algorithm that is very much
like an outline. Instructions from higher levels are refined into more
detailed instructions that are indented beneath. We have chosen to number the algorithm parts a little differently than standard outline numbering in order to clarify the relationship between an instruction and its
refinement. For example, Instruction 1 is refined into four more detailed
instructions: 1.1 through 1.4.
The process of top-down design does not necessarily end with a secondlevel design. Anytime the designer feels it is helpful to provide more detail
some or all instructions can be further refined. For the off-road vehicle
example it seems useful to provide one more level of refinement as shown
in Figure 4.11.
1. Draw a green grille.
1.1. Draw a green grille background.
1.2. Draw the left headlight.
1.3. Draw four equally spaced black vertical rectangles for grille
openings.
1.4. Draw the right headlight.
2. Draw bumper just below the grille.
3. Draw the tires behind the grille and bumper.
3.1. Draw the left tire (a black rectangle) slightly protruding left of
the grille and bumper.
3.2. Draw a half-moon hubcap extending outside the left tire.
3.3. Draw the right tire (a black rectangle) slightly protruding right
of the grille and bumper.
3.4. Draw a half-moon hubcap extending outside the right tire.
4. Draw the windshield just above the grille.
4.1. Draw a gray rectangle for the outside of the windshield.
4.2. Draw a white rectangle for the center of the windshield.
5. Draw two auxiliary lights on top of the windshield.
5.1. Draw the left auxiliary light.
5.2. Draw the right auxiliary light.
FIGURE 4.10 Second-level algorithm for the off-road vehicle drawing.
Solving Problems 109
1. Draw a green grille.
1.1 Draw a green grille background.
1.2 Draw the left headlight.
1.2.1. Draw black outer dot as a rim for the left headlight.
1.2.2. Draw white dot centered within the black rim.
1.2.3. Draw three equally spaced vertical black rectangles as
headlight protectors.
1.3 Draw four equally spaced black vertical rectangles for grille
openings.
1.4 Draw the right headlight.
1.4.1. Draw black outer dot as a rim for the right headlight.
1.4.2. Draw white dot centered within the black rim.
1.4.3. Draw three equally spaced vertical black rectangles as
headlight protectors.
2. Draw bumper just below the grille.
3. Draw the tires behind the grille and bumper.
3.1. Draw the left tire (a black rectangle) slightly protruding left of
the grille and bumper.
3.2. Draw a half-moon hubcap extending outside the left tire.
3.3. Draw the right tire (a black rectangle) slightly protruding right
of the grille and bumper.
3.4. Draw a half-moon hubcap extending outside the right tire.
4. Draw the windshield just above the grille.
4.1. Draw a gray rectangle for the outside of the windshield.
4.2. Draw a white rectangle for the center of the windshield.
5. Draw two auxiliary lights on top of the windshield.
5.1. Draw the left auxiliary light.
5.1.1. Draw outer black rectangle as a rim for the left auxiliary
light.
5.1.2. Draw yellow rectangle centered inside the black rim.
5.1.3. Place the word “HI” centered in the yellow rectangle.
5.1.4. Draw a small black rectangle for the base of the light.
5.2. Draw the right auxiliary light.
5.2.1. Draw outer black rectangle as a rim for the left auxiliary
light.
5.2.2. Draw yellow rectangle centered inside the black rim.
5.2.3. Place the word “MOM” centered in the yellow rectangle.
5.2.4. Draw a small black rectangle for the base of the light.
FIGURE 4.11 Final algorithm for the off-road vehicle drawing.
110 Computational Thinking for the Modern Problem Solver
Top-down design is not the only design technique based upon decomposition. Another form of software design that is widely used by software
engineers today is known as successive prototyping. A prototype of any
object is an early approximation of the object. For example, automobile
manufacturers often create clay or plastic models of potential new cars
long before they actually intend to manufacture them. The model (a prototype) allows the company to investigate customer opinions and possibly
even perform initial tests for aerodynamics.
A prototype for a computer program is a partially functioning piece of
software. Typically, a prototype performs some, but not all, of the requirements from the problem definition. For example, the prototype may display the proper application window, but when the user clicks buttons
nothing happens because the functionality associated with the buttons is
not included in the prototype.
Designing with successive prototyping consists of a sequence of individual prototypes that progressively lead to a final working program. The
early prototypes provide very little of the desired functionality, while later
prototypes are nearly finished programs. The design for a new car might
begin with a sketch as a first prototype, then proceed to a clay model for
a second prototype, followed by concept cars serving as later prototypes.
As an example of successive prototyping of software consider that Sals
Surfboard Shop (SSS) is a retail store, and that Sal wants to expand the
business by creating an online store to sell his surfing products. An initial
prototype of the SSS online purchase software might produce a homepage
that looks something like Figure 4.12.
For this first prototype we will assume that all of the links on this
homepage are nonfunctional. Even lacking all of this functionality, this
first prototype is useful in the sense that the customer can examine the
look and feel of the homepage, perhaps requesting different colors, images,
or links. The designer could then produce a second prototype similar to
the first but incorporating Sals requests.
A reasonable succession of prototypes might continue as indicated next:
Prototype 1Initial web page only (see Figure 4.12)
Prototype 2Same as Prototype 1 except incorporating Sals
requested improvements
Prototype 3Same as Prototype 2 except including all inventory pages
(no ability to modify cart)
Solving Problems 111
Prototype 4Same as Prototype 3 except including ability to add items
and view cart
Prototype 5Same as Prototype 4 except including secure checkout
functionality
Prototype 6Same as Prototype 5 except supporting site search functionality and Contact us page
In this case the last prototype (Prototype 6) may provide all required
functionality; this prototype could be ready to submit as a final product
after sufficient software testing.
Successive prototyping is a form of decomposition, because each prototype represents a focus on some portion of the entire set of requirements.
This means that the software engineer has to decompose the entire problem into parts and implement the parts successively.
Both top-down design and successive prototyping have their own
advantages. Top-down design can work well when all of the software
requirements are all well known from the outset. Top-down design is
advantageous because at each step the algorithm is complete, although
possibly quite vague. Such completeness provides better confidence that
no functionality will be overlooked.
The greatest shortcoming of top-down design is that generally there is
no computer software produced until the design is complete. Top-down
FIGURE 4.12 Initial page for SSS online purchase website.
112 Computational Thinking for the Modern Problem Solver
design documents are algorithms, but these algorithms are not executable.
This lack of any kind of actual software throughout the design process can
appear to the customer as a lack of progress, as well as making it difficult
for project managers to estimate the amount of progress that has been
made. Software developers also tend to be more satisfied with the visible
evidence of progress provided by actual computer programs. Successive
prototyping is popular to a great extent because of the tangible progress
evident in each prototype.
When requirements are not completely understood initially, successive
prototyping also has a clear advantage. The completion of each prototype
provides an opportunity for those involved in the project to evaluate the
software and make significant changes to the overall product. Customers
in particular like to create new requirements or make changes to requirements in response to a prototype. This customer input has become so integral to software development that the term content expert is now used to
refer to a person who understands the customers wishes. Typically, the
content expert is not a computer scientist, but still plays a vital role in
software development.
4.4 DECOMPOSITION: OTHER USES
Decomposition is certainly an essential skill for software design, but
design is far from the only way that decomposition is used in computing.
Modern computers often contain multiple processors, also referred to as
cores. These multicore machines allow for different programs, or different
parts of the same program, to execute simultaneously. The idea that multiple pieces of software execute simultaneously, also known as multitasking,
requires that the software be decomposed. This multitasking is restricted
to a handful of cores in most laptop computers but extends to tens of
thousands of processors in todays supercomputers.
A related concept, called grid computing, makes use of the Internet.
Grid computing uses many networked computers to attack the same problem. A computer program decomposes the problem in such a way that
each computer can work on solving one part of the problem at the same
time that other computers solve other parts.
The kind of decomposition described Section 4.3, like that of multitasking involves dividing a program into separate instructions or groups of
instructions. Data decomposition is another use of the concept of divide
and conquer. In fact, data decomposition is so important that there is an
entire field of computing known as data organization.
Solving Problems 113
As an example of decomposing data, we examine two search algorithms.
A search algorithm is a method for examining a group of data items in
order to find an item with some particular property.
The most intuitive of all search algorithms is linear search. A linear
search requires that the group of items be arranged one after another
from first to last. The algorithm consists of examining the first item, then
the second, the third, the fourth, and so on, until the desired item has
been found.
As an example of a linear search, suppose you were given a stack of
award certificates and told that one of the awards might be awarded to
you. A linear search would proceed as follows looking for your certificate
in a stack of 500:
Step 1 Check the name on the top certificate, if not your name then proceed to Step 2.
Step 2 Check the name on the 2nd certificate, if not your name then proceed to Step 3.
Step 3 Check the name on the 3rd certificate, if not your name then proceed to Step 4.

Step 500 Check the name on the 500th certificate.
If you find your name on a certificate, you can stop at that step. In the
worst case (when your certificate is last or not included) you would need
to examine all 500 certificates.
Now suppose that the stack of award certificates is sorted alphabetically with the beginning of the alphabet at the top of the stack. In this
case we could use a different algorithm known as binary search. Each
step of a binary search examines the middle item of the remaining
group. By comparing the middle item to the sought item, half of the
group can be eliminated from further consideration in this search. To
see why consider that your name is Jones, Susan and the name in the
middle is Smith, John. Since the stack has been alphabetized and since
Jones precedes Smith alphabetically, there is no need to consider the half
of the data from Smith to the end. Similarly, if the middle name was
Gomez, Marc, then the first half of the data (through Gomez) can be
eliminated from further consideration. A binary search of the previous
114 Computational Thinking for the Modern Problem Solver
(alphabetized) stack of 500 scholarship certificates would proceed as
follows:
Step 1 Check the name on the middle certificate in the stack. If the middle certificate alphabetically precedes your name, then set aside
the top half of the stack. If the middle certificate alphabetically
follows your name, then set aside the bottom half of the stack.
Step 2 Check the name on the middle certificate in the remaining stack.
If the middle certificate alphabetically precedes your name, then
set aside the top half of the remaining stack. If the middle certificate alphabetically follows your name, then set aside the bottom
half of the remaining stack.
Repeat Step 2 until either your certificate is found or the remaining
stack has only one certificate that is not yours.
As mentioned earlier, a disadvantage of binary search is that it requires
data that is sorted. However, the payoff is that binary search is usually
faster. A linear search of 500 scholarship certificates can require as many
as 500 steps, while the most steps for binary search is 9. Figure 4.13 justifies this claim.
Both linear search and binary search involve decomposition of data in
the sense that they divide the data into individual parts to be searched, but
the way that this division occurs is quite different. Linear search removes
one item from the remaining group of items for each step of the algorithm,
whereas binary search removes roughly half of the group at each step. This
distinction in the way that divide and conquer is applied leads to the significantly improved performance of binary search. For more discussion
of how decomposition is useful for data, Chapter 7 considers more data
organizational techniques.
4.5 ABSTRACTION: CLASS DIAGRAMS
Sometimes the word abstract conjures up thoughts of abstract art that
might seem unusual or even extreme or difficult to understand. However,
there is another definition for the technique used by computer science.
A more appropriate definition is that an abstraction is anything that
allows us to concentrate on important characteristics while deemphasizing less important, perhaps distracting, details. For example, you are
Solving Problems 115
using abstraction if you tell someone that you just saw a red Corvette. In
this case the color and model of the car were considered to be the most
important, while details of the model year, engine displacement, wheel
dimensions, and so forth are omitted. Abstraction allows for more succinct communication, while also allowing the user to choose a particular
emphasis. Someone else might have felt that the year the Corvette is manufactured is more important than its color and use a different abstraction.
Binary Search
after this step
number of items
remaining to be
searched
1 250
2 125
3 62
4 31
5 15
6 7
7 3
8 1
Line 9 search complete ar Search
after this step
number of items
remaining to be
searched
1 499
2 498
3 497
4 496
5 495
6 494
7 493
8 492
9 491
10 490

499 1
500 search complete
FIGURE 4.13 Worst-case performance of linear and binary search (500 items).
116 Computational Thinking for the Modern Problem Solver
Software engineers use abstractions that assist in the problem-solving
process. In Section 4.3 we pointed out human memory limitations of 7 2.
One way to overcome our inability to solve complex problems is to simplify complexity using abstraction. Like a digital camera uses a handful
of focus points, computer scientists learn to focus on the most important
issues through abstraction.
A control structure is a mechanism for specifying the proper order in
which instructions must be performed. Algorithms are composed of five
fundamental control structures:
1. Sequential control
2. Selection
3. Repetition
4. Control abstraction
5. Concurrency (the topic of Chapter 11)
These five structures are composed to define the control flowthe order
of instruction executionfor an algorithm. The first three of these control
mechanisms were introduced in Section 4.2. Sequential control ensures
that one instruction executes before another. Selection occurs whenever
the algorithm must choose (select) among different options. Repetition
consists of executing one or more instructions repeatedly. As an example
of these three control structures, consider the recipe (algorithm) for making fudge in Figure 4.14.
The fudge recipe demonstrates many examples of sequential execution.
Each of the numbered steps necessarily precedes the subsequent steps in
the sequence of execution. Control selection occurs in Step 2, when the
cook has the option of adding walnuts or not. Step 5 is an example of control repetition.
Control abstraction is not necessary in an algorithm as simple as the
fudge recipe. However, if we consider something more complicated, then
control abstraction becomes useful. Figure 4.15 illustrates with directions
(an algorithm) for creating a tray of treats.
Control abstraction occurs when one instruction in an algorithm consists of a reference to executing a subalgorithm. In the algorithm from
Figure 4.15, Step 1 is such a reference. This single instruction abstractly
refers to the recipe (a kind of subalgorithm) from Figure 4.14. Notice that
Solving Problems 117
control abstraction removes distracting details from the algorithm for
making the tray of treats. Step 1 abstracts the nine-step recipe for fudge
in just two words: Make fudge. Similarly, Steps 2 and 3 are probably also
abstractions for other cooking recipes.
Data abstraction is no less important than control abstraction. A standard way to diagram data abstraction is known as a class diagram. Class
diagrams use a rectangle to denote a single class of objects. The class diagram rectangle abstracts the group of objects in terms of two things:
Attributes
Operations
The theory behind this kind of data abstraction is that objects in our
world can be explained in terms of (1) what they are and (2) what they can
do. An objects attributes capture what it is, and operations that can be
performed upon the object define what it can do. For example, consider
the class diagram for a thermostat from Figure 4.16.
RECIPE STEPS
1. Place the following ingredients in a microwavable bowl:
3 cups of semisweet chocolate chips
one 14 oz. can of sweetened condensed milk
cup of butter
2. If desired, stir in 1 cup of walnut pieces.
3. Zap in microwave for one minute.
4. Remove from microwave and stir the mixture.
5. Repeat Steps 3 and 4 until chocolate chips are completely melted.
6. Stir 1 teaspoon of vanilla into mixture.
7. Pour mixture into a greased 8 by 8 dish.
8. Refrigerate for three hours.
9. Cut fudge into 1 inch squares.
FIGURE 4.14 Fudge recipe.
RECIPE STEPS
1. Make fudge (see Figure 4.14).
2. Make chocolate chip cookies.
3. Make peanut butter bars.
4. Arrange fudge, cookies, and bars on a large tray.
FIGURE 4.15 Making a tray of treats.
118 Computational Thinking for the Modern Problem Solver
The rectangle on the left abstractly describes the thermostat pictured to
its right. A class diagram rectangle consists of three parts, diagrammed in
three horizontal compartments. The name of the class of objects (in this
case Thermostat) is in the top compartment. The middle compartment
lists attributes. The thermostat can be abstracted into three attributes: (1)
the current position of the upper left switch (COOL, OFF, or HEAT); (2)
the current position of the upper-right fan switch (either ON or AUTO);
(3) the current setting of the rotary temperature dial.
The operations in a class diagram are listed in the bottom compartment. Operations are abstract references to the behavior of the object.
There are three ways to change the upper-left switch of the thermostat,
corresponding to the setToHeat, setToCool, and setToNoHeat operations. Similarly, there are two ways some can position the upper-right
switch: setFanToOn and setFanToAuto. Turning the temperature dial
clockwise is listed as increaseTempSetting and turning counterclockwise as decreaseTempSetting. The last operation, readCurrentTemperature, is included because homeowners often use thermostats to check the
house temperature. In total this kind of thermostat is abstracted as three
attributes and eight operations that capture the most important aspects
of the device.
The pair of parentheses following each operation in Figure 4.16 is indicative of the potential for operations to include parameters. A parameter
provides flexibility to a method by allowing the same method to receive
different argument values. In the case of the Thermostat, we could have
ermostat

heatSwitchSetting : ( COOL / OFF / HEAT )
fanSetting : ( ON / AUTO )
temperatureSetting : integer
setToHeat ()
setToCool ()
setToNoHeat ()
setFanToOn ()
setFanToAuto ()
increaseTempSetting ()
decreaseTempSetting ()
readCurrentTemperature ()
FIGURE 4.16 Thermostat class diagram.
Solving Problems 119
replaced the increaseTempSetting and decreaseTempSetting methods by
the following single method:
setTemperature(t : integer)
The setTemperature method has a single parameter, named t. The
: integer notation indicates that t must be some integer. When the setTemperature is applied to a thermostat, an integer argument must be supplied. For example, setTemperature(70) represents an operation to set the
temperature to 70 degrees.
Figure 4.17 shows a second Thermostat class that incorporates parameters in its operations. This class requires fewer operations because of
the flexibility provided by parameters. In place of applying a setToNoHeat() operation, the equivalent operation for ThermostatToo objects is
setMainFunction(OFF). Similarly, the operations setMainFunction(COOL),
setMainFunction(HEAT), setFan(ON), setFan(AUTO) from ThermostatToo
correspond, respectively, to setToCool(), setToHeat(), setFanToOn(), and
setFanToAuto().
As a second example class diagram, consider a dial padlock (see
Figure 4.18). The padlock has two attributes (dialPosition and latch) and
four operations, as shown.
4.6 ABSTRACTION: USE CASE DIAGRAMS
We have seen that abstraction is useful during software design both for
expressing the instructions of an algorithm and for describing algorithms
data. But abstraction can be used even before the process of software
design begins.
ermostat Too

heatSwitchSetting: ( COOL / OFF / HEAT )
fanSetting: ( ON / AUTO )
temperatureSetting: integer
setMainFunction( f : COOL / OFF / HEAT )
setFan ( b : ON / AUTO )
setTemperature( t : integer )
FIGURE 4.17 ThermostatToo class diagram.
120 Computational Thinking for the Modern Problem Solver
Use case diagrams are a technique for depicting a systemsoftware system or some other systemby way of interaction between computer users
and a system. The two main components of a use case diagram are actors
and use cases. Each actor represents a group of users of similar type, and a
use case is an action that can be performed by the system. Lines are drawn
from each actor to the particular actions that this type of user can perform.
Figure 4.19 is a simple use case diagram that describes the work of a
cab driver. The single actor shown in this diagram is the cab driver and
there are four use cases to abstract four significant actions performed by
the actor.
Figure 4.20 is a use case diagram for a more complex system: a computer program for online student course registration. In this case a rectangle has been drawn around the actions to indicate that they collectively
represent the functionality of the registration system.
Padlock
dialPosition : integer
latch : (OPEN / CLOSED)
turnLeftTo( j : integer )
turnRightTo ( j : integer )
pullLatchOpen()
pushLatchClosed()
FIGURE 4.18 Padlock class diagram.
Pick up taxi
from depot
Pick up next
passenger
Deliver
passenger &
collect fare
Return taxi to
depot
Cab Driver
FIGURE 4.19 Cab driver use case diagram.
Solving Problems 121
Actors of a use case diagram are grouped into roles. The reason for the
different roles is to group users according to their shared actions. In the
registration example there are three roles and, therefore, three actors: student, registrar, and professor. Students can perform four actions: registering for a class, canceling a class registration, logging in, and viewing online
courses. Professors do not need to register for classes or cancel such enrollment, but they might want to view their class lists or increase/decrease the
number of possible students who can enroll. The registrar needs to be able
to perform still other actions. It is common for some actions to be available to multiple actors. For example, students, professors, and registrars
must all be able to log into the student registration system.
Use case diagrams may also depict relationships between actions. Two
of the more common relationships are labeled extend and include.
Cancel a
course
registration
Register for a
course
Registration System
Change
maximum
course size
Student Log in securely
View courses
Display class
list
Create new
course
Cancel course
Professor
Registrar
FIGURE 4.20 Registration system use case diagram.
122 Computational Thinking for the Modern Problem Solver
An extend relationship occurs whenever one action is an extension or
specialized version of another. An include relationship results from one
action making use of another as part of its function. Figure 4.21 contains
examples of both of these relationships.
This use case diagram illustrates a simplified version of the checkout
system in a grocery store. Two actorsthe customer and the checkout
clerkare pictured. The primary action of a customer is to purchase items
from the store. However, liquor is handled somewhat differently because
of the need to be certain that the customer is of legal age to purchase
liquor. Therefore, the action of purchasing liquor is a specialized version
of making a purchase.
There are three include relationships pictured in Figure 4.21. The
action of purchasing liquor involves the action of verifying the customers
age. Likewise, receiving money from the customer and printing a sales
receipt are both actions that are a part of completing the sale.
Purchase liquor
Purchase item
<<<include>>>
<<<include>>>
Grocery Store
Complete the
sale
Print sales
receipt
Customer
Checkout
Clerk
Verify age of
customer
Receive cash
from customer
<<<extend>>>
<<<include>>>
FIGURE 4.21 Grocery store use case diagram.
Solving Problems 123
4.7 SUMMARY
The four problem-solving techniquesproblem definition, logical reasoning, decomposition, and abstractionthat make up the foundation of this
chapter form an interconnected structure that are at the core of computational thinking. Problem definitions are decomposed into functional
requirements that are typically expressed abstractly using forms borrowed
from logic. Deductive reasoning is based in logical reasoning. The 3-tiered
design model is itself a decomposition into three abstract modules, one
of which is focused on the logic of the processing solution. Similarly, topdown design, prototyping, and data decomposition all rely upon problem
definition, logical reasoning, and abstraction.
The five patterns of controlsequential execution, selection, repetition,
control abstraction, and concurrencyare essential for expressing algorithms, and algorithms are the form of problem solutions in the software
world. Diagrams are also helpful in the process of designing software solutions. Use case diagrams are used to analyze the problem; state-activity
diagrams help ensure completeness of a set of functional requirements;
and class diagrams are effective tools for software design.
Most of the problem-solving techniques of this chapter had their origins long before computers existed and most have utility that extends well
beyond computer science. What employee could not benefit by improved
problem-solving skills? Occupations from scientific research to crime
scene investigation are rooted in logical reasoning. Sociologists, economists, and politicians all decompose populations into abstractly defined
groupsanother form of data decomposition.
4.8 WHEN WILL YOU EVER USE THIS STUFF?
Life can be viewed as an endless sequence of problems. When you wake
up you must solve the problem of what clothes to wear and what to eat for
breakfast, and at the end of the day you must decide when to retire and
when to set the alarm clock for your next day. The middle of our workdays
tend to result in more complex problems, and it is these more challenging
problems that determine things like success and paycheck size. It is also
these more challenging problems that benefit from well-honed problemsolving skills.
How many times have you been overwhelmed by a new project, saying something like, I dont know where to begin? There are two good
answers to this question in this chapter: (1) begin by defining the problem,
124 Computational Thinking for the Modern Problem Solver
and (2) you can always limit the focus of the problem by using abstractions. The chapter goes further to teach strategies, such as listing functional requirements for problem definition and use case diagrams for
abstraction.
Many problem-solving strategies are not unique to computer science.
Divide and conquer problem solving is something many would label as
common sense. However, computer science applies divide and conquer in
many ways from top-down design to prototyping, from dividing data in
half for a binary search to identifying simultaneous efforts in multitasking.
Logical reasoning also permeates all of humankinds discoveries. From
a few experiments, scientists can generalize findings by careful use of
inductive reasoning. The scientist might also rely upon the patterns from
prior observations as a way to determine which future experiments are of
interest, thereby applying a form of deductive reasoning.
Yes, we are all problem solvers. But when it comes to problems with
algorithmic solutions, no one understands better how to solve the problems than the computer scientist.
REFERENCES
1. Doyle, Sir Arthur Conan. The Sign of Four. (1890).
2. Miller, G. The magical number seven, plus or minus two: Some limits on
our capacity for processing information. The Psychological Review 63 (1956):
8197.
TERMINOLOGY
3-tiered architecture
abstraction
actor
algorithm
analysis
attributes (of a class)
binary search
class diagram
content expert
control abstraction
control flow
control structure
customer (software)
data abstraction
data organization
decomposition
deductive reasoning
design (of software)
Solving Problems 125
divide and conquer
functional requirements
grid computing
inductive reasoning
linear search
logical reasoning
multitasking
nonfunctional requirements
operations (of a class)
outlining
patterns
problem definition
prototype
repetition
requirements (software)
role (of users)
search algorithm
sequential (execution)
state-activity table
successive prototyping
top-down design
use case
use case diagram
EXERCISES
1. Write a group of functional requirements in the style of Figure 4.1
for the task of setting the time on a common wristwatch.
2. Draw a class diagram for the wristwatch described in the previous exercise.
3. Draw a class diagram for the DVD player described in Figure 4.1.
4. Create a use case diagram for handling books in a library. Be certain
to capture the work of patrons and librarians.
5. For each of the following situations, describe whether the reasoning
is deductive or inductive.
a. Scientific investigation relies upon two different laboratories that
are able to repeat the same experiment before publishing the result.
b. Using the current weather radar and local forecast for the day,
you decide whether to schedule an outdoor party.
c. Based upon the US Constitution lawyers argue a specific case in
front of the Supreme Court.
126 Computational Thinking for the Modern Problem Solver
d. A mathematician proves a new theorem by applying accepted axioms and other theorems as reasoning for each step of the proof.
e. A painter decides whether to use oil or water colors for a particular
painting based upon past experiences using these different media.
f. A forensic expert concludes that someone died of natural causes,
based upon her education and the results of an autopsy.
6. Consider the following set of functional requirements:
Index: W1
Name: Parka
Action: If the current temperature is less than 0 degrees Fahrenheit
and the forecast is for snow, then you should wear a parka.
Index: W2
Name: Raincoat
Action: If the current temperature is greater than 0 degrees Fahrenheit
and the forecast is for snow, then you should wear a raincoat.
Index: W3
Name: Umbrella
Action: If the current temperature is greater than 0 degrees
Fahrenheit and the forecast is for precipitation, then you should
carry an umbrella.
Index: W4
Name: Leather
Action: If the current temperature is less than 0 degrees Fahrenheit
and the forecast is for no precipitation, then you should wear a
leather coat.
a. Create a state-activity table for this set of requirements.
b. Identify all of the conflicts in the set of requirements.
c. Identify all of the ways in which the requirements are
incomplete.
Solving Problems 127
7. In Section 4.2 the following algorithm is proposed as an incorrect
way to attempt to swap the contents of two variables. Assuming
that the myDog variable is assigned Fido initially, while yourDog
stores Rover, then what values do each variable store after this
algorithm executes?
myDog yourDog
yourDog myDog
8. Suppose you are given the task of looking for a particular name in a
telephone book with roughly 4,000 names.
a. Which name of the phone book would be the first one examined
using a linear search?
b. Which name of the phone book would be the first one examined
using a binary search?
c. Assuming the person you are searching for is not in the phone
book, how many names would be examined to discover this
when using a linear search?
d. Assuming the person you are searching for is not in the phone
book, about how many names would be examined to discover
this when using a binary search?

129
Chapter 5
Algorithmic Thinking
And now the sequence of events in no particular order.
DAN RATHER
An algorithmic view of nature, social interaction, and life itself can be
incredibly valuable. Ranging from the mundane to the complex, many of
lifes essential activities involve following a sequence of simple and discrete steps to solve some larger problem. Baking a dozen cookies, tying
a Windsor knot, developing a business plan, diagnosing an illness, and
designing a commercial jumbo jet are examples of processes that require
algorithmic thinking to complete.
Perhaps more than any other discipline, computer science has given
deep thought to algorithmic thinking and has developed highly refined
ways of describing and interpreting complex processes. This chapter
describes actions, sequences of actions, conditional actions, repeated
OBJECTIVES
Understand the concept of software and program execution
Understand that algorithms involve choices and choices take the
form of selections involving logical conditions
Understand that algorithms often involve the repetition of statements
Understand how algorithms are modularized
Understand the form and function of flowchart elements for imperative statements including naming, selection, and repetition
Understand the concepts of computational state, events, and actions
Model sequential algorithms of ten or fewer states
130 Computational Thinking for the Modern Problem Solver
actions, and how to reduce complexity by decomposing large problems
into smaller units.
5.1 ALGORITHMS
An algorithm is a sequence of discrete actions that when followed, will
result in achieving some goal or solving some problem. Everyone is accustomed to following algorithms in daily life whether we are aware of it
or not. Football players are following an algorithm when they execute a
play on the field; drivers are using an algorithm when they follow a set of
instructions for getting from one city to another; piano players are using
an algorithm when they read and play a musical score; mathematicians
are using an algorithm when they use long division to find the ratio of two
numbers; and actors are using an algorithm of sorts when they read and
execute a script for some theatrical performance.
As another example, consider that a recipe is an algorithm that a chef
can follow to create a main dish, dessert, or even a drink.
Chocolate Chip1 Cookie Recipe
Ingredients
1 cup melted butter
2 cups brown sugar
2 eggs
3 cups flour
1 teaspoon baking powder
1 teaspoon baking soda
2 cups chocolate chips
Directions
1. Preheat the oven to 375 degrees F.
2. Line a cookie sheet with parchment paper
3. In a bowl, stir together the butter, brown sugar and eggs.
4. In a separate bowl, combine the flour, baking powder and baking
soda. Gradually combine with the sugar mixture.
5. Add the chocolate chips
6. Fill the cookie sheet with one-spoonful drops of the cookie dough.
7. Bake dough for 9 minutes
8. Cool for five minutes before removing from cookie sheet.
Image courtesy of http://www.flickr.com/photos/amagill/34754258/
In the field of computer science, an algorithm is any well-defined
sequence of actions that takes a set of values as input and produces some
set of values as output. In other words, an algorithm is a sequence of computational actions that transform the input into the desired output. A
Algorithmic Thinking 131
computational understanding of the chocolate chip cookie recipe views
the list of ingredients as the input to the recipe; the directions constitute
the algorithm. The directions describe an orderly sequence of discrete
actions that transform the input into the desired output. The output is, of
course, a plate full of the best chocolate chip cookies in the world.
Any useful algorithm must ensure that several important properties
are maintained. One of the most important requirements is that each
of the individual actions referred to in the algorithm be meaningful.
When computer programmers write an algorithm, programmers must
know the precise meaning of each action they write; just as a chefs must
understand the meaning of each action described in a recipe. Computer
programmers refer to the meaning of an action as the semantics of an
action. The phrase semantics refers to the meaning of the actions that
occur in an algorithm.
Another requirement is that the actions of an algorithm must have only
one possible interpretation, so that there is no misunderstanding about
the semantics of the action. We say that an action must be unambiguous; meaning that the action is not subject to conflicting interpretations.
In the recipe example, each step is written in such a way that a chef can
easily understand and therefore follow the instructions. Actions like preheat, line, stir, combine, add, bake, and cool are common terms that all
chefs fully understand and are not subject to multiple interpretations. If
we replace the word bake in step 7 with the term heat, the directions now
say to Heat dough for 9 minutes. This makes the algorithm less clear and
therefore more difficult to follow since chefs do not typically use this term
to describe baking cookies. An inexperienced cook might consider broiling the dough or simply letting it set out at room temperature in order to
heat the dough.
An algorithm must also ensure that the order in which the actions
occur be well defined. It should be self-evident that the order of actions
taken when making chocolate chip cookies is vitally important. If, for
example, we swap steps 6 and 7 in the cookie recipe, we end up placing
a bowl full of dough into the oven and baking one giant cookie that we
remove from the oven and carve up into small spoon-sized chunks that
we carefully drop onto the cookie sheet after which the dough is allowed
to bake for nine minutes.
Finally we note that the number of actions described by an algorithm
must be finite rather than infinite. No goal can be reached if we are
required to follow a never-ending sequence of actions in order to achieve
132 Computational Thinking for the Modern Problem Solver
the goal. A computer scientist might express this requirement by saying
that an algorithm must halt in order to be useful.
5.2 SOFTWARE AND PROGRAMMING LANGUAGES
A computer is able to perform a surprisingly small number of relatively
simple actions such as adding two integer numbers or checking to see if
two integer numbers are equal. Of course, computers can solve tremendously complex problems and achieve incredibly useful outcomes if they
perform these actions quickly enough and in the right sequence.
Computer software, also referred to as a program, provides the instructions for telling a computer the algorithm that it should follow to achieve
some goal. Software cannot be expressed in human languages such as
English or Chinese or Spanish since these languages are not easily used to
describe computation with the necessary technical precision. Computer
software is therefore expressed in a programming language. A programming language is a language that is designed to precisely and compactly
express computational algorithms. Programming languages must therefore be able to represent the input and output data of an algorithm along
with the sequence of actions that a computer must follow to transform the
input into the desired output. When a computer executes a computer program, the computer simply follows the steps that are given by the program
in order to obtain the desired output from the provided input.
Just like there are numerous human languages in the world, there are
a surprisingly large number of different programming languages in common use today. Although each programming language must be able to
precisely express a computational algorithm, not all programming languages express computation in the same way. Many programming languages express computation as a sequence of commands that are issued to
the computer. These commands are often referred to as imperatives and
languages that express computation in this fashion are therefore known
as imperative languages. Other languages express computation using very
different paradigms. Functional languages emphasize the relationship
between input and output as an intrinsic entity rather than viewing computation as a sequence of individual actions that move from input to output. Declarative languages emphasize the expression of facts from which
output can be generated by applying relevant facts to the input. Other
paradigms include logical programming, object-oriented programming,
and concurrent programming.
Algorithmic Thinking 133
In this chapter we will use an informal imperative language for expressing computational algorithm. Although a computer cannot directly execute this informal language, the programs that we will describe can be
easily translated into a real programming language.
5.3 ACTIONS
As we have already mentioned, computational algorithms must be
expressed as a well-defined sequence of actions that the computer must
follow. Perhaps the most critical aspect of computation involves knowing what actions a computer can take and also knowing what actions a
computer cannot take! Consider, for example, the algorithm shown in
Figure 5.1 that gives actions allowing us to travel from New York City to
Los Angeles without consuming any fuel or electrical energy. Although
the algorithm is very simple to write and very simple to understand, it is
not useful since it requires us to perform an impossible action. The action
requiring a person to jump 2,440 miles is of course impossible to perform
and this renders the algorithm meaningless.
Since any executable algorithm must be expressed as a sequence of possible actions, we must first understand what actions a computer might possibly take. Such actions are sometimes referred to as computable actions
or, more formally, as computable functions. The remainder of this section
informally defines a small but powerful set of computable functions that
allow us to express a surprisingly large number of very useful algorithms.
5.3.1 Name Binding
One of the simplest, yet also one of the most important, actions that a
computer can perform is that of naming the elements of a program. In
Fuel-Efficient Travel Algorithm
1. Sprint southwest for 50 yards
2. Jump 2440 miles
3. Land in Los Angeles
FIGURE 5.1 Unrealizable algorithm for fuel-efficient travel.
134 Computational Thinking for the Modern Problem Solver
programming languages, name binding is the association of a name, also
known as an identifier, with a value. Once an identifier is bound to a value,
the identifier is said to reference the corresponding value such that when
the identifier is used in some later context, the identifier stands for the
value to which it is bound.
We will express the name binding action of a computer using an arrow
symbol as shown in Figure 5.2. A valid identifier must appear on the left
of the arrow and a value or a formula that produces a value must occur
on the right. Although most programming languages allow identifiers
to contain characters like dashes, underscores, and even dollar signs, we
will assume that an identifier must only contain the letters A through Z
in either upper- or lowercase. An element known as an expression must
appear on the right of the arrow. An expression is either a value or a formula that produces a value.
Consider the following sequence of name bindings. The first two
actions associate the name X with the value 3 and the name Y with the
value 4. Note that in the final expression, the phrase 3 + 4 is an expression that produces the value 7. In computer science, an expression is a
short formula that describes how to compute a value. Whenever a computer follows the formula to produce a value, we say that the expression is
evaluated. Name binding will always evaluate the expression on the right
side and then associate the resulting value with the name given on the left
side. The effect of the binding on line 3 is therefore to associate the name
Z with the value 7. Although the evaluation of expressions is extremely
important to understand, we will not describe expression evaluation further within this section.
1. X 3
2. Y 4
3. Z 3 + 4
Name Binding
IDENTIFIER EXPRESSION
FIGURE 5.2 How to write a name binding. The value on the right side of the
arrow is bound to the identifier on the left of the arrow.
Algorithmic Thinking 135
Once a binding is established, the name can be used as a replacement
for the value to which it is bound. Consider, for example, the following
sequence of name binding actions. In this example, the first two actions
associate the name X with the value 3 and the name Y with the value 4 as
before. The final action associates the name Z with the sum of X and Y.
Since X refers to 3 and Y refers to 4 we see that Z becomes bound to the
value 7.
1. X 3
2. Y 4
3. Z X + Y
5.3.1.1 Proper Naming
Computer scientists have long recognized the critical importance of
choosing correct names for the elements of a program. The importance
of proper naming is not a modern invention of computation. In ancient
literature and philosophy, the ability to properly name things indicated a
mastery over those things. The ancient Middle Eastern book of Genesis,
for example, describes how God created the universe and placed the first
man, Adam, as the caretaker over all other creatures. Adam demonstrated
his mastery by giving a name to every other creature.
Computer scientists also recognize that a set of well-named programming elements shows a mastery of the logic and nature of the underlying computation. An element is well named if the name descriptively and
correctly reflects the central essence of the element. Proper naming thus
enables a computer scientist to more clearly reason about the algorithm
and data of the program. Poorly named program elements reflect a confused understanding of the elements and also make clear-headed reasoning more difficult.
Consider, for example, an algorithm that takes, as input, the number of
gallons of gasoline it takes to fill up a cars gas tank and the cost per gallon
of gas; a cost that is assumed to be $3.75. The algorithm will then compute
the total cost required to fill up the cars gas tank if the tank is empty.
Figure 5.3 shows two algorithms that perform the same set of actions, and
hence are identical, except that the names of the data values differ.
It should be apparent that the naming shown on the left reflects a deeper
and more correct understanding of the problem than the variable naming on the right. The identifier Cents, for example, is factually incorrect
136 Computational Thinking for the Modern Problem Solver
since the number 3.75 is not given in cents but is a dollar amount. Also,
the identifier Cents does not convey the important information that
the number 3.75 represents the cost per gallon of gasoline. The identifier
Size, while not truly incorrect, reflects a vague understanding that it is
the capacity of the tank that is central to the problem and not, in general,
the physical dimensions or actual size of the tank. Finally, although the
identifier Money actually reflects that the bound value should be interpreted as currency, it does not accurately convey that it is the cost required
to fill the gas tank.
Name binding allows us to write algorithms that solve a wide range of
problems. Consider any problem that involves converting a quantity from
one unit of measure into another. Perhaps we are traveling to the 2016
Summer Olympic Games in Rio de Janeiro, Brazil, and we need to know
how many Brazilian reais (BRL: the official Brazilian unit of currency) one
thousand U.S. dollars (USD) is worth. Of course, the conversion is dependent upon the prevailing exchange rate and since the exchange rate will vary
from day to day, it may be useful to write a computer program to generate
the correct answer for us. Figure 5.4 gives an algorithm using an exchange
rate of 205.5 to determine the BRL that corresponds with US$1,000.
Convert from USD to BRL Algorithm
1. USD 1000
2. ExchangeRate 205.5
3. BRL USD ExchangeRate
FIGURE 5.4 Currency conversion algorithm.
FIGURE 5.3 Two algorithms that differ only in the way data are named.
Algorithmic Thinking 137
Ensuring that all of the variables in a computer program use correct units
of measure is a challenging task for programmers. In September 1999 the
$327.6 million Mars Climate Orbiter was lost due to a software error. The
satellite entered the Martian upper atmosphere at too low an altitude and
disintegrated. NASA later determined that the ground station software was
working in pounds while the spacecraft expected to receive the same information in newtons. This inconsistency led the ground station to underestimate the power of the spacecrafts thrusters by a factor of about 4.5.
5.3.1.2 State
Name bindings are allowed to change as a program executes. For example,
consider a program that executes the following sequence of name bindings.
1. X 3
2. X 4
3. X X + X
After the computer has executed the first action, the name X is associated with the value 3. After the second action has been executed, the name
X is associated with the value 4 rather than the value 3. In the third action,
the name X becomes associated with the value produced by the expression
X + X. Since X is associated with the value 4 when the expression X + X
is evaluated, the name X becomes associated with the value 8.
The computational state of a program is the collection of name bindings that are active at any single point in time. Since any programming
action will potentially change the state of a program, we can describe the
meaning of a program by examining the sequence of changes made to the
state as the program executes. Consider the following sequence of name
bindings where the program state that results from each name binding is
described below the action.
1. X 3
The state is now {X = 3}
2. Y X + 4
The state is now {X = 3 and Y = 7}
138 Computational Thinking for the Modern Problem Solver
3. Y X + Y
The state is now {X = 3 and Y = 10}
4. X X * Y
The state is now {X = 30 and Y = 10}
To illustrate how state changes can be useful in the context of software programming we will again consider traveling to the 2016 Summer
Olympic Games in Rio de Janeiro. Once we are in Rio, we might need to
know the weather forecast for the day to decide whether to attend an outdoor event like skeet shooting or an indoor event like high diving. Perhaps
this presents a challenge to us since the temperature in Brazil is reported in
degrees Celsius but we are far more familiar with temperatures reported in
Fahrenheit. To address this challenge we decide to write a conversion algorithm; an algorithm to convert a temperature from Celsius into Fahrenheit.
We research how this conversion is performed and realize that given
a value in Celsius, we first multiply that value by 9, then divide by 5 and
finally add 32 to obtain the corresponding value in Fahrenheit. We decide
to write the steps of this algorithm as shown in Figure 5.5.
Figure 5.6 shows how the computational state of an algorithm changes
as the algorithm is carried out. In particular, we note that the values bound
to Fahrenheit change three times as the program executes. Fahrenheit
first takes the value 301.5, the product of 33.5 and 9. This binding is then
changed such that Fahrenheit refers to 60.3. Finally, we add 32 and bind
the name Fahrenheit to the value 92.3. The first two values to which the
Convert from Celsius to Fahrenheit Algorithm
1. Celsius 33.5
2. Fahrenheit Celsius * 9
3. Fahrenheit Fahrenheit / 5
4. Fahrenheit Fahrenheit + 32
FIGURE 5.5 Temperature conversion algorithm showing how name bindings
are allowed to change.
Algorithmic Thinking 139
name is bound can be consider temporary values; values that are helpful
as we make progress toward computing the final answer. The binding of
the name Fahrenheit at the conclusion of the algorithm, however, must
ultimately be the correct and final result that we seek.
5.3.2 Selection
Control flow is a computational term that refers to the specific order
in which the individual actions of a computer program are executed.
Normally the actions that a program performs are done in the order that
they are written by the programmer. Often, however, the ordering of
actions must be flexible and allow the computer to respond to inputs of
various types. This flexibility is supported in programming languages by
elements known as control flow statements. Control flow statements are
commands that control the specific ordering of the actions performed by
a computer program.
A selection statement is a control flow statement that allows a computer
to make choices regarding whether certain actions should be performed.
A one-way selection statement allows a programmer to either perform an
action or skip the action. A two-way selection statement allows the computer to choose one of exactly two actions, whereas a multiway selection
statement allows the computer to choose one of several alternatives. We
will first describe a one-way selection statement and then expand our discussion to two-way and multiway selection statements.
5.3.2.1 One-Way Selection
Consider, for example, an online store that charges a $10 shipping cost for
any order under $40 but gives free shipping for any order of at least $40.
This policy can be expressed in English as If the order amount is less than
Convert from Degrees Celsius to Fahrenheit
1. Celsius 33.5
e state is now {Celsius = 33.5}
2. Fahrenheit Celsius * 9
e state is now {Celsius=33.5 and Fahrenheit=301.5}
3. Fahrenheit Fahrenheit / 5
e state is now {Celsius=33.5 and Fahrenheit=60.3}
4. Fahrenheit Fahrenheit + 32
e state is now {Celsius=33.5 and Fahrenheit=92.3}
Figure 5.6: e computational state changes as the algorithm executes
FIGURE 5.6 The computational state changes as the algorithm executes.
140 Computational Thinking for the Modern Problem Solver
$40, then the shipping cost is $10 otherwise the shipping cost is $0. In
this example, the shipping cost is set to either $10 or to $0 depending on
whether the order amount is less than $40.
We will describe algorithms using two different techniques. First, we
will use flowcharts to visually highlight the flow of control through an
algorithm. A flowchart, also known as an activity diagram, is a diagram
that helps to visualize the sequence of actions that occur within a complex
algorithm. In this chapter we will simply use flowcharts as an intuitive
aid to understand sequencing, whereas in Chapter 6 we give a detailed
explanation of how flowcharts are used as a high-level model for computational processes. Most computer programs are not written as flowcharts,
however, so we will also textually describe algorithms using notations that
are very similar to what a computer programmer might use to develop
computational algorithms.
Figure 5.7 shows a flowchart that expresses the algorithm for computing the shipping cost for our online shopping site. The circle at the top
of the flowchart denotes the starting point of the algorithm and arrows
denote the sequencing of the computable actions.
In this flowchart, the order amount, given by the shopping cart total,
is first read into the program from some unspecified external source.
Perhaps the user has entered some data from which the order amount is
computed by another algorithm or perhaps the order amount is read from
a database. After reading the order amount, the shipping cost variable is
then bound to the value 0. This can be understood as a default value that
orderAmount shoppingCartTotal()
shippingCost 10
shippingCost 0
[orderAmount < 40] [orderAmount > = 40]
FIGURE 5.7 A flowchart for computing the shipping cost.
Algorithmic Thinking 141
may be changed to $10 if the order amount is less than the $40 amount
required by the business policy of the online store. Of course, the computer needs to make a decision to either bind shipping cost to $10 or not,
a decision that is denoted by the diamonds of the flowchart. The topmost
diamond splits into two separate paths such that the computer will follow
exactly one of the paths. The path labeled as orderAmount < 40 will be
followed if the logical condition is satisfied. This condition corresponds to
the yes/no question Is the order amount less than 40? If the answer to
this question is yes, expressed as a logical value of true by the computer,
then the shipping cost takes on the value 10. If the logical condition is not
satisfied, then the path labeled as orderAmount >= 40 will be taken.
Although a flowchart is useful to visualize the order in which actions will
take place in an algorithm, most algorithms are written in a textual programming language. Flowcharts are graphical in nature and can be cumbersome to draw and arrange such that the shapes, lines, and arrows are
easily followed. Programming languages, by contrast, consist of text that is
entered in a linear fashion from beginning to end. Programming languages
also tend to be highly structured, meaning that phrases and words must
be written in strictly followed patterns. In this textbook we will describe
a small set of simple textual patterns that correspond to the elements of a
flowchart. Although the language we describe is not a real programming
language, it is very similar to many real programming languages.
The syntactic pattern for expressing a one-way selection is shown in
Figure 5.8. The highlighted and capitalized phrases are simply placeholders that must contain meaningful phrases when the phrase is used in an
actual algorithm. In particular, the CONDITION must be a formula that
produces a logical value of either true or false. The ACTIONS must be a
sequence of valid actions. The meaning of the one-way selection is that
the sequence of ACTIONS is executed whenever the CONDITION is true;
otherwise the ACTIONS are not executed.
One-Way Selection
if CONDITION then
ACTIONS
endif
Figure 5.8. Syntactic pattern for writing a one-way selection
FIGURE 5.8 Syntactic pattern for writing a one-way selection.
142 Computational Thinking for the Modern Problem Solver
Using this notation, we can translate the flowchart of Figure 5.7 into
a textual program. The variable orderAmount is associated with a value
that is generated by a shoppers input. Since the value is not known when
the program is written, only when the program is executed, there must
be a formula to generate this amount. We will assume that the expression
shoppingCartTotal() produces this value for us. This expression might
query a database or might add items together to compute the result. The
details of how this expression produces a value should not concern us;
rather we only need to understand that the expression produces the total
order amount when the expression is evaluated.
After line 1 is executed, the shipping cost is associated with the value
0. The program will then determine whether the condition given as
orderAmount < 40 is true or false. If the condition is true, the shipping cost
variable is changed to the value 10. It should be apparent how the graphical
flowchart corresponds precisely to the written form of this algorithm.
5.3.2.2 Two-Way Selection
Although the algorithm of Figure 5.9 correctly computes the shipping cost
for any order amount, you might notice that the algorithm is somewhat
inefficient since it will sometimes require two bindings when only one
binding is ever necessary. If, for example, the order amount is less than
40 then the shippingCost is bound to 0 and then almost immediately the
binding is changed to the value 10. We can use a two-way selection to better
and more efficiently compute the shipping cost. In a two-way selection, the
computer must choose exactly one of two paths to follow. This is a natural
way to express the computation of shipping cost since there are exactly two
possible shipping costs and exactly one of them must be chosen.
A two-way selection for computing the shipping cost is shown in
Figure 5.10. It is visually apparent from the flowchart that exactly one of
the two alternatives will be executed. There will never be a situation where
Program to Compute Shipping Cost
1. orderAmount shoppingCartTotal()
2. shippingCost 0
3. if orderAmount < 40 then
4. shippingCost 10
5. endif
FIGURE 5.9 Program for computing the shipping cost given an order amount.
Algorithmic Thinking 143
no action is executed. There will never be a situation where both actions
are executed. In this algorithm, the order amount is read from an external
source and then a decision is made to either bind the shipping cost to 0
or bind the shipping cost to 10. Comparison with the previous flowchart
shows that the action binding the shippingCost to zero has been moved to
be part of the selection statement itself.
We will describe a two-way selection statement using the textual phrase
shown in Figure 5.11. Just as before, the highlighted and capitalized elements are merely placeholders into which real phrases must be placed.
More specifically, the CONDITION must be a formula that produces a
logical value while both the IF-TRUE-ACTIONS and IF-FALSE-ACTIONS
must be a sequence of valid actions.
When a two-way selection statement is executed, the meaning is to
execute either the IF-TRUE-ACTIONS or the IF-FALSE-ACTIONS.
Which of these two actions we select depends on the CONDITION. If the
orderAmount shoppingCartTotal()
shippingCost 10
[orderAmount < 40] [orderAmount > = 40]
shippingCost 0
FIGURE 5.10 An improved flowchart for computing the shipping cost.
Two-Way Selection
if CONDITION then
IF-TRUE-ACTIONS
else
IF-FALSE-ACTIONS
endif
Figure 5.11. Syntactic pattern for a two-way selection
FIGURE 5.11 Syntactic pattern for a two-way selection.
144 Computational Thinking for the Modern Problem Solver
CONDITION produces a value of true, then the IF-TRUE-ACTIONS are
executed, otherwise the IF-FALSE-ACTIONS are executed.
Using this notation, we can now write a program that more efficiently expresses the shipping cost policy for our online shopping site.
Figure 5.12 shows how the flowchart of Figure 5.10 can be expressed as a
computable algorithm.
After the orderAmount is obtained in line 1, the program will select
either the action on line 3 or the action on line 5 depending upon the
condition. In this example, the condition is given as orderAmount < 40.
When this condition is true the computer executes the name binding of
line 3; a binding that associates the value 10 with the shipping cost. If the
condition produces a value of false, the name binding of line 5 is executed;
a binding that associates the value 0 with the shipping cost. The logic and
flow of statements in the computable algorithm of Figure 5.12 are identical
with the flowchart of Figure 5.11.
5.3.2.3 Multiway Selection
We often need more flexibility than selecting one alternative between
only two possible actions. Perhaps the online shop has a three-level shipping policy as expressed in Figure 5.13a. In this example, the highest level
charges $10.00 shipping for any order below $20.00, the second highest
level charges $5.00 shipping for any order that is at least $20.00 and less
than $40.00, and the lowest level gives free shipping for any order that is
at least $40.00. We must therefore construct an algorithm to select exactly
one of these levels from among the three distinct possibilities.
The flowchart of Figure 5.13b can be translated into textual form as
shown in Figure 5.14. The program expresses a multiway selection as a
sequence of two-way selections that are chained together by the phrase
elseif. Notice also that the controlling condition of line 2 is more complex
Program to Compute Shipping Cost
1. orderAmount shoppingCartTotal()
2. if orderAmount < 40 then
3. shippingCost 10
4. else
5. shippingCost 0
6. endif
FIGURE 5.12 Program for computing the shipping cost given an order amount.
Algorithmic Thinking 145
since we explicitly check to see if the order amount is at least zero and less
than 20 prior to selecting 10 as the shipping cost. This expression corresponds exactly to the way the policy is listed in Figure 5.13b. In similar
fashion, the controlling condition of line 4 says that the order amount is at
least 20 but less than 40 for the computer to select 5 as the shipping cost.
Notice, however, that the final choice is not explicitly controlled by a conditional. The selection statement is formed in such a manner as to select a
shipping cost of zero only if no other conditions are applicable. The final
action is always selected if neither of the first two actions is taken. In other
words, the computer makes a choice that is dependent upon the order in
which the conditions are written.
The program of Figure 5.14 can be simplified by understanding that
the computer evaluates the conditions from top to bottom. Consider, for
Shipping Cost Policy
Order Amount Shipping Cost
$0.00 to $19.99 $10.00
$20.00 to $39.99 $5.00
$40.00 and up $0.00
(a)
orderAmount shoppingCartTotal()
shippingCost 10
[orderAmount < 20] [orderAmount > = 20]
(b)
[orderAmount > = 40]
shippingCost 5 shippingCost 0
FIGURE 5.13 (a) Shipping cost policy. (b) Flowchart modeling a multiway selection; selecting one of three alternatives.
146 Computational Thinking for the Modern Problem Solver
example, the condition on line 4. This condition is only evaluated when
the condition of line 2 has produced a value of false. In other words, when
the condition of line 4 is evaluated we know that the order amount is not
between $0 and $19.99. The order amount must therefore be either negative
or at least $20. We can exploit this knowledge to reduce the complexity of
our algorithm by asking questions that are easier to answer. If we assume,
for example, that the order amount will never be negative, we know that
the order amount must be at least $20 by the time we ask the second question. By taking the order of the decisions into account and by assuming
that the order amount is not allowed to be negative, we can simplify our
algorithm as shown in Figure 5.15.
Since we assume that the order amount will never be negative, we eliminate that portion of the criterion from line 2 of Figure 5.15. This makes
our algorithm more computationally efficient since the computer does
Program to Compute Shipping Cost
1. orderAmount shoppingCartTotal()
2. if orderAmount < 20 then
3. shippingCost 10
4. elseif orderAmount < 40 then
5. shippingCost 5
6. else
7. shippingCost 0
8. endif
FIGURE 5.15 More computationally efficient program for choosing a shipping
cost of $0, $5, or $10 based on the order amount.
Program to Compute Shipping Cost
1. orderAmount shoppingCartTotal()
2. if orderAmount 0 and orderAmount < 20 then
3. shippingCost 10
4. elseif orderAmount 20 and orderAmount < 40 then
5. shippingCost 5
6. else
7. shippingCost 0
8. endif
FIGURE 5.14 Program for choosing a shipping cost of $0, $5, or $10 based on the
order amount.
Algorithmic Thinking 147
not need to check twice whether the amount is greater than or equal to
zero. In addition, notice that the criteria orderAmount >= 20 has been
removed from the condition of line 4. This is possible since the computer
first checks the condition of line 2 and only if that condition does not
apply is the condition of line 4 checked. Logically, then, the sequencing
of the conditions implies that the order amount must be greater than or
equal to 20 whenever the computer checks the condition of line 4.
5.3.3 Repetition
Wash, rinse, repeat is a phrase that originated on the back of many
brands of shampoo. This phrase has become part of pop culture and is
often used as a metaphor for people who robotically follow instructions
without critically thinking about what they are doing. Of course the point
of this sarcastic metaphor is that anyone following these instructions will
literally spend the rest of their lives endlessly repeating the same steps over
and over; at least until they run out of shampoo.
Nonetheless, in everyday life we must often repeat a sequence of actions
in order to achieve some greater outcome. You paint a wall, for example,
by repeatedly dipping your brush into the paint can and applying the paint
to the wall. You construct a fence repeatedly digging a hole and inserting a
fence post. You even sing a song by repeatedly singing a verse followed by
the chorus. Just as many real-life activities require repetition, computers
often must also execute a sequence of actions repeatedly in order to achieve
some greater outcome. In fact, one of the great strengths of a computer is
its ability to robotically and quickly repeat actions without complaint!
A loop is a control structure that repeatedly executes a sequence
of actions. A while loop is a type of loop where a sequence of actions is
repeated as long as some logical condition holds. All while loops will have
the flowchart structure shown in Figure 5.16. When the while loop is
first encountered, we must determine whether to perform some action or
Actions to Repeat
[condition is true]
[condition is false]
FIGURE 5.16 Flowchart structure for a while loop.
148 Computational Thinking for the Modern Problem Solver
sequence of actions at least one (more) time. This decision is made by asking a yes/no question. If the question is answered affirmatively, then the
actions are performed after which we again ask whether we must repeat
the sequence at least one more time. The repeating loop is highlighted by
the red arrow.
Using everyday English we might describe a repeated sequence of
actions with a phrase similar to while the steak has not yet reached a
temperature of 135F, cook for three minutes. In this example, the logical
condition is the steak has not yet reached 135 F and the repeated action
is cook for three minutes. A flowchart that models this process is shown
in Figure 5.17.
A while loop will be expressed using the notation shown in Figure 5.18
where the CONDITION and the ACTIONS contain elements that make
the loop meaningful. In particular, the CONDITION must be an expression that produces a logical value and the ACTIONS is a meaningful
sequence of actions. The sequence of actions of a loop is often referred to
as the loop body. The condition controls how many times the loop body
actions will be executed.
Figure 5.19 uses this notation to express a computer program that models the process of grilling a steak. In this program we assume that the steak
is placed on the grill at a room temperature of 75 and that for every three
minutes the steak remains on the grill the temperature increases by 13. The
first line binds the value 75 to the name steakTemp; a variable that models
Cook for three minutes
[steakTemp < 135]
[steakTemp >= 135]
FIGURE 5.17 Flowchart that uses a while loop to model the process of grilling
a steak.
while CONDITION do
ACTIONS
endwhile
FIGURE 5.18 Syntactic pattern for a while loop.
Algorithmic Thinking 149
the current temperature of the steak. Of course, the current temperature of
the steak will increase with the amount of time that the steak remains on
the grill. The loop is controlled by the logical condition steakTemp < 135
and the repeated action is expressed as steakTemp steakTemp + 13. In
other words, the loop repeatedly increases the steak temperature in increments of 13 degrees until the minimum desired temperature is attained.
We can gain further insight into the meaning of a while loop by listing the sequence of individual actions that occur when the algorithm is
actually executed by a computer. Figure 5.20 gives a list of each action the
computer takes when executing the program of Figure 5.19 and also shows
the computational state that results from each individual action. The steak
temperature is initialized to the value 75. After this initial action, the program repeatedly decides whether to leave the steak on the grill for three
more minutes (the result being to increase the steak temperature by precisely 13 degrees). Since, at this point in time, the steak temperature is less
than 135, the program decides to grill for three more minutes; and thus
the steak temperature changes from 75 to 88. After several times through
this process, the steak temperature finally increases to a temperature that
is not less than 135. In that case, the program decides that the steak should
not be grilled for another three minutes and the loop terminates.
The algorithm for grilling a steak computes the final temperature of
the steak at the conclusion of grilling. The final temperature may not be
exactly 135 but, as the example illustrates, may be higher than 135 depending upon the starting temperature and the amount by which the temperature rises within a three-minute span.
Grill a Steak Program
1. steakTemp 75
2. while steakTemp < 135 do
3. steakTemp steakTemp + 13
4. endwhile
FIGURE 5.19 An algorithm for modeling the temperature of a steak as it is
grilled.
150 Computational Thinking for the Modern Problem Solver
A small addition to the algorithm will allow us to compute additional
information that a grill chef might require. Perhaps the chef is cooking a
large meal that includes steak, baked potatoes, and steamed broccoli. The
chef needs to know the time required for grilling the steak in order to
ensure that all three dishes are completed at about the same time.
To compute the length of time required, we can introduce a new variable
that represents the number of minutes of grilling that have elapsed at the
conclusion of every three-minute span of time. This variable should obviously be initialized to zero prior to entering the loop since, at that point in the
process, the steak has not yet been put on the grill. Each execution of the loop
should increase the variable by three minutes since our model states that the
temperature is checked in three minute intervals. Once the loop terminates,
the value of the variable will then contain the length of time required to
grill the steak. This modification is shown in Figure 5.21 where the variable
minOnGrill is initialized to zero in line 2 and incremented by three in line 5.
Computer programmers will quickly recognize that the loop of Figure 5.21
is effectively a counting loop. A counting loop is one that contains a variable
Line
number
Comment State after
execution
1 Bind 75 to steakTemp {steakTemp=75}
2 e condition steakTemp < 135 is true (therefore
repeat)
{steakTemp=75}
3 steamTemp = steakTemp + 13 {steakTemp=88}
2 e condition steakTemp < 135 is true (therefore
repeat)
{steakTemp=88}
3 steamTemp = steakTemp + 13 {steakTemp=101}
2 e condition steakTemp < 135 is true (therefore
repeat)
{steakTemp=101}
3 steamTemp = steakTemp + 13 {steakTemp=114}
2 e condition steakTemp < 135 is true (therefore
repeat)
{steakTemp=114}
3 steamTemp = steakTemp + 13 {steakTemp=127}
2 e condition steakTemp < 135 is true (therefore
repeat)
{steakTemp=127}
3 steamTemp = steakTemp + 13 {steakTemp=140}
2 e condition steakTemp < 135 is false (therefore stop)
{steakTemp=140}
Since the condition is false we are done with the
program. e variable steakTemp is bound to the
value 140.
{steakTemp=140}
FIGURE 5.20 The computational state of the steak grilling program.
Algorithmic Thinking 151
to keep track of the number of times the loop is actually executed. In our
example, the variable minOnGrill effectively counts the number of times
that the loop executes, although the count is maintained as a multiple of
three. Prior to executing the loop body, the variable is initialized to zero,
thus denoting that the loop has been executed zero times. After the loop
body is executed for the first time, the minOnGrill variable holds the value
3, denoting that the loop has been executed 1 time (1 multiple of 3). After
the loop is executed for the second time, the minOnGrill variable holds the
value 6, denoting that the loop has been executed 2 times (2 multiples of 3).
The algorithm of Figure 5.21 also exhibits a design pattern that all computer programmers are familiar with. This design pattern states that all
well-written loops must have three well-defined elements.
1. InitializationEvery variable that occurs in the loop must hold the
correct value prior to entering the loop. The initialization of the loop
in Figure 5.21 is performed on lines 1 and 2 where we state that the
steakTemp immediately prior to the grilling process is 75 degrees
and that the steak has been on the grill for 0 minutes.
2. ConditionThe condition that determines when to repeat the
loop must be precise. Since the chef requires the steak to reach 135
degrees, the condition, given on line 3, indicates that the process will
continue as long as steakTemp < 135.
3. ProgressThe actions that are repeatedly executed must in some
way make progress that allows the loop to terminate. Since the condition of Figure 5.21 implies that the loop will terminate only when
Time to Grill a Steak Program
1. steakTemp 75
2. minOnGrill 0
3. while steakTemp < 135 do
4. steakTemp steakTemp + 13
5. minOnGrill minOnGrill + 3
6. endwhile
Figure 5.21 Program to compute how long it will take to grill a steak.
FIGURE 5.21 Program to compute how long it will take to grill a steak.
152 Computational Thinking for the Modern Problem Solver
the steakTemp is not less than 135, the loop makes progress toward
termination by increasing the steakTemp by 13 with every repetition.
This repeated action ensures that the loop will eventually terminate
since the steakTemp must eventually exceed 135.
5.3.3.1 Infinite Loops
Consider making one small change in the program of Figure 5.21. Since we
know that the steak is done when it reaches a temperature of 135 degrees
we decide to reformulate the terminating condition to ensure that we continue to cook the steak as long as the temperature of the steak is not equal
to 135 degrees. This change is reflected on line 3 of Figure 5.22 where we
change the less than (<) to a not equal ().
The algorithm of Figure 5.22 is logically flawed since the loop does not
make progress toward termination. Notice that the loop will only terminate if the steak temperature is precisely 135. Our program, however, is
written in such a way that the steak temperature will never have a value
of precisely 135. The steak temperature will instead take on the values of
75, 88, 101, 113, 126, 139, 152, 175, and so forth. The steak temperature will
therefore increase without limit; becoming computationally hotter than
any object in the universe! In addition, the time required for grilling the
steak will also grow without bound.
Figure 5.22 is an example of an infinite loop. An infinite loop is a loop
that will never terminate because the loop never makes progress toward
termination. In other words, when we consult the condition of the loop
to determine whether the loop should repeat, the answer is always yes
lets do it again! As we mentioned earlier in this chapter, wash,
Time to Grill a Steak Program (incorrect)
1. steakTemp 75
2. minOnGrill 0
3. while steakTemp 135 do
4. steakTemp steakTemp + 13
5. minOnGrill minOnGrill + 3
6. endwhile
FIGURE 5.22 An incorrect program to compute how long it will take to grill a
steak.
Algorithmic Thinking 153
rinse, repeat is a phrase found on the back of many brands of shampoo.
This phrase is another example of an infinite loop, at least from a computational point of view, since there is no condition that ever allows us
to stop the repetition. An infinite loop is almost always*
a logical error
since it violates the requirement that a program halt in a finite number
of steps. Infinite loops are the source of many mistakes in real-world
software.
5.3.4 Modularization
We began this chapter by asserting that any executable algorithm must
be expressed as a sequence of possible, or computable, actions. We have
described several computable actions that include binding, selection, and
repetition along with ability to perform basic arithmetic. We have also
described a process for modeling how a steak is grilled; a process that
is computable since every discrete action of the process is computable.
Modularization is a vital element of programming that allows us to define
new computable actions by assigning a name to some computable process.
Algorithms can be modularized by breaking them into independent
subprocesses. We can, for example, assign the name grillSteak to the
program of Figure 5.21 and we can then invoke the entire steak grilling
algorithm by simply referring to its name. A module is a named subprocess.
Figure 5.23 gives the syntactic pattern for naming a subprocess as a module.
Figure 5.24 shows how the steak grilling program can be turned into a
module by naming the program. In this case, the name grillSteak is associated with the process of grilling a steak. Once a module is defined, we can
execute the subprocess by writing the name of the process and appending
a pair of empty parenthesis. The notation grillSteak(), for example, is
understood to mean execute the process named grillSteak.
* In limited situations, infinite loops can be logically correct and useful. These situations are beyond
the scope of our text.
module NAME() is
ACTIONS
endmodule
FIGURE 5.23 The syntactic pattern for naming a subprocess as a module.
154 Computational Thinking for the Modern Problem Solver
Modules are vital when writing large programs that consist of many
individual parts. Consider, for example, a grill chef who is making dinner
for a small private party. We might describe the entire process of making dinner as the execution of a series of modules that involve baking a
cake, fixing a salad, making lemonade, and grilling a steak. Each of these
modules can be understood as an individual, programmer-defined computable action, and these actions can be invoked by simply referring to
them by name. Since these modules have been elevated to the status of
a computable action, we can also incorporate them into our flowchart
notation. Figure 5.25 shows how a module named makeDinner might be
described as a sequence of submodules. Figure 5.25 also shows a flowchart
that describes the process.
Well-designed modules should meet several criteria. These criteria
generally ensure that the module can be used in a wide variety of larger
processes, that the module is self-contained, that any errors caused by a
Make Dinner Module
1. module makeDinner() is
2. bakeCake()
3. fixSalad()
4. makeLemonade()
5. grillSteak()
6. endmodule
Bake a cake
Fix a salad
Make lemonade
Grill a steak
FIGURE 5.25 Making a dinner expressed as a sequence of subprocesses.
Grill a Steak Module
1. module grillSteak() is
2. steakTemp 75
3. while steakTemp < 135 do
4. steakTemp steakTemp + 13
5. endwhile
6. endmodule
FIGURE 5.24 The grillSteak module.
Algorithmic Thinking 155
module have a limited effect on any system that makes use of the module,
and that the module can be used in a wide variety of contexts. These criteria are given as
1. UnderstandabilityEvery module is self-contained, which implies
that it can be fully understood without any knowledge of actions that
take place outside of the module itself.
2. EncapsulationEvery module affects only the data that it contains. Any
errors that arise from a module are also contained within the module.
3. CompositionEvery module can be incorporated into a larger module without special treatment.
Hosting a private party involves more than just making dinner. The
host must, for example, send out invitations, gather up the responses,
purchase food, clean the house, and choose background music. We can
describe the process of hosting a private party as a module that is composed of these other submodules (Figure 5.26).
Modularity is an extremely powerful technique for designing complex
algorithms. Modules allow us to isolate smaller parts of a large process
such that those smaller parts are much easier to understand and manage.
In addition, since these smaller parts are self-contained, they can be easily inserted into other complex algorithms without needing to customize
them or rewrite them. Also, although we must understand precisely what
a submodule does, we do not need to fully understand the details of how a
submodule actually works.
Host a Party Module
1. module hostParty() is
2. sendInvites()
3. collectResponses()
4. purchaseFood()
5. cleanHouse()
6. chooseMusic()
7. makeDinner()
8. endmodule
FIGURE 5.26 A module for hosting a private dinner party.
156 Computational Thinking for the Modern Problem Solver
5.3.4.1 Module Flexibility
Modules should typically be flexible enough to be used in a variety of conditions. Consider, for example, the steak grilling module of Figure 5.24.
This module can only be accurately used if the ambient room temperature
is 75 degrees. But what if we are grilling the steak in our backyard and we
have allowed the steak to thaw out to the ambient air temperature of 94
degrees? Rather than writing a completely different module, we should
rewrite our grillSteak module to make it flexible enough to accommodate
any starting steak temperature.
Modules are made flexible by allowing users to feed input values into
the code. The module can then respond differently depending on the input
values provided by the user. The number of inputs that a module accepts
must be defined when a module is written. These inputs are known as
formal parameters. A formal parameter is a variable where the initial
value is bound to the values provided as input to the module. The modules
behavior then depends upon the initial value that is provided by the user.
The initial values provided by the module user are known as arguments or
actual parameter.
Figure 5.27 gives an expanded syntactic pattern for defining a module.
The formal parameters are listed within the parentheses associated with
the name. A formal parameter is simply a variable name and a module
may have as many formal parameters as convenient for the modules function. Of course, a module may have no formal parameters, as illustrated by
all of the modules we have previously described.
We can make our grillSteak module flexible by making the starting temperature an input that is controlled from the outside of the module. This
flexibility is shown in Figure 5.28. Note that the module simply defines
what actions the computer should take to grill a steak. Although it may
initially seem that we have to know the value of the steakTemp variable in
order to write a process for grilling the steak, all we really need to know is
that the steak has a starting temperature. Of course, if we are ever asked to
module NAME(V1, V2, ., VN) is
ACTIONS
endmodule
FIGURE 5.27 The syntactic pattern for defining formal parameters.
Algorithmic Thinking 157
grill an actual steak, we then need to obtain the starting steak temperature
to actually carry out the process.
The rewritten grillSteak module now has one formal parameter. This
implies that if we ever need to use this module to grill a steak that we must
supply one actual parameter. The actual parameter becomes the starting
steak temperature for the steak grilling subprocess. If, for example, we
want to grill a steak from a starting temperature of 94 degrees because
we are grilling on a scorching hot summer day from our back porch in
Phoenix, Arizona, we would write
grillSteak(94)
Although the grillSteak module is now flexible enough to be used with
any starting steak temperature, we can still increase its flexibility by noting
that there are two further circumstances that might not always hold. We
might sometimes want to grill a rare steak and hence stop grilling when
the steak reaches 130 degrees. We might also want to grill a well-done
steak and not stop grilling until the steak reaches perhaps 155 degrees.
Also, perhaps it is the case that we have a very thick steak on a slow-cooking grill such that the steaks temperature only increases by 2 degrees for
every three minutes the steak is on the grill. These observations imply
that we can optimize the flexibility of our grillSteak module by adding
two additional formal parameters: the target steak temperature and the
increase in temperature for every three minutes of grilling time. These
changes are shown in Figure 5.29.
Since the grillSteak module now specifies three formal parameters, we
are required to provide three actual parameters when we use the module.
In other words, before using the module we must know (1) the starting
steak temperature, (2) the target steak temperature, and (3) the amount by
which the temperature of the steak will increase with every three minutes
Flexible Grill a Steak Module
1. module grillSteak(steakTemp) is
2. while steakTemp < 135 do
3. steakTemp steakTemp + 13
4. endwhile
5. endmodule
FIGURE 5.28 A more flexible grillSteak module.
158 Computational Thinking for the Modern Problem Solver
left on the grill. Each of the following shows how we can use this grillSteak module to achieve very different outcomes under very different
circumstances.
grillSteak(65, 130, 2)
This causes the steak to be grilled from a starting point of 65 degrees
until it reaches a temperature of at least 130 degrees where the temperature increases by 2 degrees for every three minutes of grill time.
grillSteak(94, 155, 13)
This causes the steak to be grilled from a starting point of 94 degrees
until it reaches a temperature of at least 155 degrees where the temperature increases by 13 degrees for every three minutes of grill time.
grillSteak(94, 135, 5)
This causes the steak to be grilled from a starting point of 94 degrees
until it reaches a temperature of at least 135 degrees where the temperature increases by 5 degrees for every three minutes of grill time.
In summary, we have described name binding, selection, loops, and
modules as ways of expressing algorithms and computational processes.
We have described how the computational state of an algorithm captures
the current values of all data as the algorithm is executed. And finally,
we have seen how modules allow us to break large problems into smaller
units and how these smaller units can be made flexible through the use of
formal parameters.
Most Flexible Grill a Steak Module
1. module grillSteak(steakTemp, targetTemp, increaseAmount) is
2. while steakTemp < targetTemp do
3. steakTemp steakTemp + increaseAmount
4. endwhile
5. endmodule
FIGURE 5.29 An optimally flexible grillSteak module.
Algorithmic Thinking 159
TERMINOLOGY
activity diagram
actual parameter
algorithm
argument
composition
computable action
computable function
computational state
computer software
control flow
control flow statement
encapsulation
executes
expression
flowchart
formal parameter
halt
identifier
loop
counting loop
infinite loop
while loop
modularization
module
name binding
program
programming language
declarative
functional
imperative
selection statement
multiway
one-way
two-way
semantics
unambiguous
understandability
EXERCISES
1. Consider writing a software system to determine what you will wear
to work. If the morning temperature is above 50 degrees you will
wear a pair of olive-green shorts otherwise you will wear a pair of
red-flannel sweats.
a. Write a flowchart that describes how you decide what to wear.
Use a variable named temperature. The first action you chart
should take is to initialize the temperature by obtaining the value
160 Computational Thinking for the Modern Problem Solver
from the National Weather Service (NWS). You may assume that
a module named getTemperatureFromNWS() is available for
your use. Use a variable named attire. When the flowchart is
completed, the value of this variable must be 0 if you choose to
wear shorts and 1 if you choose to wear sweats.
b. Convert your flowchart into module named whatToWear using
the notation described throughout this chapter.
2. As explained in Exercise 1, consider writing a software system to
determine what you will wear to work. In this case you decide to
wear overalls if the temperature is below 20 degrees. Otherwise, if
the temperature is 50 or below you will wear sweats. In all other
cases you will wear shorts.
a. Write a flowchart that describes how you decide what to wear.
Follow the directions of Exercise 1, but note that the final value
of the attire variable must be 0 for shorts, 1 for sweats, and 3 for
overalls.
b. Convert your flowchart into a module named whatToWear
using the notation described throughout this chapter.
3. Assume that a print module allows you to write text onto a computer
screen. If, for example, you wanted to write the text Computational
Thinking onto the computer screen, you would express this action
as print(Computational Thinking).
a. Write a flowchart that describes how to print the values 0, 3, 6, 9,
and 12 to the computer screen. You must use a loop.
b. Write a module named countBy3 that prints the values 0, 3, 6,
9, and 12 to the computer screen.
4. For each of the following flowcharts, list each action that the computer takes and indicate the computational state that follows from
each action.
Algorithmic Thinking 161
[n > 1]
[n <= 1]
[n > 1]
[n <= 1]
n 10
10
n
n
n
n
n
n
n / 2
n / 2
n + 2
n – 2
0 [n < 10]
[n >= 10]
[n is even]
[n is odd]
5. Write a module that computes the weekly salary earned by an hourly
employee. The module has two formal parameters. The first parameter is named hoursWorked and denotes the number of hours that
an employee has worked during a one-week pay period. The second
parameter is named hourlyRate and denotes the number of dollars
the employee makes for every hour of nonovertime work. The hourly
rate for overtime work, anytime exceeding 40 hours in one week, is
50% above the normal hourly rate. As examples, consider using this
module as shown below.
a. weeklySalary(10, 9) should compute the answer 90 since the
employee worked 10 nonovertime hours at $9 per hour.
b. weeklySalary(50, 10) should produce 550 since the employee
worked 40 nonovertime hours at $10 per hour and 10 overtime
hours at $15 per hour.
6. Write a module that computes the volume of a cone. Your module
must have two formal parameters. The first parameter is the radius,
which is given in inches. The second parameter is the height of the
162 Computational Thinking for the Modern Problem Solver
cylinder and is given in feet. Your module must compute the volume
in cubic inches. For a cone of radius R and height H, the volume V is
given by the following equation.
V = (*R2*H)/3
7. Write a module that plays the number guessing game. In this game,
the computer chooses a random number between 0 and 100. The
player must then try to guess the chosen number. Every time the
player guesses, the computer will write Too low if the guess is
less than the chosen number; Too High if the guess is larger than
the chosen number; and You Got It if the guess is equal to the
chosen number.
a. Assume that the module random produces a value in the interval [0, 100]. You can then write something like: computerGuess
random().
b. Assume that the module print as described in Exercise 3 is
provided.
163
Chapter 6
Modeling Solutions
The secret to film is that it is an illusion.
GEORGE LUCAS
Life is full of models. Perhaps in your childhood you made plastic models
of cars or boats. Models are also used to show off new clothing designs.
Economists create models of financial systems, and sociologists model
populations.
A model is nothing more than a replica or representation of some object
or system. Sometimes models are used to capture things too small, too
fast, or too distant to be understood in other ways. A toy model of the
planets of our solar system and a chemists three-dimensional model of
molecular structures are useful because they help us to understand things
that are impossible to see with our eyes.
Typically, a model relies on abstraction to emphasize important characteristics and remove unnecessary detail from that which is being modeled. Architects often use physical models of their buildings to highlight
OBJECTIVES
To be able to interpret activity diagrams involving actions and
conditions
To recognize the three forms (sequences, selections, and repetition)
of control that constitute control flow in basic activity diagrams
To be able to create basic activity diagrams for simple algorithms
To be able identify states and events from an algorithm
To be able to interpret state diagrams including do, entry, and exit
actions
164 Computational Thinking for the Modern Problem Solver
the aesthetics of the exterior structure. Movie creators use storyboards to
model a film in terms of separate scenes.
One subfield of computer science is devoted to software modeling. Such
a computer model is sometimes called a simulation because it simulates
the actual system. Action games and flight simulators used to train airplane pilots are examples of simulations.
This chapter focuses on two different techniques used by software engineers to model algorithms, namely, activity diagrams and state diagrams.
Both of these techniques utilize abstract pictures that depict selected
aspects of algorithms. Both are part of the common diagramming standard notation known as the Unified Modeling Language (UML). Use case
diagrams and class diagrams (see Chapter 4) are also a part of the UML
standard notations.
You should recall that algorithms consist of two main ingredients:
1. Instructions
2. Data
These ingredients explain the primary difference between activity diagrams and state diagrams: one is focused on instructions (activity) and the
other begins with data (and its state).
6.1 ACTIVITY DIAGRAMS
An algorithm is a group of instructions for performing some task. The
variety of such tasks is limitless. There are algorithms for driving from one
city to another, algorithms for assembling a lawn mower, algorithms for
ways to catch the most fish, and algorithms for starting a new company.
Computer scientists are most interested in those algorithms that lead to
software systems, but the design techniques used to develop software algorithms are generally applicable to many types of algorithms.
We say that an algorithm is correct if it performs the intended task
(problem). A correct algorithm must use the correct instructions. For
example, you can not use fishing instructions to solve a problem such as
assembling a lawn mower. However, just because you have identified the
right instructions for a task does not mean your algorithm is correct; you
must still arrange the instructions in a proper order. Imagine the confusion over directions for driving from one city to another if the order of
turns is reversed!
Modeling Solutions 165
In Chapter 4 the term control flow was introduced to mean order of
instruction execution, and diagramming control flow is the best way to
think of activity diagrams. Some people refer to this kind of diagram as
a flow diagram or flowchart. The picture elements of an activity diagram
are quite simple; just five symbols are needed for most diagrams. See
Figure 6.1.
A rectangle represents a single activity. Activities correspond to many
instructions in a computer program. In nonsoftware algorithms, an activity denotes some action to be performed. The action corresponding to the
activity is described inside the activity rectangle. Arrows are used to connect activities and other symbols, indicating the control flowthe order in
which the activities must occur. An arrow from the rectangle for Activity
A to Activity B specifies that A must be performed prior to B.
Decision/merge diamonds are used in activity diagram locations where
the control flow must split or join together as we shall see later. Start and
end symbols are used to denote where the algorithm begins or completes
execution.
As a first example, consider the activity diagram for a typical morning
routine shown in Figure 6.2. This person seems to have a five-step routine
to begin the day. After awakening, teeth are brushed, followed by a shower,
drying hair, and breakfast, in that order.
Activity diagrams are somewhat abstract in the sense that the instruction descriptions are not always detailed, but activity diagrams are quite
precise when it comes to control flow. The morning routine activity diagram includes an order of actions that is unambiguous. Perhaps your
Activity
Control ow
Merge/split
Start
End
FIGURE 6.1 Symbols used in activity diagrams.
166 Computational Thinking for the Modern Problem Solver
routine is to eat breakfast before showering. Changing the order of activities for such a different routine results in a different algorithm and a different activity diagram is needed. The algorithm depicted in Figure 6.2
clearly indicates that showers precede breakfast.
6.2 SELECTION IN ACTIVITY DIAGRAMS
In Chapter 4 we identified five different forms of control flow:
1. Sequential execution
2. Selection
3. Repetition
4. Control abstraction
5. Concurrency
Activity diagrams can depict all five. In this chapter we explore the first
four, while Chapter 11 is devoted to concept of concurrency.
Selection occurs anytime that an algorithm must make a choice. In an
activity diagram a selection is depicted as a split in the flow; the control
Awaken
Brush teeth
Shower
Dry hair
Eat
breakfast
FIGURE 6.2 Activity diagram for a morning routine.
Modeling Solutions 167
flow can follow alternative paths. Figure 6.3 shows how the decision symbol (a small diamond) is used to denote such a split. This diagram shows
that following Activity A the algorithm contains a choice of next executing Activity B or Activity C.
Choices in activity diagrams are based upon conditions, where a condition is any statement that must be either true or false (i.e., a logical expression). Each arrow extending from a decision split needs to be labeled with
a condition (enclosed in square brackets) for which the associated path is
chosen. In Figure 6.3 Activity B is executed in the event that Condition 1
is true following the execution of Activity A. If Condition 2 is true, then
Activity C is chosen. A properly written activity diagram crafts the conditions in such a way that either Condition 1 is true or Condition 2 is true,
but both cannot be true at once.
Figure 6.4 demonstrates the use of this notation for an algorithm that
provides driving directions from University Square Park in Baltimore,
Maryland, to Mt. Vernon Square in Washington, D.C. Traffic in this area
of the United States can be extremely heavy so this algorithm provides for
three potential routes of travel. Regardless of route, the driving directions
begin by traveling on W. Baltimore Street.
Presumably, before leaving home the traveler consults a traffic report
for the Baltimore-Washington Parkway. In the event that the traffic report
is favorable, the driver choses this route (the left path of the diagram)
because it is shorter. However, the diagram shows that the arrow to the
right should be followed if the traffic report for the parkway is bad. This
secondary route follows I-95 and leads to a second decision of whether to
exit at Exit 22B or continue to Exit 27. The second selection also depends
upon traffic report conditions, comparing highways US-29 and US-50.
Notice that Figure 6.4 also illustrates the use of the diamond-shaped
symbol for merging within an activity diagram. In this case the merge
occurs in the path from taking Exit 22B off I-95. This exit causes the driver
to join the Baltimore-Washington Parkway, the same highway as used in
Activity A
Activity B Activity C
[Condition 1] [Condition 2]
FIGURE 6.3 Using a decision symbol for selection.
168 Computational Thinking for the Modern Problem Solver
travel east on W.
Baltimore St.
turn left onto N.
Paca St.
turn left onto W.
Fayette St.
turn left onto N.
Greene St.
continue south on BaltimoreWashington Pkwy
turn right onto S.
Eutaw St.
turn left onto W.
Partt St.
turn right onto S.
Howard St.
continue onto
I395 S.
Join I-95 S.
[trac report favors
US-50 over US-29]
take exit 22B
join Baltimore-Washington
Pkwy
take exit 27 onto
I-495
take exit 30 onto
US-29 S. take US-50 exit
toward Washington
turn left onto M St.
NW
turn right onto 6th
St. NW
turn left onto
Georgia Ave.
continue onto 7th
St. NW
[trac report good for
Baltimore-Washington Pkwy]
[trac report bad for
Baltimore-Washington Pkwy]
[trac report favors
US-29 over US-50]
FIGURE 6.4 Activity diagram for directions from Baltimore to Washington,
D.C.
Modeling Solutions 169
the route of the diagrams leftmost path. Because two routes share the
same highway at this point, they also share the same three last activities,
beginning with exiting onto Highway US-50. The merge diamond is a way
to describe such situations in which two different paths come together for
common future activities. Unlike decision diamonds that require condition labels on outgoing arrows, a merge diamond never includes conditions because there is decision to be made in merging.
The decision/merge symbols also work well in depicting optional activities. Figure 6.5 illustrates with operating instructions for taking a photo
with a simple point-and-click camera. The optional activity in this case
replacing the memory card, because this action is unnecessary unless the
card is full.
Not every selection involves just two choices, as shown in the examples so far. A decision diamond may have more outgoing arrows in order
to handle more choices. Figure 6.6 contains an activity diagram for the
checkout process of a typical online retailer. After an online customer
has pressed the Select Payment button, a choice of payment method
[MEMORY CARD FULL]
[normal operation]
Replace memory card
with one not full
click on/o switch
to turn camera on
Aim camera as
desired
Press shutter release
to take photo
Click on/o switch
to turn camera o
FIGURE 6.5 Activity diagram for taking a photo.
170 Computational Thinking for the Modern Problem Solver
(PayPal, MasterCard, VISA, or Discover) must be made. This represents a
four-way selection.
6.3 REPETITION IN ACTIVITY DIAGRAMS
The decision/merge symbol also serves as a notation for depicting algorithms with repetition. Figure 6.7 demonstrates. This algorithm describes
how to place a call to a specific phone number on a typical cell phone. The
first activity for placing a call is to turn on the cell, then the user must
press the proper button to initiate the telephone app.
The repetition in this algorithm occurs when the caller dials a particular phone number. Notice that the activity diagram pictures this as a
press Proceed to
Checkout button
press Select
Payment button
press Conrm
Purchase button
Enter PayPal
password
Enter PayPal
user name
Enter
expiration date
Enter Discover
number
Enter Mastercard
number
Enter VISA
number
Enter shipping
address
[select Discover]
[select Mastercard] [select VISA]
[select PayPal]
FIGURE 6.6 Activity diagram for checkout process of online retailer.
Modeling Solutions 171
choice based upon whether the phone number is complete or incompletely
dialed. In the case that the number is incomplete, the diagram indicates
that the caller presses the next button and returns to another choice based
upon phone number completeness.
Repetition in an activity diagram is always drawn as an arrow that
returns to a location that was encountered earlier in the algorithm. In
other words the path of arrows forms a loop, which explains why many
computer scientists use the word loop to mean algorithmic repetition.
Figure 6.7 shows that arrows sometimes connect decision and merge
symbols with no intervening activities. It might be tempting to combine
the decision and merge into a single diamond, but it is generally a bit more
readable to avoid using dual-purpose diamond symbols.
Turn on cell
phone
Press telephone
app button
Press 1st button of
phone number
Press next button of
phone number
[phone number complete]
[phone number incomplete]
Press green
call button
FIGURE 6.7 Activity diagram for placing a cell phone call.
172 Computational Thinking for the Modern Problem Solver
A more complex use of repetition is present in the activity diagram of
Figure 6.8. The algorithm described by this diagram is for a kind of online
auction. This auction only puts a few items up for bid at any point in time.
The user is allowed to browse through the items (displayed along with
their current highest bid) one item at a time.
Log in to online
auction
Advance to
next item
[no more items to view
OR nished with auction]
[more items to view]
[no interest in bidding]
[wish to bid]
[wish to watch item]
[nished watching item]
View item up
for bid
Log out of
aution
Place bid
Click refresh
View item up
for bid
FIGURE 6.8 Activity diagram for an online auction.
Modeling Solutions 173
The auction activity diagram contains three instances of repetition.
One loop describes the user advancing from one item to the next and terminates when there are no more items or when the user is finished viewing auction items. A second loop surrounds the first loop, allowing the
user to place a bid before viewing the next item. The bottom loop allows
a user to find out whether someone has placed a higher bid by refreshing
the current item.
6.4 CONTROL ABSTRACTION IN ACTIVITY DIAGRAMS
Activities do not need to be atomic actions. More complex activities can
be abstracted as a rectangle. Zooming in on the rectangle expands it into
subactivities. For example, the activity named log in to online auction
from the Figure 6.8 activity diagram is probably an abstract reference to a
more detailed algorithm. Figure 6.9 expands this activity into more detail.
The box in the upper left of the activity diagram in Figure 6.9 shows
the subalgorithm represented by the log in activity rectangle. This box
contains a five-step sequence that is the subalgorithm. Subalgorithms
may contain all of the notations that are permitted in any other activity
diagram, including their own starting and ending symbols. The diagram
intentionally makes the subalgorithm appear as a blowup of the more
abstract activity rectangle. Software applications for manipulating activity diagrams often use zoom-in and zoom-out commands to manage such
subalgorithms.
In order to indicate that an activity can be expanded into a subalgorithm, a symbol is included in the lower right corner of the abstracted
activity in the diagram.
6.5 STATES AND STATE DIAGRAMS
Activity diagrams are useful for diagramming the behavior (control flow)
of algorithms. However, modern computer applications often rely on the
concept of state, suggesting an alternative kind of design diagram.
Physical matter can be in one of three states: solid, liquid, or gaseous.
Bits of computer memory can be in one of two states: 0 or 1. A homes climate control system is in one of three states: off or heat or cool.
It is computational state that is of the most concern to computer scientists. Imagine that you could take a snapshot of the bit values of every
piece of your computers memory. If so, this snapshot would capture the
complete computers state. Of course, this state is likely to change to a different state almost instantaneously.
174 Computational Thinking for the Modern Problem Solver
When considering what constitutes state in algorithmic design, it is best
to think more broadly about general situations or circumstances from the
users perspective. Software applications are often organized around states
in which each state is a separate situation with its own unique conditions.
Applications designed for Internet delivery are especially state dependent. For example, a web page can often be thought of as a separate state
that contains its own collection of potential commands, in the form of
Direct web browser
to someAuction.com
Click logon bottom
Click 1st Item bottom
Log out of
auction
Place bid
Click refresh
View item up
for bid
Advance to
next item
View item up
for bid
[no more items to view
OR finished with auction)
[more items to view)
[wish to bid]
[wish to watch item]
[no interest in bidding]
[finished watching item]
type password Log in to online
auction
type user name
FIGURE 6.9 Activity diagram for an online auction with subalgorithm.
Modeling Solutions 175
buttons, links, or tabs. Suppose that an airline application allows users to
check flight status, make reservations, and investigate personal information regarding pending flights and frequent flier miles. We can think of
these three broad functionalities as three separate states:
A state for checking flight status
A state for updating reservations
A state for checking and changing my account
A user selects some button, tab, or menu entry to enter each of these
states, and each state has its own unique web page(s), allowing the user to
perform different tasks associated with that state.
State diagrams use many of the same notations as activity diagrams.
However, the meanings of the symbols are quite different for activity and
state diagrams. See Figure 6.10. Rectangles symbolize states in a state diagram, and arrows denote potential transitions from one state to another.
The symbols used at the beginning and ending of a control flow in an
activity diagram are also used to indicate a starting state and ending state
for state diagrams.
Figure 6.11 shows a simple initial example of a state diagram. This state
diagram depicts the three possible states of water: in a liquid form, a solid
form (Ice), and a gaseous form (Water Vapor). The four transitions illustrate how this kind of matter changes state. For example, cooling liquid
water to temperature below 0C causes water to freeze into ice. Similarly,
heating the liquid form of water above 100C results in a transformation from liquid to gas. This particular state diagram has the somewhat
unusual property of needing no start or end state.
State
Transition
Start state
End state
FIGURE 6.10 State diagram notations.
176 Computational Thinking for the Modern Problem Solver
The labels used on transitions describe events where an event is a condition or circumstance. The transition labeled by an event applies only when
the event occurs. For example, the only time that ice transitions to liquid
is when the event heated above 0 degrees C occurs.
The state diagram of Figure 6.12 illustrates a more complex system: the
behavior of a filling stations gasoline pump. This particular pump requires
the use of a credit card. Most of the events described in this diagram
would be performed by the filling station customer. Such events include
swiping a credit card, inserting the pump nozzle into the gas tank while
engaging the filling lever, and disengaging the filling lever while returning
the nozzle. The owner of the gas station is also responsible for performing a couple of different events, namely, turning the pump on and off.
The pumping system itself is responsible for events involving credit card
validation. Yet another way an event occurs is merely due to the passage
of time. For example, there is a five-second delay after this pump prints
a receipt before the welcome screen allows a customer to swipe the next
credit card. Similarly, if the customer fails to engage the nozzle within one
minute of credit card validation, then the pump returns to the welcome
state.
Figure 6.12 demonstrates that it is possible for a transition to begin and
end at the same state. In this example the Warning state has a transition
loop to itself in the event that the customer fails to disengage the filling
lever properly.
6.6 INCLUDING BEHAVIOR IN STATE DIAGRAMS
State diagrams, like those shown so far, are helpful in understanding the
potential changes within a system. However, without more detail these
diagrams fail to explain the behavior of the system. It is possible to add
Liquid
Cooled below
0 degrees C
Cooled below
100 degrees C
Heated above
0 degrees C
Heated above
100 degrees C
Ice Water Vapor
FIGURE 6.11 State diagram for water transitions.
Modeling Solutions 177
system behavior by actions within the states. The correct state diagram
notation for such actions divides states into two compartments: the top
compartment names the state and the bottom compartment describes
actions associated with the state. Each state can include up to three different actions of the following types:
entryThis defines an action that is performed upon each transition
into the state.
exitThis defines an action that is performed upon each transition
out of the state.
doThis defines an action that is performed continuously while in
the state.
Out of Service Welcome
Verifying Invalid
Warning
After 1 min.
of inactivity
After 1 min.
of inactivity
After 30 sec.
of inactivity
After 5 sec.
After 10 sec.
Tank is full
Insert nozzle and engage lever
Credit card validated
Disengage &
return nozzle
to pump
Disengage &
return nozzle to pump
Disengage &
return nozzle to pump
Credit card fails to validate
Swipe credit card
owner turns o pump owner turns pump on
owner turn pump on
Ready
Pumping
Finished
Receipt
FIGURE 6.12 State diagram for gasoline pump.
178 Computational Thinking for the Modern Problem Solver
Figure 6.13 adds behaviors to the gasoline pump state diagram.
The transitions and associated events in Figure 6.13 are the same as in
Figure 6.12. The only difference is that actions have been added.
An entry action is appropriate whenever the action needs to occur upon
a transition into the state. Entering the Verifying state causes the customers credit card to be checked for validity and entering the Receipt state
cause the customers receipt to be printed. Exit actions occur whenever a
transition is made from a state. Sometimes an equivalent state diagram
can be drawn by substituting an exit action of one state with an entry
action to a preceding state. For example, the exit action of the Pumping
state could be removed by making it into an entry action in both the
Finished and Receipt states. Also, note that entry and exit actions are to
be performed every time the associated transition is made. Therefore, the
alarm bell from the Warning state must ring again for every passing minute of inactivity.
A second example of using entry, exit, and do actions is given in
Figure 6.14. This state diagram describes the user authentication system of
an ATM. The user of the ATM begins by activating the machine perhaps
Warning
Invalid
Out of Service Welcome
Verifying
Ready
Pumping
Finished
Receipt
entry/ring bell for 2 sec.
do/show Please remove
nozzle screen
entry/start gas ow
do/gas ow
exit/stop gas ow
do/show ready to ll screen
entry/check card
do/show welcome screen
do/turn light o
do/show Invalid Credit
Card message
entry/print receipt
After 1 min.
of inactivity
After 30 sec.
of inactivity
Disengage &
return nozzle to pump
Disengage &
return nozzle to pump
Disengage &
return nozzle
to pump
After 1 min.
of inactivity Credit card validated
Credit card fails to validate
Swipe credit card
Owner turns pump on
After 10 sec.
Owner turn pump on
Owner turn o pump
Insert nozzle and engage lever
Tank is full
After 5 sec.
FIGURE 6.13 State diagram for gasoline pump including system behavior.
Modeling Solutions 179
by pressing a button on touching the touch screen. While in the Initial
state, the ATM is displaying a screen that welcomes the user and asks for a
credit card to be swiped. The card swiping is an event causing a transition
into the Awaiting PIN state. Immediately before making this transition,
the Initial states exit action is performed. The do action of the Awaiting
PIN state explains that the user will be requested to enter a PIN at this
time. Once the PIN is entered, a transition into the Checking state is made.
If the PIN is valid then the next transition is to the Validated state, which
serves as the end of this process.
User activates ATM
Initial
Awaiting PIN
Checking
Validated ERROR
do/show welcome screen
exit/attemptCount assigned zero
do/show screen to request PIN
exit/attemptCount increased by one
entry/system checks card and PIN
do/show transaction screen entry/destroy credit card
do/show See Card Provider message
User swipes credit card
User enters PIN
PIN is valid PIN is invalid
and attemptCount = 3
PIN is invalid
and attemptCount < 3
FIGURE 6.14 State diagram for ATM authentication.
180 Computational Thinking for the Modern Problem Solver
Invalid PINs are handled in a different way. This algorithm makes use
of a variable, called attemptCount. The attemptCount variable is assigned
an initial value of zero by the exit action of the Initial state. Each exit from
the Awaiting PIN state causes this variable to increase by one. In other
words, while in the Checking state the attemptCount variable will store
the number of times the user has attempted to enter a PIN. This particular
ATM allows the user to attempt the PIN three times and upon a third failure it destroys the credit card. Using variables, like attemptCount, in state
machines helps to keep track of data in addition to the states.
6.7 PROVIDING MORE DETAIL IN STATE DIAGRAMS
It is easy to imagine state diagrams with many more states than those
shown in previous examples. Many algorithms require hundreds, or even
thousands, of states. Such complexity does not mean that state diagrams
are inadequate; it merely means that we need to learn how to use them
effectively.
Like other computational problem solving, two important things to
remember while designing state diagrams are (1) keep them simple and (2)
use divide and conquer. State diagrams are best when they fit on a single
sheet of paper, a single computer display. A common way to so restrict
state diagram is to use states that can be exploded into a separate state diagram. To illustrate, imagine that you have decided to create a new portable
music player in the shape of a five-pointed star. See Figure 6.15.
This music player has five control buttons. Clicking buttons are typical
events, as is shown in the first state diagram for the music player contained
in Figure 6.16. This state diagram includes a variable, called songNum. The
FIGURE 6.15 A star-shaped portable music player.
Modeling Solutions 181
idea is to use this variable to refer to songs that are numbered from 1 (the
first song) to the length of the song list (the last song). Pressing the button during the Playing state causes the songNum, and thereby the player,
to advance to the next song, and pressing moves to the preceding song.
The state diagram also shows that the song list wraps around in the sense
that clicking these buttons to advance off one end of the list causes an
advance to the opposite end.
Figure 6.16 also describes that the play () button functions both to
play and to pause the player. While in the Ready state, pressing causes a
transition into Playing, and pressing in the Playing state causes a transition to the Ready state. Given there is no action in the Ready state, we can
presume that no music is playing at this time.
Figure 6.16 describes two aspects of the music players behavior without
much detail. Pressing the + and buttons produce transitions from the
Playing state to the Playing state, but it isnt clear what function this performs. The second vaguely described behavior that is less obvious has to
do with charging. It is not quite clear when the user plugged in the charger
or what happens if the charger is unplugged so quickly that the battery is
still fully depleted.
Depleted Battery
Ready
Playing
Next
press press
press
press
battery is depleted
unplug charge
press
press +
press
end of song
after
1 sec.
after
1 sec.
Previous
entry/If songNum = 1, then songNum assigned last song in playlist;
Otherwise, songNum decreased by one
do/battery charging
entry/If songNum = length of playlist, then songNum assigned 1;
Otherwise, songNum increased by one
do/play song numbered
songNum
FIGURE 6.16 State diagram for music player.
182 Computational Thinking for the Modern Problem Solver
The proper way to add more detail to a state diagram is to expand/
explode a state into its own state diagram. Figure 6.17 shows a more
detailed state diagram for the music player that explodes both the Playing
state and the Depleted Battery state. Notice that these two exploded states
are still present, but with state diagrams within. We will refer to the states
within an exploded state as the inner states and an exploded state as the
outer state.
The Depleted Battery state has been exploded into a separate state diagram consisting of three inner states. These three states detail when the
charger should be plugged in and how the music player uses an LED to
inform the user about charging. A blinking LED indicates that the device
is charging and a constant green LED light indicates that the charge is
complete. The Playing state has also been exploded into three states. This
explains that the function of the + and buttons is to raise and lower
sound volume.
When states are exploded it is possible for transitions to exit from either
an inner or an outer state. When a transition exits from an outer state,
the transition applies to all of the associated inner states. For example,
if a song ends during either the Louder, Normal, or Quieter state, then a
Previous
Dead Battery
Depleted Battery
Charging
Charged
Playing
Normal
Louder
Ready
Quieter
Next
press
battery is depleted
press press
press
press
plug in charger
charging completed
unplug charger
press
press +
press +
press + press
press
press
end of song after
1 sec.
after
1 sec.
entry/If songNum = 1, then songNum assigned last song in playlist;
Otherwise, songNum decreased by one
entry/decrease sound volume
entry/decrease sound volume
entry/beep three times
exit/songNum assigned 1
entry/battery charging;
blink charging LED
do/charging LED on
constant green
entry/If songNum = length of playlist, then songNum assigned 1;
Otherwise, songNum increased by one
do/play song numbered songNum
FIGURE 6.17 Exploded state diagram for music player.
Modeling Solutions 183
transition to the Next state occurs. Entering transitions must connect to
inner states, not outer states.
Figure 6.17 also points out that it is possible for either inner or outer
states to include their own entry, exit, and do actions. When an outer state
has actions, these must apply to all of its inner states. For example, the do
action of the Playing state means that songs continue to play regardless of
whether in the Louder, Normal, or Quieter states.
6.8 SUMMARY
Although their focus is somewhat different, both activity diagrams and
state diagrams are effective ways to picture and to design algorithms. Both
can be applied to any algorithm, although each has its strengths.
Activity diagrams are best when individual states of an application
are difficult to discern. Algorithms that seem to exhibit just a single state
in which all events are possible at any time tend to follow this pattern.
Activity diagrams do a good job of illustrating the order in which instructions are performed. They also illustrate decisions made by the algorithm
and repeated activities quite well.
State diagrams tend to be more useful when an application consists of
clear and separate states. For example, a software application that uses
web pages in which each page has different buttons will create a different
set of events for each page. In such a situation the pages suggest states.
State diagrams depict a system as an event-driven algorithm. That is,
the system proceeds in response to events, either user events, systemgenerated events, or events dependent upon the passage of time.
Both activity diagrams and state diagrams support decomposition and
abstraction. Sometimes we can zoom in on the actions of an activity diagram to obtain more detail. Similarly, states of a state diagram can sometimes be exploded into their component state diagrams. In both cases it is
possible to not zoom or not explode in order to abstract unwanted detail.
Modeling algorithms pictorially is an effective way to communicate the
key aspects of the algorithm. Computer scientists and non-computer scientists find activity diagrams and state diagrams to be helpful tools for
communicating algorithms of all kinds.
6.9 WHEN WILL I EVER USE THIS STUFF?
It has been said that a picture is worth a thousand words. Not everyone
will create computer programs in their lifetime, but we all use algorithms
daily and we can all benefit from ways to diagram these algorithms as
184 Computational Thinking for the Modern Problem Solver
a way to communicate. The director of a human resource department
depicts the hiring procedures and policies in the form of an activity diagram. The art teacher explains the best ways to create ceramic pottery in
the form of a state diagram.
Nowhere are these diagrams more important than as a tool for communicating with engineers. Activity and state diagrams serve as an abstract
kind of language that allows a design engineer to communicate ideas with
customers. If you can interpret an activity diagram, you are equipped to
understand what the software engineer is planning for your companys
new retail website. If you understand state diagrams, then you can understand the plans of an automotive engineer creating a new car dashboard.
Not only are activity and state diagrams good for designing systems,
but they can also be helpful for analyzing systems. If we draw a state diagram for an organizations shipping process, we might discover combinations of states and events that were never considered. An activity diagram
of your daily routine might help you plan time for additional volunteer
work or a new committee obligation.
TERMINOLOGY
activity diagram
control flow
do (state action)
entry (state action)
exit (state action)
event
flowchart
loop
model
simulation
state (of computation)
state diagram
Unified Modeling Language
(UML)
EXERCISES
1. Which of the following is (are) the rough form(s) of the flow diagram
depicting a loop (repetition)?
Modeling Solutions 185
(a) (b)
(c)
a. Both a) and b) depict loops.
b. All three depict loops.
Use the picture below to complete Exercises 2 through 4.
X
[X 0]
[X < 0]
1000
X X-1
Output X
2. Is the picture an activity diagram or a state diagram?
3. What is the first value of X output when this algorithm executes?
a. 0
b. 1
c. 999
186 Computational Thinking for the Modern Problem Solver
d. 1,000
e. 1,001
4. When this algorithm executes how many times has the Output X
action been executed?
Use the following picture to answer Exercises 5 and 6.
exit/photoCount 99;
displayPhoto 0
Inactive
entry/photoCount photoCount + 1
shutter botton
half pressed
shutter botton
half pressed
shutter botton
fully pressed
play button
pressed
play button
pressed
click NEXT
button
TakingPhotos
entry/displayPhoto displayPhoto + 1
do/display photo on LCD screen
DisplayingPhotos
5. The rectangle named TakingPhotos in this diagram represents
which of these?
a. A computational activity
b. One instruction from a computer program
c. A group of instructions from a computer program
d. A computer program
e. A computational state
6. Assuming the camera is inactive, then the user presses buttons in
the following order: shutter button half pressed, shutter button fully
pressed, play button pressed, shutter button half pressed. What is the
resulting value of photoCount?
7. Draw an activity diagram for the following algorithm, assuming that
pepperoni and mozzarella are both integer variables.
Modeling Solutions 187
Use the following diagram to answer Exercises 8 through 10.
entry/gallonsUsed 3
exit/gallonsUsed gallonsUsed + 1 exit/gallonsUsed gallonsUsed + 0.5
Idling
park car park car
turn onto highway
turn onto highway
turn onto city street
turn onto city street
travel 30
miles
travel 10
miles
HighwayDriving CityDriving
8. What do the rectangles in the diagram represent? (Hint: This is also
the name of this kind of diagram.)
9. Using the diagram, how many total gallons of gas are used in a complete trip that begins from idle, followed by 24 miles of city travel,
followed by 29 miles of highway travel.
10. Which one of the following is an event in the diagram?
a. park car
b. idling
c. exit
d. entry
e. gallonsUsed gallonsUsed + 1
pepperoni 10
mozzarella 1
if pepperoni mozzarella then
while pepperoni > 8 do
mozzarella mozzarella + pepperoni
pepperoni pepperoni – 1
endwhile
else
pepperoni 0
endif
mozzarella mozzarella + 1000

189
Chapter 7
Data Organization
In the successful organization, no detail is too small to escape
close attention.
LOU HOLTZ
Have you ever had trouble finding an important item in your room
because the room was cluttered and disorganized? Have you ever had
trouble finding a file on your computer because you could not remember
what it was named? Computing systems commonly manage billions of
items with every passing moment. A computing system must keep precise account of this data as it flows through the system and this requires
close attention to every small detail. In particular, this chapter explains
that all data must be well organized and properly identified in order to
be usable.
OBJECTIVES
To understand the importance of properly naming items
To understand how a computing system organizes data in memory
To understand how lists, trees, and graphs can be stored in memory
To understand how lists, trees, and graphs are correlated to familiar
concepts such as family trees, road maps, and organizational charts
To understand how indexing is used to organize data in memory
To understand how linking is used to organize data in memory
190 Computational Thinking for the Modern Problem Solver
7.1 NAMES
Theodor Geisel wrote and illustrated more than 45 childrens books.
His books were filled with imaginative scenery and fantastically shaped
creatures. Much of his writing used fictional names that created a poetic
rhythm to his work and rolled smoothly off the tongue when read aloud.
His drawing and watercolors were equally vibrant, carrying an intense
and unique style. Theodor Seuss Geisel, also known as Dr. Seuss, once
wrote a short story about a woman who had 23 sons each having the
name Dave. The following is the opening stanza of this short story, Too
Many Daves[1].
Did I ever tell you that Mrs. McCave
Had twenty-three sons and she named them all Dave?
Well, she did. And that wasnt a smart thing to do.
You see, when she wants one and calls out, Yoo-Hoo!
Come into the house, Dave! she doesnt get one.
All twenty-three Daves of hers come on the run!
This makes things quite difficult at the McCaves
As you can imagine, with so many Daves.
The story goes on to say that Mrs. McCave wished she had named each
son differently so that there would not be so much difficulty. The same
thing is true of computing. When computational data is inappropriately
or confusingly named it becomes very difficult to access or reason about
the data. This same principle is not only true in the context of computation
but is equally true in real life. Although it can be very difficult to determine the correct name for at item, if we inappropriately name something
in the real world, some degree of confusion and difficulty will inevitably
follow. If, for example, we mistakenly identify a coral snake (a venomous
variety) as a scarlet snake (a nonvenomous variety) we are likely to endure
much more difficulty than Mrs. McCave!
Data Organization 191
There are only a few guidelines that should be followed to properly
name items in a computational setting. These guidelines help to ensure
that two different people or computing systems can identify, locate, and
reason about data without confusion.
1. Names should be unique. A name should refer to only one thing and
never more than one. Mrs. McCave, for example, used one name to
refer to many sons and this caused confusion at her household. If a
name only refers to a single item, then whenever that name is used
there is no confusion about what item is being referred to.
2. One item should not have more than one name. If one item has two
different names, it can be confusing to communicate with other people (or other computing systems) about that item. If, for example, I
refer to the author of Too Many Daves as Theodor and you refer to
the author as Dr. Seuss; communication may be more difficult than
if we both used the same name.
3. A name should be descriptive. When computing with data, the
name of an item should describe its role or function within the system. What if we decided to give random names to all of the MP3
music files on our computer? We might, for example, end up with
files named zqiy.mp3, gzpu.mp3, and gaep.mp3. Although each name
would be unique and no file would have more than one name, the
names themselves engender confusion because they are not related
to the content of the music. Descriptive names reduce confusion
by helping us understand the role or the content of the item. A file
named The Star Spangled Banner.mp3 is preferable to naming that
same file zqiy.mp3.
4. The name of an item should be related to the location of the item.
Computing systems must manage and organize an overwhelming
amount of data. The World Wide Web, for example, is a collection of
trillions upon trillions of pieces of data and each of these items must not
only be uniquely named but also quickly located in order to be useful.
The World Wide Web provides one of the best examples of the importance of proper naming. Even though the web contains trillions upon trillions of pages of information, every piece of this information has a unique
name. These names are informally known as web addresses but are formally known as Uniform Resource Locators (URLs). The URL of a web
192 Computational Thinking for the Modern Problem Solver
page is technically not the name of the item itself, but is rather a way of
locating the item. Nonetheless, in a practical sense, the URL serves as both
the name and the location of an item. Consider whether URLs follow the
four guidelines for proper naming.
1. Names should be unique. URLs are unique since a single URL will
not refer to more than one website. For example, http://www.wikipedia.org/ always refers to the Wikipedia website and not to some
weather or news page. If this URL is typed into a web browser, one
will always be directed to the main Wikipedia page and not to a variety of randomly determined websites.
2. One item should not have more than one name. Although this guideline can be violated, it rarely ever is. Most websites do not have two
different URLs to refer to the same page on the site. It is very rare,
for example, to type two different URLs into a web browser and be
directed to the same web page.
3. A name should be descriptive. Most URLs contain a description of
the information on the web page. Consider, for example, the URL
http://en.wikipedia.org/wiki/Coral_snake. This URL is the English
language (en) Wikipedia page describing coral snakes. It would be
surprising to load this page into a browser and see a list of news items
related to recent volcanic eruptions or a description of the top grossing movies of all time.
4. The name of an item should be related to the location of the item.
Every URL indicates not only the content of the page but is primarily related to where the page can be located. Every computer on
the Internet has a name and the first part of a URL identifies one
computer on the Internet. Each computer also has a file system and
the remaining parts of a URL correspond to the location of a file
in that file system. For example, the URL http://en.wikipedia.org/
wiki/Coral_snake indicates, roughly, that the computer named
en.wikipedia.org has a folder named wiki inside of which is a file
named Coral_snake.
The ability to properly identify and name items is essential when managing large amounts of information. It is also essential in real life since
improper names create unnecessary confusion when reasoning about and
Data Organization 193
communicating information. Throughout the remainder of this chapter
we will see how large collections of items can be stored within a computer
so that the items are easily located. The most common ways of organizing
information are as lists, graphs, and trees.
7.2 LISTS
Are you the type of person that makes a list of everything? Perhaps you
have a list of your favorite friends, a list of enemies, a shopping list, a list
of your favorite movies or favorite foods, a to-do list, a pet-peeve list,
a reading list, a wish list, or even a list of all of your lists. Much of the
worlds data is best organized in list form and deep thought is required
to understand how lists can be stored and manipulated by computing
systems.
A list is a sequence of items that are arranged in a particular order.
Consider the following list of the top five most expensive paintings of all
time. It is amazing to find out that The Card Players was privately purchased
for between $250 million to $300 million as of the time of this writing! [2]
1. The Card Players by Paul Czanne
2. No. 5, 1948 by Jackson Pollock
3. Woman III by Willem de Kooning
4. Portrait of Adele Bloch-Bauer I by Gustav Klimt
5. Portrait of Dr. Gachet by Vincent van Gogh
Any item on the list can be identified by its position in the list. We might,
for example, say that The Card Players is the number one most expensive
194 Computational Thinking for the Modern Problem Solver
painting of all time. We might also say that Portrait of Dr. Gachet is the
fifth (or number five) most expensive painting of all time. When we use
numbers to identify the things in a list we are using a technique known as
indexing. Indexing associates a unique number with every item in a set of
data and therefore allows the items to be identified by their index. Since
indices are used to identify data within a list; an index can be understood
as a unique name for one of the items in a list.
In this chapter, we will denote an item in a list by using brackets. For
example, if Paintings is the name of a list, we denote the ith painting as
Paintings[i]. Using this notation, the first painting in the list is denoted as
Paintings[1] and the second item in the list is denoted as Paintings[2]. For
now we are assuming that the first item in a list has an index of 1, but we
will see later that most computing systems assume the first item in a list
has an index of 0. For any computing system that uses zero as the starting
index, we denote the first item in the list as Paintings[0] and the second
item in the list as Paintings[1].
Consider how a list of items can be stored in computer memory. In
computing systems the memory is a one-dimensional arrangement of
items such that each item is assigned a memory address. All of the data
in a computer is stored at some location in memory and each memory
location is numbered as a list starting from zero. Each memory location
can store one word of data where a word is the smallest unit of data that is
naturally stored by some computing system. Figure 7.1 depicts how each
word in memory is stored at a memory address and that these addresses
Words Addresses Words
Addresses 0
0
8
16 15
7
9
1
2
6
5
4
3
14
17
10
11
12
13
1
2
3
4
5
6
FIGURE 7.1 Memory is linear. Each piece of data in memory is located at a
memory address. Memory addresses are numbers or indices. Even CD and DVD
memory is organized linearly.
Data Organization 195
are integer numbers. Memory addresses always start at zero and are as
large as the amount of memory in a particular computing system.
Although hard disks, compact discs (CDs), and digital video discs
(DVDs) are physically shaped as discs, the data stored on these devices
is also arranged in a linear manner. Each disc is divided into concentric
rings known as tracks. Each track is divided into arcs known as sectors.
Each sector is able to store one word of data.*
As a disc spins, a single track
will scan through a sequence of words whose indices increase linearly.
7.2.1 Arrays
7.2.1.1 Storage
An array is perhaps the simplest way of storing a list in memory. An array
stores each item at the memory address corresponding to the items position in the list. If we store the list of the top five most expensive paintings,
for example, we would store the information as shown in Figure 7.2. Since
The Card Players is at position one, it is stored at address 1 and since the
Portrait of Dr. Gachet is at position five in the list, it is stored at address 5.
This description assumes that the title of the painting can be stored in one
word and that there is only one list that we need to store in memory since
storing two lists would require us to store two different things in each
* Sectors will actually contain more than one word of data and sectors nearer the center of the disc
may contain less data than sectors farther from the center. For our purposes, however, it is sufficient to indicate that the words are arranged in a logically linear manner.
e Card Players e Card Players
No. 5, 1948
No. 5, 1948
Woman III
Woman III
Portrait of Adele
BlochBauer I
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet Portrait of Dr.
Gachet
0
7
1
2
6
4
3
1
2
3
4
5
6
0
5
FIGURE 7.2 The list of five paintings can be stored as an array in memory or on
a DVD.
196 Computational Thinking for the Modern Problem Solver
word. Figure 7.2 illustrates that this technique for storing lists will work
whether we are using internal memory or even a DVD.
Given this arrangement of data, is it possible to store two arrays in
memory? Perhaps we also want to store a list of the five top grossing movies of all time or a list of the five longest movies of all time. The problem
is that each of these lists will have a different item at position one and we
cannot store more than one item at memory address one. The solution is
to allow the entire array to be located anywhere in memory rather than
assuming that the array must be located at memory address 1. As long as
we keep track of the location of the array, we are still able to access every
item in the array. The location of the array is known as the base address or
the anchor, and is the memory address of the first item in the array.
From a computers perspective, the name of an array corresponds to the
anchor of the array. If the name of the array is known, then the anchor is
known and all of the array items can be accessed by their index. Figure 7.3
gives an example of two different lists that are stored in memory as arrays.
The array named Paintings is anchored as location 3 and the array named
Movies is anchored at location 8. From the viewpoint of the computer, the
Paintings
anchor e Card Players
No. 5, 1948
Movies
anchor
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Woman III
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet
Avatar
Titanic
Harry Potter and the
Deathly Hallows Part 2
Transformers:
Dark of the Moon
e Lord of the Rings:
e Return of the King
FIGURE 7.3 Two lists stored as arrays in memory. List A is anchored at memory
address 3, and list B is anchored at address 8.
Data Organization 197
name Paintings actually means memory location 3 and the name Movies
actually means memory location 8.
One very important property of an array is that once an array is stored
in memory, the array cannot change its location nor can it change its length.
The array cannot expand to fill more memory nor can it shrink to take up
less memory. Figure 7.3 shows one reason why an array cannot expand.
In this example, the Paintings array cannot expand since there is another
array stored immediately after it.
7.2.1.2 Accessing Array Elements
One of the main advantages of arrays is that we can easily find any item
in the array if we know the index, or position, of the item in the list. If
for example, we want to find the second item in the list of paintings, we
would name that item as Paintings[2]. This name indicates to the computer where the item is located in memory. The computer associates the
name Paintings with the anchor (memory address 3) and then takes the
number 2 as an offset from the anchor. For this example, the computer
moves forward 1 memory location from the anchor to arrive at memory
address 4. The ith item in an array A is named A[i] and the memory location of that item is given by the following simple formula.
(anchor of array A) + (i 1)
Every time a computing system looks up an item in an array, the system must perform one subtraction and one addition to find the items
address. Since performing these operations slows the computing system,
most computing systems adopt the convention that the first item in a list
is numbered from 0 rather than 1. This convention is known as zero indexing. When using zero indexing, the first item in a list is considered to be at
position 0 and the second item in a list is considered to be at position 1 and
so forth. If we adopt this convention, we can compute the memory address
of the i
th item in an array by using the formula:
(anchor of array) + i
7.2.1.3 Deleting Array Elements
Lists will almost certainly change over time. Someone will eventually pay
more than $300 million for a painting and some movie will eventually
198 Computational Thinking for the Modern Problem Solver
make more money than James Camerons Avatar. If we have a to-do list we
will cross things off the list as we complete each task and add other tasks
to the list. The two most common ways of changing a list are to delete an
item and to insert an item.
Consider how our list of the five most expensive paintings of all time
would change if we were to delete The Card Players from the list. Since
the purchase was a private transaction we might hypothetically discover
that the painting had only been purchased for a mere $100 million, which
would place it below other more expensive paintings. This would require
us to delete The Card Players after which we might insert the next most
expensive painting at the end of the list.
Deleting an element from an array is very similar to deleting an item
from a handwritten list. You would likely first erase all of the items in the
list, and then rewrite them once they have been erased. If you also wanted
to insert something into the list, you would simply rewrite the entire list
in the desired order. This process is obviously not very efficient since we
essentially rewrite the entire list any time we delete an item from the list.
At least, we rewrite all of the items in the list that follow the deleted item.
Figure 7.4 illustrates this process.
Although we have already mentioned that an array cannot expand or
shrink, it is possible to both delete items from an array and to insert items
into an array. If, for example, we delete the first item in the list of paintings, each of the other elements in the list would have to shift in memory
since their position in the list changes as a result of the deletion. The second item in the list must become the first item and the third item in the list
must become the second and so forth. The array itself will still consume
the same amount of memory locations but the last memory location will
be blank after the deletion.
Figure 7.5 shows the various steps required to delete The Card
Players from the Paintings list of Figure 7.4. We must first move the
second item in the list, No. 5, 1948, into position 1 of the new list.
FIGURE 7.4 Deleting the first item from a list of famous paintings. The first step
is to erase the entire list. The second step is to rewrite the list. Not very efficient.
Data Organization 199
Since the first item in the list must be stored at the anchor, we must
move the second item in the list, the item at memory location 4, to the
anchor position. Each subsequent item in the list must also be shifted
in memory since its position in the list changes as a result of the deletion. Note that the order in which these moves are performed must be
from the front of the list to the end of the list, otherwise the operation
will not work correctly. For this example, deleting the top item in the
list requires four moves.
7.2.1.4 Inserting Array Elements
We can also insert an element into the array, but only if there are blank
locations at the end of the array. Consider, for example, what would happen if someone purchased Bal du moulin de la Galette, a painting by
Pierre-Auguste Renoir, for $350 million. We would then insert this item
at the beginning of the paintings list since the purchase price would make
the painting the most expensive in history. Insertion at the beginning of
the list requires us to first shift every item in the list and then to finally
place the entered item into the anchor location. These operations must
take place from the end of the list working toward the beginning of the list
to prevent data loss. This is illustrated in Figure 7.6 where the first step is
Paintings
anchor No. 5, 1948
Move 4 to 3
Delete item 1
Move 5 to 4
Move 6 to 5
Move 7 to 6
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Woman III
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet
Avatar
Titanic
Harry Potter and the
Deathly Hallows Part 2
Transformers:
Dark of the Moon
e Lord of the Rings:
e Return of the King
FIGURE 7.5 Deleting the first item in the Paintings list. This requires moving
four items in memory starting with earlier items in the list and moving toward
the end of the list.
200 Computational Thinking for the Modern Problem Solver
to move the Portrait of Dr. Gachet from location 6 to location 7 after which
we move the other elements forward by one memory location. Finally, we
insert Bal du moulin de la Galette at location 3, thereby making it the first
item in the list.
7.2.1.5 Array Summary
Any list can be stored in memory as an array. The main advantage of using
an array is that any element in an array can be easily accessed by just
knowing the position of the item in the list. The main disadvantages are
that the size of the array is fixed and that inserting and deleting items in
the list will often require a significant number of steps.
7.2.2 Linking
7.2.2.1 Storage
Linking data in memory is the most common technique for storing a list
in memory. When we link data together we form a chain of items that are
scattered throughout memory but are nonetheless very well organized and
easily manipulated. This type of storage technique is known as a linked list.
The fundamental idea behind linking data is very similar to certain
forms of geocaching. Geocaching is a real-world treasure hunting game
Paintings
anchor
Bal du moulin de
la Galette
No. 5, 1948
Move 3 to 4
Insert
Move 4 to 5
Move 5 to 6
Move 6 to 7
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Woman III
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet
Avatar
Titanic
Harry Potter and the
Deathly Hallows Part 2
Transformers:
Dark of the Moon
e Lord of the Rings:
e Return of the King
FIGURE 7.6 Inserting an item at the beginning of a list. This requires shifting all
items in the list to make room for the newly inserted item.
Data Organization 201
where players try to locate hidden treasures, known as geocaches, by using
GPS-enabled devices. In a basic geocache game, a person will place a logbook and some special items, the treasure, into a waterproof container.
The person will then hide the container, also known as the cache, somewhere interesting and record the GPS coordinates of the cache. These
coordinates are then posted on an Internet site and other players attempt
to find the cache.
When a player finds the cache, he or she will sign the logbook and perhaps even replace the treasure they find with a treasure of their own. The
treasures are not typically valuable objects, but are interesting trinkets or
perhaps objects that have personal or sentimental value to the player.
A geocache race, or a multicache, introduces a slight variation into the
basic geocaching game. In this variation, each waterproof container will
house not only a logbook and treasure but will also contain the GPS coordinates of the next geocache in a sequence of geocaches. Contestants in
the race will begin with the GPS coordinates of the first geocache. Only
when they find the first geocache will they know what treasure the cache
contains and where the next treasure can be found. The winner of the race
is the first person to find all items in the race. Players will know they have
found the last geocache whenever they find a container without any further GPS coordinates. The race can be summarized as a list of containers
where each container holds both a treasure and the GPS location of the
next container.
Figure 7.7 illustrates how a geocache race is completed. All participants
initially meet at a certain location, which in our example is denoted by the
38.6, 97.5
38.9, 97.5
38.7, 97.5
FIGURE 7.7 Illustration of a geocache race.
202 Computational Thinking for the Modern Problem Solver
yellow dot. Each participant is given the location of the first cache, which
in our example is located at (38.6, 97.5). Note that these are the coordinates
of the first item in the race, not the coordinates of the starting point. When
we reach the first cache, we find a container with a pocket watch and a new
set of coordinates, (38.7, 97.9). The pocket watch is the first item in the race
and the new coordinates indicate the location of the second item in the
race. After reaching the second location we find a container with an ornamental ship anchor and the coordinates of the third cache, (38.9, 97.5).
After reaching the third location we find a container with a seashell, but
there are no coordinates. Since there are no more coordinates, we realize
that we have completed the race. In addition, we now know that the items
in the race are (1) a pocket watch, (2) an ornamental ship anchor, and (3)
a seashell. We discovered all of this information by starting only with the
GPS coordinates of the first item in the race.
The items in a list can be linked together in memory using a technique
that is very similar to geocaching. We first need a waterproof container to
hold our data. We therefore define a node, a (waterproof?) container, to
be an adjacent pair of memory cells. The first node value holds an item in
the list and the second node value holds the memory location of the next
item in the list. By convention, we say that if the second node value holds
the number zero, then there are no more items in the list. We define the
anchor of the list to be memory address of the first node.
Figure 7.8 illustrates how the items in the paintings list can be linked in
memory. In part (a) of this figure, we see 16 memory cells and the data that
each cell contains. A proper interpretation of this data is shown in part (b)
where the cell-pairs that compose a single node are grouped together and
the linkages are shown with arcs that connect the nodes. Initially, the only
thing that we know is the anchor of the list, the memory location of the
first node. In our example, the anchor node at location 3 is composed of
the two cells at memory locations 3 and 4.
The first item in the list is stored at location 3 and the location of the
next item will be stored at location 4. In other words, location 4 will not
contain the next item, but rather it will contain the location of the next
item. We note that The Card Players is the first item in the list and that
the next item in the list is stored at location 12. Moving to location 12 we
find that the next item in the list is No. 5, 1948 and that the location of the
next item is 1. Moving to location 1 we find that the next item in the list is
Woman III and that the location of the next item is 5. Moving to location
Data Organization 203
5 we find that the Portrait of Adele Bloch-Bauer I is the next item in the list
and this item is followed by the painting stored at location 10. Moving to
location 10 we find that the next item in the list is the Portrait of Dr. Gachet
and that there are no more items in the list since the location of the next
item is 0. Recall that the value 0 is a special value that denotes the end of
the list when it is used as a memory location.
7.2.2.2 Accessing Linked List Elements
Perhaps the only real disadvantage to linked lists is the difficulty of
accessing an item in the list given only the index of the element in the
list. To identify the Nth item in a list requires that we start at the anchor
and move through exactly N 1 links. Locating the fourth item in the
list of Figure 7.8, for example, requires us to start at the anchor, follow
the first link to arrive at location 12, follow the second link to arrive at
location 1, and then follow the third and final link to arrive at location 5.
Paintings
anchor e Card Players
14
10
12
5
Woman III
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
14
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet
0
No. 5, 1948
1
Avatar
e Card Players
14
10
12
5
Woman III
14
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet
0
No. 5, 1948
1
Avatar
(a) (b) Link to Item 2
Link to
Item 5
Link to Item 3
Link to
Item 4
FIGURE 7.8 Storing a list of five paintings by linking the items together in memory. (a) Memory without any interpretive notations, (b) memory with interpretive notations.
204 Computational Thinking for the Modern Problem Solver
There we discover that the fourth item in the list is the Portrait of Adele
Bloch-Bauer I.
7.2.2.3 Deleting Linked List Elements
Once an element is found, however, it can be very easily deleted from the
list. Consider a list where we wish to delete an item we will refer to as item
B. The first step is to find the item immediately before B, an item we will
refer to as A. We can delete B by simply making the location of the item
following A to be the location of the item following B. This essentially
relinks the elements in the list to bypass item B. In the list of Figure 7.8, for
example, we can delete Portrait of Adele Bloch-Bauer I by (1) finding that
the item immediately before the portrait to delete is Woman III, (2) noting
that the location of the item following the Portrait of Adele Bloch-Bauer I
is 10, and finally (3) placing the value 10 into memory location 2. You can
double check that this process works by mentally changing the contents of
memory location 2 from a 5 to a 10 and then following the links to determine what paintings are in the list.
7.2.2.4 Inserting Linked List Elements
Inserting into a linked list is similar to deletion. Consider a list that contains
two adjacent items A and C. If we insert item B between items A and C we
must simply change the location of the item following A to be the location
of B and also make the location of the item following B to be the location of
C. A change to these two memory locations is sufficient for insertion.
Consider inserting a new painting into the list of Figure 7.9. Perhaps
a rising new artist has recently sold a painting named Computational
Abstraction that makes it the second most expensive painting in history.
We therefore seek to insert this painting as the second item in the list. The
first step requires us to identify two unused memory cells that we will use
as a list node. Since memory cells 14 and 15 are unused we define this pair
of cells as a node.
Since the first value of a node holds the value of the list item, we can
immediately place the title Computational Abstraction into memory location 14. We must then relink certain items in the list to pass through this
newly created node in the correct order. This relinking is accomplished by
first placing a 14 into cell 4 since cell 4 contains the location of the node that
immediately follows The Card Players. Finally, we place the value 12 into cell
Data Organization 205
15 since No. 5, 1948 follows the newly inserted item. This process is illustrated
in Figure 7.9 where the memory cells that have been changed are highlighted.
7.2.2.5 Linked List Summary
Insertion into a list and deletion from a list are slowed only because we
first have to chain to the position where we will either insert or remove.
Inserting at the beginning of the list and removing the first element in a list
are therefore very fast operations since the first item is the easiest to locate.
Thoughtful readers will perhaps question whether an item can actually
be inserted at the beginning of a list or even whether the first element in
a list can be deleted. Our presentation here does obscure a rather minor
detail present in most real programming situations. In real languages, the
anchor is allowed to change, which makes operations on the first element
very efficient and convenient. In addition, the items in the list do not have
Paintings
anchor
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
e Card Players
14
10
14
5
Woman III
14
12
Computational
Abstraction
Portrait of Adele
BlochBauer I
Portrait of Dr. Gachet
0
No. 5, 1948
1
Avatar
Link to Item 2
Link to Item 4
Link to
Item 3
Link to
Item 6
Link to
Item 5
FIGURE 7.9 Inserting an element into a list involves creating a new node (as
shown in cells 14 and 15) and changing an existing link to refer to the new node
(as shown in cell 4).
206 Computational Thinking for the Modern Problem Solver
to be next to each other in memory, which means that it is easier to find
places to store items since the items are smaller in size.
7.3 GRAPHS
Many real-world objects and concepts are be modeled as a graph. A graph
is a mathematical abstraction that is composed of elements called nodes
and edges. A node typically represents some real-world item, and an edge
is a connection between two nodes. In this text, we limit our discussion
to directed graphs where the edges between nodes are referred to as arcs.
Using a more formal description, we say that a directed graph is a set
of nodes and a set of arcs. The word set is defined in the mathematical
sensea collection of distinct items such that there are never duplicate
items in the collection. In other words, a directed graph is a collection
of distinct nodes and a collection of distinct arcs. An arc is defined as an
ordered pair of nodes that establishes a one-way connection from the first
node to the second node. If, for example, a graph contains an arc from
node A to node B, we write the arc as (A, B). This denotes a connection
from A to B but does not imply a connection from B to A.
We say that graph G = (V, E) means that graph G is composed of a set of
nodes, V, and a set of arcs, E. As an example, consider the following formal
definitions of an example graph.
V = {A,B,C,D,E}
E = {(A,E), (A,B), (B,A), (B,D), (C,E), (D,C), (E,B), (E,C), (E,D)}
G = ({A,B,C,D,E}, {(A,E), (A,B), (B,A), (B,D), (C,E), (D,C), (E,B), (E,C), (E,D)})
In this example, the set of vertices V is given as {A,B,C,D,E} and the set
of arcs E is given by {(A,E), (A,B), (B,A), (B,D), (C,E), (D,C), (E,B), (E,C),
(E,D)}. Graphs are commonly drawn as a diagram where the nodes are
represented as discs, and the arcs are represented as arrows that emerge
from one disc and point to another. Figure 7.10 illustrates how graph G
might be drawn in this manner. Each of the five discs is labeled with one
of the node names, and each arc is shown as an arrow that emerges from
the first node in the arc and points to the second node in the arc.
Graphs are extremely useful models for reasoning about many different types of real-world problems. Figure 7.11 shows how the graph of
Figure 7.10 can be understood as a model of airline routing. If the nodes
of a graph are understood to represent airports and the arcs to represent
Data Organization 207
flights from one airport to another we can represent airline connections.
For the graph of Figure 7.11, we might associate node A with Seattle, B
with Los Angeles, E with Denver, C with Chicago, and D with Miami. The
arcs of the graph then indicate that there are direct flights from Seattle to
Los Angeles and Denver but no direct flight from Denver to Seattle. Also,
the graph tells us that if we want to fly round-trip from Denver to Miami
we have to take a return flight through Chicago.
Road maps can be modeled as a graph if we associate each node with an
intersection and each arc with one lane of a road. Figure 7.12 shows how
the graph of Figure 7.10 could be interpreted as a road map. In this map,
7th Avenue is a two-way street that intersects two one-way streets: W. Oak
FIGURE 7.11 A graph that models airline connections between five cities in the
continental United States.
FIGURE 7.10 Graph G is drawn as a diagram. G is composed of five nodes and
nine arcs.
208 Computational Thinking for the Modern Problem Solver
and Vine. Node A represents the intersection of W. Oak and 7th while
node B represents the intersection of 7th and Walnut Drive in addition to
the intersection of 7th and Vine. Node E is a roundabout that gives access
to W. Oak, E. Oak, Walnut Drive, and Peach Tree Lane.
Graphs are truly ubiquitous in computational thought because they are
able to capture the essence of a wide variety of real-world problems and their
solutions. Graphs are used to model computer networks (i.e., the Internet)
where each node represents a computer and each arc represents a connection between computers. Games like checkers and chess can be modeled as
a graph where each node represents the board after a player has moved and
each arc represents one players move. Chemical structures can be modeled
as a graph if each node is associated with an atom and each arc represents a
bond between atoms. Electrical circuits are graphs such that each node represents an electrical connection between two components, and each arc represents an electrical component such as a resistor or capacitor. The national
power grid can be modeled as a graph where each node represents a transformer and each arc represents a power line that connects transformers. A
universitys curriculum can be expressed as a graph where each node represents a course and each arc represents a prerequisite for taking a course.
7.3.1 Terminology and Properties
Graphs are a mathematical model used to describe the central essence of
a particular real-world concept or object. Graphs are often characterized
A E. Oak St.
B
C
E
D
W. Oak St.
7th Avenue
8th Avenue
Vine St.
Walnut Drive.
Peach Tree Lane
FIGURE 7.12 A graph used to model a road map. Each node represents an intersection and each arc represents a road between intersections.
Data Organization 209
by a set of features that describe the overall structure of the graph itself.
For our text, the features of most concern are listed next and illustrated by
reference to graph G of Figure 7.13.
AdjacencyAssume that U and V are vertices in some graph. Vertex U
is adjacent to vertex V if there is an arc (U, V) in the graph. For example, vertex D is adjacent to vertex C in G since the arc (D, C) appears in
G. Vertex C is not adjacent to D since the arc (C, D) is not in G.
LoopA loop is any arc such that the first and second nodes of the
arc are the same. Graph G does not have a loop.
In-degreeThe in-degree of a vertex V is the number of arcs in the graph
having V as the second vertex. The in-degree of vertex E is 2 since G has
arcs (A, E) and (C, E) as the only arcs where vertex E is the second vertex.
Out-degreeThe out-degree of a vertex V is the number of arcs in
the graph having V as the first vertex. The out-degree of vertex E is
3 since G has arcs (E, B), (E, C), and (E, D) as the only arcs where
vertex E is the first vertex.
OrderThe order of a graph is the number of vertices. The order of
G is 5 since there are 5 vertices.
SizeThe size of a graph is the number of arcs. The size of G is 9
since there are 9 arcs.
PathA path is a sequence of vertices such that for every pair of
adjacent vertices in the sequence there is a corresponding arc in
FIGURE 7.13 Graph G.
210 Computational Thinking for the Modern Problem Solver
the graph. Also, a sequence containing a single vertex is a path. For
example, the sequence [A, E, C] is a path since (A, E) and (E, C) are
arcs in the graph. The sequence [A, B, E] is not a sequence since (B,
E) is not an arc in the graph.
Path lengthThe length of a path is the number of arcs in the path.
The length of [A, E, C] is 2.
CycleA cycle is a path where the length is greater than zero, and
the first and last vertices are the same. A graph without any cycles
is known as an acyclic graph. For example, [A, B, A] is a cycle and
hence graph G is not acyclic.
7.3.2 Storage
Although graphs can be stored in memory using array-like techniques,
we will restrict our discussion to how a graph can be represented using
links. A list can be thought of as a graph where each element but the first
has an in-degree of one, and each element but the last has an out-degree of
one. The central difference between graphs and lists is that the vertices of
a graph may have a larger out-degree.
When storing lists using a linked representation, we assumed that the outdegree of each element was one. In other words, we assumed that each element
in the list was immediately followed in memory by a single link; the memory
address of the single element that followed. We cannot make this assumption
with graphs since a vertex may be adjacent to as many other vertices as exist
in the graph. Since we cannot assume that a vertex has out-degree 1, we must
store the out-degree of each vertex along with the vertex value.
We can store a graph by first storing the value of the vertex (the name)
and then storing the out-degree of the vertex in the very next memory
location. After this, we store N links where N is the out-degree of the vertex. As an example, consider Figure 7.14 that shows one way to store the
graph of Figure 7.13 in memory. In this figure, we arbitrarily select vertex
A as the anchor node and note that the anchor of the graph is then the
memory location of A. In other words, the graph is anchored at 10.
Consider vertex A of Figure 7.14. Since the number 2 is stored in the
memory address immediately following node A, we now know that the
out-degree of A is 2. We then understand that the next two values in memory are links to the two vertices that are adjacent to A. In this example, we
note that vertices B (stored at location 1) and E (stored at location 14) are
adjacent to A. Note that vertex E has an out-degree of 3 and is adjacent to
Data Organization 211
nodes B, C, and D. Note that this representation can only be used if all
vertices in the graph can be reached by starting at the anchor and following some chain of arcs.
7.4 HIERARCHIES
A hierarchy is an arrangement of elements such that the elements are
arranged in levels. Each element in the hierarchy may have many elements
that are directly below but only one element that is directly above. Many
real-world concepts form hierarchies of elements. We will briefly describe
several real-world examples of data that is hierarchical in nature.
7.4.1 Organizational Chart
An organizational chart (often known as an org chart) is a diagram showing the authority structure of an organization and the relationships and
reporting lines that exist between the people that are part of the organization. An organizational chart is a hierarchy of elements where the levels in
the hierarchy correspond to various managerial levels, and each element
corresponds to an individual within the organization.
Figure 7.15, for example, is a simplified organizational chart for the
Internet sales company Amazon. In this chart, there is one president,
Jeffrey Bezos, who sits atop the tree as the root. Four individuals hold
the role of vice president and report directly to Jeffrey Bezos. There are
four directors and one senior manager. Since Thomas Szkutak is above
Tim Stone in this chart, we understand that Tim Stone reports directly to
0
1
2
3
4
5
6
7
8
9
10
11
12
13
0
B
2
10
25
F
1
8
G
0
A
2
1
14
14
15
16
17
18
19
20
21
22
23
24
25
26
27
E
3
1
20
25
0
C
1
14
0
0
D
1
A
Vertex E
Adjacent to B
Adjacent to C
Adjacent to D
Outdegree 3
Graph
anchor
FIGURE 7.14 Graph G is stored in linear memory.
212 Computational Thinking for the Modern Problem Solver
Thomas Szkutak and that Thomas Szkutak has supervisory authority over
Tim Stone. In addition, since Jeffrey Bezos is above Thomas Szkutak, we
understand that Thomas Szkutak reports directly to Jeffrey Bezos and that
Jeffrey Bezos has supervisory authority over Thomas Szkutak.
7.4.2 Family Tree
A family tree shows the genealogical relationship between ancestors and
their descendants. The lower levels of a family tree contain family members from recent generations, and the upper levels of the hierarchy contain ancestors from many generations past. Family trees are not purely
hierarchical if they include information about both the maternal and fraternal ancestry since a person will have two individuals, both a father and
a mother, directly above them. This feature violates the constraint that
each element in the hierarchy must have only one element that is directly
above. If, however, we restrict a family tree to showing only the fraternal
or maternal ancestry of a person, the result is a proper hierarchy of family
members.
J.R.R. Tolkien, author of the popular Lord of the Rings trilogy [3], described
the family ancestry of the Bagginses covering a span of about five generations. The Baggins family lived in the Shire, near the town of Hobbiton
where Bilbo Baggins lived with his adopted relative Frodo Baggins. The
Baggins clan is said to descend from one Balbo Baggins. Bilbo is a greatgrandson of Balbo, as was Frodos father, Drogo. Figure 7.16 shows the fraternal side of the tree for the famous Baggins family as Tolkien narrated.
Jeffrey
Bezos
Jeffrey
Blackburn
Jeffrey
Wilke
Steven
Kessell
Vice
President
President
Director
Senior
Manager
omas
Szkutak
Marc
Onetto
Mark
Peek
Tim
Stone
Sam
Wheeler
Russell
Baker
FIGURE 7.15 A simplified organizational chart for Amazon.com showing four
levels of authority within the corporate structure.

Get Professional Assignment Help Cheaply

Are you busy and do not have time to handle your assignment? Are you scared that your paper will not make the grade? Do you have responsibilities that may hinder you from turning in your assignment on time? Are you tired and can barely handle your assignment? Are your grades inconsistent?

Whichever your reason is, it is valid! You can get professional academic help from our service at affordable rates. We have a team of professional academic writers who can handle all your assignments.

Why Choose Our Academic Writing Service?

• Plagiarism free papers
• Timely delivery
• Any deadline
• Skilled, Experienced Native English Writers
• Subject-relevant academic writer
• Adherence to paper instructions
• Ability to tackle bulk assignments
• Reasonable prices
• 24/7 Customer Support
• Get superb grades consistently

Online Academic Help With Different Subjects

Literature

Students barely have time to read. We got you! Have your literature essay or book review written without having the hassle of reading the book. You can get your literature paper custom-written for you by our literature specialists.

Finance

Do you struggle with finance? No need to torture yourself if finance is not your cup of tea. You can order your finance paper from our academic writing service and get 100% original work from competent finance experts.

Computer science

Computer science is a tough subject. Fortunately, our computer science experts are up to the match. No need to stress and have sleepless nights. Our academic writers will tackle all your computer science assignments and deliver them on time. Let us handle all your python, java, ruby, JavaScript, php , C+ assignments!

Psychology

While psychology may be an interesting subject, you may lack sufficient time to handle your assignments. Don’t despair; by using our academic writing service, you can be assured of perfect grades. Moreover, your grades will be consistent.

Engineering

Engineering is quite a demanding subject. Students face a lot of pressure and barely have enough time to do what they love to do. Our academic writing service got you covered! Our engineering specialists follow the paper instructions and ensure timely delivery of the paper.

Nursing

In the nursing course, you may have difficulties with literature reviews, annotated bibliographies, critical essays, and other assignments. Our nursing assignment writers will offer you professional nursing paper help at low prices.

Sociology

Truth be told, sociology papers can be quite exhausting. Our academic writing service relieves you of fatigue, pressure, and stress. You can relax and have peace of mind as our academic writers handle your sociology assignment.

Business

We take pride in having some of the best business writers in the industry. Our business writers have a lot of experience in the field. They are reliable, and you can be assured of a high-grade paper. They are able to handle business papers of any subject, length, deadline, and difficulty!

Statistics

We boast of having some of the most experienced statistics experts in the industry. Our statistics experts have diverse skills, expertise, and knowledge to handle any kind of assignment. They have access to all kinds of software to get your assignment done.

Law

Writing a law essay may prove to be an insurmountable obstacle, especially when you need to know the peculiarities of the legislative framework. Take advantage of our top-notch law specialists and get superb grades and 100% satisfaction.

What discipline/subjects do you deal in?

We have highlighted some of the most popular subjects we handle above. Those are just a tip of the iceberg. We deal in all academic disciplines since our writers are as diverse. They have been drawn from across all disciplines, and orders are assigned to those writers believed to be the best in the field. In a nutshell, there is no task we cannot handle; all you need to do is place your order with us. As long as your instructions are clear, just trust we shall deliver irrespective of the discipline.

Are your writers competent enough to handle my paper?

Our essay writers are graduates with bachelor's, masters, Ph.D., and doctorate degrees in various subjects. The minimum requirement to be an essay writer with our essay writing service is to have a college degree. All our academic writers have a minimum of two years of academic writing. We have a stringent recruitment process to ensure that we get only the most competent essay writers in the industry. We also ensure that the writers are handsomely compensated for their value. The majority of our writers are native English speakers. As such, the fluency of language and grammar is impeccable.

What if I don’t like the paper?

There is a very low likelihood that you won’t like the paper.

Reasons being:

• When assigning your order, we match the paper’s discipline with the writer’s field/specialization. Since all our writers are graduates, we match the paper’s subject with the field the writer studied. For instance, if it’s a nursing paper, only a nursing graduate and writer will handle it. Furthermore, all our writers have academic writing experience and top-notch research skills.
• We have a quality assurance that reviews the paper before it gets to you. As such, we ensure that you get a paper that meets the required standard and will most definitely make the grade.

In the event that you don’t like your paper:

• The writer will revise the paper up to your pleasing. You have unlimited revisions. You simply need to highlight what specifically you don’t like about the paper, and the writer will make the amendments. The paper will be revised until you are satisfied. Revisions are free of charge
• We will have a different writer write the paper from scratch.
• Last resort, if the above does not work, we will refund your money.

Will the professor find out I didn’t write the paper myself?

Not at all. All papers are written from scratch. There is no way your tutor or instructor will realize that you did not write the paper yourself. In fact, we recommend using our assignment help services for consistent results.

What if the paper is plagiarized?

We check all papers for plagiarism before we submit them. We use powerful plagiarism checking software such as SafeAssign, LopesWrite, and Turnitin. We also upload the plagiarism report so that you can review it. We understand that plagiarism is academic suicide. We would not take the risk of submitting plagiarized work and jeopardize your academic journey. Furthermore, we do not sell or use prewritten papers, and each paper is written from scratch.

When will I get my paper?

You determine when you get the paper by setting the deadline when placing the order. All papers are delivered within the deadline. We are well aware that we operate in a time-sensitive industry. As such, we have laid out strategies to ensure that the client receives the paper on time and they never miss the deadline. We understand that papers that are submitted late have some points deducted. We do not want you to miss any points due to late submission. We work on beating deadlines by huge margins in order to ensure that you have ample time to review the paper before you submit it.

Will anyone find out that I used your services?

We have a privacy and confidentiality policy that guides our work. We NEVER share any customer information with third parties. Noone will ever know that you used our assignment help services. It’s only between you and us. We are bound by our policies to protect the customer’s identity and information. All your information, such as your names, phone number, email, order information, and so on, are protected. We have robust security systems that ensure that your data is protected. Hacking our systems is close to impossible, and it has never happened.

How our Assignment Help Service Works

1. Place an order

You fill all the paper instructions in the order form. Make sure you include all the helpful materials so that our academic writers can deliver the perfect paper. It will also help to eliminate unnecessary revisions.

2. Pay for the order

Proceed to pay for the paper so that it can be assigned to one of our expert academic writers. The paper subject is matched with the writer’s area of specialization.

3. Track the progress

You communicate with the writer and know about the progress of the paper. The client can ask the writer for drafts of the paper. The client can upload extra material and include additional instructions from the lecturer. Receive a paper.

4. Download the paper

The paper is sent to your email and uploaded to your personal account. You also get a plagiarism report attached to your paper.

GET A PERFECT SCORE!!!