Module 1
Intro to Computers and Algorithms
A. The Definition of Computer Science
Almost every day our newspapers, televisions, and electronic media carry reports
of significant advances in computing, such as high-speed supercomputers that perform
more than 90 quadrillion (1015) mathematical operations per second; wireless networks
that stream high-definition video and audio to the remotest corners of the globe in
fractions of a second; minute computer chips that can be embedded into appliances,
clothing, and even our bodies; and artificial intelligence systems that understand and
respond to English language questions faster and more accurately than humans. The next
few years will see technological breakthroughs that, until a few years ago, existed only in
the minds of dreamers and science fiction writers. These are exciting times in computing,
and our goal in this text is to provide you with an understanding of computer science and
an appreciation for the diverse areas of research and study within this important field.
Although the average person can produce a reasonably accurate description of
most scientific fields, even if he or she did not study the subject in school, many people
do not have an intuitive understanding of the types of problems studied by computer
science professionals. For example, you probably know that biology is the study of living
organisms and that chemistry deals with the structure and composition of matter.
However, you might not have the same fundamental understanding of the work that goes
on in computer science. In fact, many people harbor one or more of the following
common misconceptions about this field.
This apparently obvious definition is actually incorrect or, to put it more
precisely, incomplete. For example, some of the earliest and most fundamental theoretical
work in computer science took place from 1920 to 1940, many years before the
development of the first computer system. (This pioneering work was initially considered
a branch of logic and applied mathematics. Computer science did not come to be
recognized as a separate and independent field of scientific study until the late 1950s and
early 1960s.) Even today, there are branches of computer science quite distinct from the
study of “real” machines. In theoretical computer science, for example, researchers study
the logical and mathematical properties of problems and their solutions. Frequently, these
researchers investigate problems not with actual computers but rather with formal models
of computation, which are easier to study and analyze mathematically. Their work
involves pencil and paper, not circuit boards and disks.
Programming is extremely important to the discipline—researchers use it to study
new ideas and build and test new solutions—but, like the computer itself, programming is
a tool. When computer scientists design and analyze a new approach to solving a problem
or create new ways to represent information, they often implement their ideas as
programs to test them on an actual computer system. This enables researchers to see how
well these new ideas work and whether they perform better than previous methods.
For example, searching a list is one of the most common applications of
computers, and it is frequently applied to huge problems, such as finding one specific
account among the approximately 63,000,000 active listings in the Social Security
Administration database. A more efficient lookup method could significantly reduce the
time that telephone-based customers must wait before receiving answers to questions
regarding their accounts. Assume that we have designed what we believe to be a “new
and improved” search technique. After analyzing it theoretically, we would study it
empirically by writing a program to implement our new method, executing it on our
computer, and measuring its performance. These tests would demonstrate under what
conditions our new method is or is not faster than the search procedures currently in use.
If one’s introduction to computer science is not programming, then it might be a
course on the application of computers and software. Such a course typically teaches the
use of a number of popular packages, such as word processors, search engines, database
systems, spreadsheets, presentation software, smartphone apps, and web browsers. These
packages are widely used by professionals in all fields. However, learning to use a
software package is no more a part of computer science than driver’s education is a
branch of automotive engineering. A wide range of people use computer software, but it
is the computer scientist who is responsible for specifying, designing, building, and
testing these software packages as well as the computer systems on which they run.
These three misconceptions about computer science are not entirely wrong; they are just
woefully incomplete. Computers, programming languages, software, and applications are
part of the discipline of computer science, but neither individually nor combined do they
capture the richness and diversity of this field.
There are many definitions of computer science, but the one that best captures the
richness and breadth of ideas embodied in this branch of science was first proposed by
professors Norman Gibbs and Allen Tucker.2 According to their definition, the central
concept in computer science is the algorithm. It is not possible to understand the field
without a thorough understanding of this critically important idea.
We use algorithms (although we don’t call them that) all the time— whenever we
follow a set of instructions to assemble a child’s toy, bake a cake, balance a checkbook,
or go through the college registration process. A:good example of an algorithm used in
everyday life is the set of instructions shown in Figure 1.1 for programming a DVR to
record a collection of television shows. Note the three types of instructions in this
algorithm: sequential (Steps:3, 4, 5, and 7), conditional (Steps 1 and 6), and iterative
(Step 2). Mathematicians use algorithms all the time, and much of the work done by early
Greek, Roman, Persian, and Indian mathematicians involved the discovery of algorithms
for important problems in geometry and arithmetic; an example is Euclid’s algorithm for
finding the greatest common divisor of two positive integers. (Exercise 10 at the end of
the chapter presents this 2,300-year-old algorithm.) We also studied algorithms in
elementary school, even if we didn’t know it.
The instructions our teachers gave were as follows: First add the rightmost
column of numbers (7 1 5), getting the value 12. Write down the 2 under the line and
carry the 1 to the next column. Now move left to the next column, adding (4 1 2) and the
previous carry value of 1 to get 7. Write this value under the line, producing the correct
answer 72. Although as children we learned this algorithm informally, it can, like the
DVR instructions in Figure 1.1, be written formally as an explicit sequence of
instructions. Figure 1.2 shows an algorithm for adding two positive m-digit numbers. It
expresses formally the operations informally described previously. Again, note the three
types of instructions used to construct the algorithm: sequential (Steps 1, 2, 4, 6, 7, 8, and
9), conditional (Step 5), and iterative (Step 3).
We have reached the end of the algorithm, and it has correctly produced the sum
of the two numbers 47 and 25, the three-digit result 072. (A more clever algorithm would
omit the unnecessary leading zero at the beginning of the number if the last carry value is
a zero. That modification is an exercise—Exercise 6—at the end of the chapter.) Try
working through the algorithm shown in Figure 1.2 with another pair of numbers to be
sure that you understand exactly how it functions.
There are also problems for which it is theoretically possible to specify an
algorithm but a computing agent would take so long to execute it that the solution is
essentially useless. For example, to get a computer to play winning chess, we could adopt
a brute force approach. Given a board position as input, the computer would examine
every legal move it could possibly make, then every legal response an opponent could
make to each initial move, then every response it could select to that move, and so on.
This analysis would continue until the game reached a win, lose, or draw position. With
that information, the computer would be able to optimally choose its next move.
If we use a supercomputer that evaluates 1 quadrillion (1015) board positions per
second, it would take about 30,000,000,000,000,000,000,000,000 years for the computer
to make its first move! Obviously, a computer could not use a brute force technique to
play a real chess game. There also exist problems that we do not yet know how to solve
algorithmically. Many of these involve tasks that require a degree of what we term
“intelligence.” For example, after only a few days a baby recognizes the face of his or her
mother from among the many faces he or she sees. In a few months, the baby begins to
develop coordinated sensory and motor control skills and can efficiently plan how to use
them—how to get from the playpen to the toy on the floor without bumping into either
the chair or the desk that is in the way. After a few years, the child begins to develop
powerful language skills and abstract reasoning capabilities.
Thus, algorithmic problem solving has many variations. Sometimes solutions do
not exist; sometimes a solution is too inefficient to be of any use; sometimes a solution is
not yet known. However, discovering an algorithmic solution has enormously important
consequences. As we noted earlier, if we can create a correct and efficient algorithm to
solve a problem, and if we encode it into a programming language, then we can take
advantage of the speed and power of a computer system to automate the solution and
produce the desired result. This is what computer science is all about.
B. Algorithms
The formal definition of an algorithm is rather imposing and contains a number of
important ideas. Let’s take it apart, piece by piece, and analyze each of its separate
points. An algorithm is a collection of operations, and there must be a clear and
unambiguous ordering to these operations. Ordering means that we know which
operation to do first and precisely which operation to do next as each step is successfully
completed. After all, we cannot expect a computing agent to carry out our instructions
correctly if it is confused about which instruction it should be doing next.
With this additional information, most people—even inexperienced cooks—
would understand what to do and could successfully carry out this baking algorithm.
However, there might be some people, perhaps young children, who still do not fully
understand each and every line. For those people, we must go through the simplification
process again and describe the ambiguous steps in even more elementary terms.
Now, even a child should be able to carry out these operations. But if that were
not the case, then we would go through the simplification process yet one more time,
until every operation, every sentence, every word was clearly understood. An
unambiguous operation is one that can be understood and carried out directly by the
computing agent without further simplification or explanation. When an operation is
unambiguous, we call it a primitive operation, or simply a primitive of the computing
agent carrying out the algorithm. An algorithm must be composed entirely of primitives.
Naturally, the primitive operations of different individuals (or machines) vary depending
on their sophistication, experience, and intelligence, as is the case with the cherry pie
recipe, which varies with the baking experience of the person following the instructions.
Hence, an algorithm for one computing agent might not be an algorithm for another.
One of the most important questions we will answer in this text is, What are the
primitive operations of a typical modern computer system? Which operations can a
hardware processor “understand” in the sense of being able to carry out directly, and
which operations must be further refined and simplified? However, it is not enough for an
operation to be understandable. It must also be doable by the computing agent. If an
algorithm tells me to flap my arms really quickly and fly, I understand perfectly well
what it is asking me to do. However, I am incapable of doing it. “Doable” means there
exists a computational process that allows the computing agent to complete that operation
successfully. The formal term for “doable” is effectively computable.
Algorithms solve problems. To know whether a solution is correct, an algorithm
must produce a result that is observable to a user, such as a numerical answer, a new
object, or a change to its environment. Without some observable result, we would not be
able to say whether the algorithm is right or wrong or even if it has completed its
computations. In the case of the DVR algorithm (Figure 1.1), the result will be a set of
recorded TV programs. The addition algorithm (Figure 1.2) produces an m-digit sum.
Another important characteristic of algorithms is that the result must be produced
after the execution of a finite number of operations, and we must guarantee that the
algorithm eventually reaches a statement that says, “Stop, you are done” or something
equivalent. We have already pointed out that the shampooing algorithm was not well
ordered because we did not know which statements to repeat in Step 4. However, even if
we knew which block of statements to repeat, the algorithm would still be incorrect
because it makes no provision to terminate. It will essentially run forever, or until we run
out of hot water, soap, or patience. This is called an infinite loop, and it is a common
error in the design of algorithms.
The instruction sequences in Figures 1.1–1.4 are examples of the types of
algorithmic solutions designed, analyzed, implemented, and tested by computer
scientists, although they are much shorter and simpler. The operations shown in these
figures could be encoded into some appropriate language and given to a computing agent
(such as a personal computer or a robot) to execute. The device would mechanically
follow these instructions and successfully complete the task. The device could do this
without having to understand the creative processes that went into the discovery of the
solution and without knowing the principles and concepts that underlie the problem. The
robot simply follows the steps in the specified order (a required characteristic of
algorithms), successfully completing each operation (another required characteristic), and
ultimately producing the desired result after a finite amount of time (also required).
Just as the Industrial Revolution of the nineteenth century allowed machines to
take over the drudgery of repetitive physical tasks, the “computer revolution” of the
twentieth and twenty-first centuries has enabled us to implement algorithms that
mechanize and automate the drudgery of repetitive mental tasks, such as adding long
columns of numbers, finding one specific name or account number within a massive
database, sorting student records by course number, and retrieving hotel or airline
reservations from a file containing millions of pieces of data. This mechanization process
offers the prospect of enormous increases in productivity. It also frees people to do those
things that humans do much better than computers, such as creating new ideas, setting
policy, doing high-level planning, and determining the significance of the results
produced by a computer. Certainly, these operations are a much more effective use of that
unique computing agent called the human brain.
C. A Brief History of Computing
Although computer science is not simply a study of computers, there is no doubt
that the field was formed and grew in popularity as a direct response to their creation and
widespread use. This section takes a brief look at the historical development of computer
systems. The appearance of some technologies, such as the telephone, the light bulb, and
the first heavier-than-air flight, can be traced directly to a single place, a specific
individual, and an exact instant in time. Examples include the flight of Orville and Wilbur
Wright on December 17, 1903, in Kitty Hawk, North Carolina, and the famous phrase
“Mr. Watson—come here—I want to see you.” uttered by Alexander Graham Bell over
the first telephone on March 10, 1876.
If this were a discussion of the history of mathematics and arithmetic instead of
computer science, it would begin 3,000 years ago with the early work of the Greeks,
Egyptians, Babylonians, Indians, Chinese, and Persians. All these cultures were
interested in and made important contributions to the fields of mathematics, logic, and
numerical computation. For example, the Greeks developed the fields of geometry and
logic; the Babylonians and Egyptians developed numerical methods for generating square
roots, multiplication tables, and trigonometric tables used by early sailors; Indian
mathematicians developed both the base-10 decimal numbering system and the concept
of zero; and in the ninth century, the Persians developed algorithmic problem solving.
The first half of the seventeenth century saw a number of important developments
related to automating and simplifying the drudgery of arithmetic computation. (The
motivation for this work appears to be the sudden increase in scientific research during
the sixteenth and seventeenth centuries in the areas of astronomy, chemistry, and
medicine. This work required the solution of larger and more complex mathematical
problems.) In 1614, the Scotsman John Napier invented logarithms as a way to simplify
difficult mathematical computations. The early seventeenth century also witnessed the
development of new and quite powerful mechanical devices designed to help reduce the
burden of arithmetic. The first slide rule appeared around 1622. In 1642, the French
philosopher and mathematician Blaise Pascal designed and built one of the first
mechanical calculators (named the Pascaline) that could do addition and subtraction.
The famous German mathematician Gottfried Leibnitz (who, along with Isaac
Newton, was one of the inventors of calculus) was also excited by the idea of automatic
computation. He studied the work of Pascal and others, and in 1673, he constructed a
mechanical calculator called Leibnitz’s Wheel that could do not only addition and
subtraction but multiplication and division as well. Both Pascal’s and Leibnitz’s
machines used interlocking mechanical cogs and gears to store numbers and perform
basic arithmetic operations. Considering the state of technology available to Pascal,
Leibnitz, and others in the seventeenth century, these first calculating machines truly
were mechanical wonders.
Surprisingly, the first actual “computing device” to include both these features
was not created for the purposes of mathematical computations. Rather, it was a loom
used for the manufacture of rugs and clothing. It was developed in 1801 by the
Frenchman Joseph Jacquard. Jacquard wanted to automate the weaving process, at the
time a painfully slow and cumbersome task in which each separate row of the pattern had
to be set up by the weaver and an apprentice. Because of this, anything but the most basic
style of clothing was beyond the means of most people.
Jacquard’s loom represented an enormously important stage in the development
of computers. Not only was it the first programmable device, but it showed how the
knowledge of a human expert (in this case, a master weaver) could be captured in
machine-readable form and used to control a machine that accomplished the same task
automatically. Once the program was created, the expert was no longer needed. The
lowliest apprentice could load the cards into the loom, turn it on, and produce a finished,
high-quality product over and over again.
These pioneers had enormous influence on the designers and inventors who came
after them, among them a mathematics professor at Cambridge University named Charles
Babbage. Babbage was interested in automatic computation. In 1823, he extended the
ideas of Pascal and Leibnitz and constructed a working model of the largest and most
sophisticated mechanical calculator of its time. This machine, called the Difference
Engine, could do addition, subtraction, multiplication, and division to six significant
digits, and it could solve polynomial equations and other complex mathematical problems
as well. Babbage tried to construct a larger model of the Difference Engine that would be
capable of working to an accuracy of 20 significant digits, but after 12 years of work he
had to give up his quest. The technology available in the 1820s and 1830s was not
sufficiently advanced to manufacture cogs and gears to the precise tolerances his design
required. Like Leonardo da Vinci’s helicopter or Jules Verne’s atomic submarine,
Babbage’s ideas were fundamentally sound but years ahead of their time. (In 1991, the
London Museum of Science, using Babbage’s original plans, built an actual working
model of the Difference Engine. It was 7 feet high and 11 feet wide, weighed 5 tons, and
had 4,000 moving parts. It worked exactly as Babbage had planned.)
Babbage did not stop his investigations with the Difference Engine. In the 1830s,
he designed a more powerful and general-purpose computational machine that could be
configured to solve a much wider range of numerical problems. His machine had four
basic components: a mill to perform the arithmetic manipulation of data, a store to hold
the data, an operator to process the instructions contained on punched cards, and an
output unit to put the results onto separate punched cards. Although it would be about
110 years before a “real” computer would be built, Babbage’s proposed machine, called
the Analytical Engine, is amazingly similar in design to a modern computer.
Babbage died before a working steam-powered model of his Analytical Engine
could be completed, but his ideas lived on to influence others, and many computer
scientists consider the Analytical Engine the first “true” computer system, even if it
existed only on paper and in Babbage’s dreams. Another person influenced by the work
of Pascal, Jacquard, and Babbage was a young statistician at the U.S. Census Bureau
named Herman Hollerith. Because of the rapid increase in immigration to America at the
end of the nineteenth century, officials estimated that doing the 1890 enumeration
manually would take from 10 to 12 years. The 1900 census would begin before the
previous one was finished. Something had to be done.
Hollerith’s machines were enormously successful, and they were one of the first
examples of the use of automated information processing to solve large-scale, real-world
problems. Whereas the 1880 census required 8 years to be completed, the 1890 census
was finished in about 1 year, even though there was a 26% increase in the U.S.
population during that decade. These machines were not really general-purpose
computers because each machine could do only a single task such as tabulate or sort.
Nevertheless, Hollerith’s card machines were a very clear and very successful
demonstration of the enormous advantages of automated information processing. This
fact was not lost on Hollerith, who left the Census Bureau in 1902 to run his own
Tabulating Machine Company to build and sell these machines. He planned to market his
new product to a country that was just entering the Industrial Revolution and that, like the
Census Bureau, would be generating and processing enormous volumes of inventory,
production, accounting, and sales data. His punched-card machines became the dominant
form of data-processing equipment during the first half of the twentieth century, well into
the 1950s and 1960s. During this period, virtually every major U.S. corporation had data-
processing rooms filled with keypunches, sorters, and tabulators, as well as drawer upon
drawer of punched cards. In 1924, Hollerith’s company changed its name to IBM, and it
eventually evolved into the largest computing company in the world.
World War II created another, quite different set of information-based problems.
Instead of inventory, sales, and payroll, the concerns became ballistics tables, troop
deployment data, and secret codes. A number of research projects were started, funded
largely by the military, to build automatic computing machines to perform these tasks and
assist the Allies in the war effort.
Beginning in 1937, the U.S. Navy and IBM jointly funded a project under the
direction of Professor Howard Aiken at Harvard University to build a computing device
called Mark I. This was a general-purpose, electromechanical programmable computer
that used a mix of relays, magnets, and gears to process and store data. The Mark I was
the first computing device to use the base-2 binary numbering system, which we will
discuss in Chapter 4. It used electromechanical switches and electric current to represent
the two binary values, off for 0, on for 1. Until then, computing machines had used
decimal representation, typically using a 10-toothed gear, each tooth representing one of
the digits from 0 to 9. The Mark I was completed in 1944, about 110 years after
Babbage’s dream of the Analytical Engine, and is generally considered one of the first
working general-purpose computers. The Mark I had a memory capacity of 72 numbers,
and it could be programmed to perform a 23-digit multiplication in the lightning-like time
of 4 seconds. Although laughably slow by modern standards, the Mark I was operational
for almost 15 years, and it carried out a good deal of important mathematical work for the
U.S. during the war.
To help solve this problem, in 1943 the Army initiated a research project with J.
Presper Eckert and John Mauchly of the University of Pennsylvania to build a completely
electronic computing device. The machine, dubbed the ENIAC (Electronic Numerical
Integrator and Calculator), was completed in 1946 (too late to assist in the war effort) and
was the first fully electronic general-purpose programmable computer. This pioneering
machine is shown in Figure 1.7. ENIAC contained 18,000 vacuum tubes and nearly filled
a building; it was 100 feet long and 10 feet high and weighed 30 tons. Because it was
fully electronic, it did not contain any of the slow mechanical components found in Mark
I, and it executed instructions much more rapidly. The ENIAC could add two 10-digit
numbers in about 1/5,000 of a second and could multiply two numbers in 1/300 of a
second, 1,000 times faster than the Mark I.
At about the same time that Colossus was taking form in England, a German
engineer named Konrad Zuse was working on a computing device for the German army.
The machine, code named Z1, was similar in design to the ENIAC—a programmable,
general-purpose, fully electronic computing device. Fortunately for the Allied forces, the
Z1 project was not completed before the end of World War II. Although the machines
just described—ABC, Mark I, ENIAC, Colossus, and Z1—were computers in the fullest
sense of the word (they had memory and were programmable), they did not yet look like
modern computer systems. One more step was necessary, and that step was taken in 1946
by the one individual who was most instrumental in creating the computer as we know it
today, John Von Neumann.
Von Neumann was not only one of the most brilliant mathematicians who ever
lived, he was also a genius in many other areas as well, including experimental physics,
chemistry, economics, and computer science. Von Neumann, who taught at Princeton
University, had worked with Eckert and Mauchly on the ENIAC project at the University
of Pennsylvania. Even though that project was successful, he recognized a number of
fundamental shortcomings in ENIAC. In 1946, he proposed a radically different
computer design based on a model called the stored program computer. Until then, all
computers were programmed externally using wires, connectors, and plugboards. The
memory unit stored only data, not instructions. For each different problem, users had to
rewire virtually the entire computer. For example, the plugboards on the ENIAC
contained 6,000 separate switches, and reprogramming the ENIAC involved specifying
the new settings for all these switches—not a trivial task.
The model of computing proposed by Von Neumann included many other
important features found on all modern computing systems, and to honor him this model
of computation has come to be known as the Von Neumann architecture. We will study
this architecture in great detail in Chapters 4 and 5. Von Neumann’s research group at the
University of Pennsylvania implemented his ideas, and they built one of the first stored
program computers, called EDVAC, in 1949. At about the same time, a stored program
computer called EDSAC was built at Cambridge University in England under the
direction of Professor Maurice Wilkes. The appearance of these machines and others like
them ushered in the modern computer age. Even though they were much slower, bulkier,
and less powerful than our current machines, EDVAC and EDSAC executed programs in
a fashion surprisingly similar to the miniaturized and immensely more powerful
computers of the twentyfirst century. A commercial model of the EDVAC, called
UNIVAC I—the first computer actually sold—was built by Eckert and Mauchly and
delivered to the U.S. Bureau of the Census on March 31, 1951. (It ran for 12 years before
it was retired, shut off for the last time, and moved to the Smithsonian Institution.) This
date marks the true beginning of the “computer age.”
The last 65 or so years of computer development have involved taking the Von
Neumann architecture and improving it in terms of hardware and software. Since 1950,
computer systems development has been primarily an evolutionary process, not a
revolutionary one. The enormous number of changes in computers in recent decades has
made them faster, smaller, cheaper, more reliable, and easier to use but has not drastically
altered their basic underlying structure. The period 1950–1957 (these dates are very
rough approximations) is often called the first generation of computing. This era saw the
appearance of UNIVAC I, the first computer built for sale, and the IBM 701, the first
computer built by the company that would soon become a leader in this new field. These
early systems were similar in design to EDVAC, and they were bulky, expensive, slow,
and unreliable. They used vacuum tubes for processing and storage, and they were
extremely difficult to maintain. The simple act of turning on the machine could blow out
a dozen tubes! For this reason, first-generation machines were used only by trained
personnel and only in specialized locations such as large corporations, government and
university research labs, and military installations, which could provide this expensive
support environment.
The second generation of computing, roughly 1957–1965, heralded a major
change in the size and complexity of computers. In the late 1950s, the bulky vacuum tube
was replaced by a single transistor only a few millimeters in size, and memory was now
constructed using tiny magnetic cores only 1/50th of an inch in diameter. (We will
introduce and describe both devices in Chapter 4.) These technologies not only
dramatically reduced the size of computers but also increased their reliability and reduced
costs. Suddenly, buying and using a computer became a real possibility for some small
and medium-sized businesses, colleges, and government agencies. This was also the era
of the appearance of FORTRAN and COBOL, the first high-level (English-like)
programming languages. (We will study this type of programming language in Chapters
9 and 10.) Now it was no longer necessary to be an electrical engineer to solve a problem
on a computer. One simply needed to learn how to write commands in a high-level
language. The occupation called programmer was born.
This miniaturization process continued into the third generation of computing,
which lasted from about 1965 to 1975. This was the era of the integrated circuit. Rather
than using discrete electronic components, integrated circuits with transistors, resistors,
and capacitors were photographically etched onto a piece of silicon, which further
reduced the size and cost of computers. From building-sized to room-sized, computers
now became desk-sized, and this period saw the birth of the first minicomputer—the
PDP-1 manufactured by the Digital Equipment Corp. It also saw the birth of the software
industry, as companies sprang up to provide programs such as accounting packages and
statistical programs to the ever-increasing numbers of computer users. By the mid-1970s,
computers were no longer a rarity. They were being widely used throughout industry,
government, the military, and education.
The fourth generation, roughly 1975–1985, saw the appearance of the first
microcomputer. Integrated circuit technology had advanced to the point that a complete
computer system could be contained on a single circuit board that you could hold in your
hand. The desk-sized machine of the early 1970s now became a desktop machine,
shrinking to the size of a typewriter. The Altair 8800, the world’s first microcomputer,
appeared in January 1975.
In only a few decades, computers have progressed from the UNIVAC I, which
cost millions of dollars, had a few thousand memory locations, and was capable of only a
few thousand operations per second, to today’s topof-the-line graphics design
workstations with a high-definition, flat panel monitor, trillions of memory cells, massive
amounts of external storage, and enough processing power to execute hundreds of
billions of instructions per second, all for about $1,000. Changes of this magnitude have
never occurred so quickly in any other technology. If the same rate of change had
occurred in the auto industry, beginning with the 1909 Model-T, today’s cars would be
capable of traveling at a speed of 20,000 miles per hour, would get about 1 million miles
per gallon, and would cost about $1.00!
D. Organization of the Text
A study of computer systems can be done at an even higher level. To understand
how a computer works, we do not need to examine the functioning of every one of the
thousands of components inside a machine. Instead, we need only be aware of a few
critical pieces that are essential to our work. From the user’s perspective, everything else
is superfluous. This “user-oriented” view of a computer system and its resources is called
a virtual machine or a virtual environment. A virtual machine is composed only of the
resources that the user perceives rather than of all the hardware resources that actually
exist. This viewpoint is analogous to our level of understanding of what happens under
the hood of a car. There may be thousands of mechanical components inside an
automobile engine, but most of us concern ourselves only with the items reported on the
dashboard—for example, oil pressure, fuel level, engine temperature. This is our “virtual
engine,” and that is all we need or want to know. We are all too happy to leave the
remaining details about engine design to our friendly neighborhood mechanic.
Level 3 (Chapters 6, 7, and 8), titled “The Virtual Machine,” describes how a
virtual environment is created using a component called system software. Chapter 6 takes
a look at the most important and widely used piece of system software on a modern
computer system, the operating system, which controls the overall operation of a
computer and makes it easier for users to access. Chapter 7 then goes on to describe how
this virtual environment can extend beyond the boundaries of a single system as it
examines how to interconnect individual machines into computer networks and
distributed systems that provide users with access to a huge collection of computer
systems and information as well as an enormous number of other users. It is the system
software, and the virtual machine it creates, that makes computer hardware manageable
and usable. Finally, Chapter 8 discusses a critically important component of a virtual
machine—the security system that validates who you are and ensures that you are not
attempting to carry out an improper, illegal, or unsafe operation. As computers become
central to the management of such sensitive data as medical records, military information,
and financial data, this aspect of system software is taking on even greater importance.
There are many programming languages, such as C++, Python, Java, and Perl,
that can be used to encode algorithms. Chapter 10 provides an overview of a number of
different languages and language models in current use, including the functional and
parallel models. Chapter 11 describes how a program written in a high-level
programming language can be translated into the low-level machine language codes first
described in Chapter 5. Finally, Chapter 12 shows that, even when we marshal all the
powerful hardware and software ideas described in the first 11 chapters, problems exist
that cannot be solved algorithmically. Chapter 12 demonstrates that there are, indeed,
limits to computing.
Some computer science professionals are not concerned with building computers,
creating programs, or using any of the applications just described. Instead, they are
interested in the social and cultural impact—both positive and negative—of this ever-
changing technology. The sixth level of this text addresses this important perspective on
computer science. This is not part of the original definition of computer science but has
become an:important area of study. In Level 6, titled “Social Issues” (Chapter 17), we
move to the highest level of abstraction—the view furthest removed from the computer
itself—to discuss social, ethical, legal, and professional issues related to computer and
information technology. These issues are critically important because even individuals
not directly involved in developing or using computers are deeply affected by them, just
as society has been drastically and permanently altered by such technological
developments as telephones, televisions, automobiles, and nuclear power. This last
chapter takes a look at such thorny and difficult topics as computer crime, information
privacy, and intellectual property. It also looks at one of the most important phenomena
supported by this new technology, the creation of social networks such as Facebook,
Twitter, LinkedIn, and Pinterest. Because it is impossible to resolve all the complex
questions that arise in these areas, our intent is simply to raise your awareness and
provide some decisionmaking tools to help you reach your own conclusions.
We first lay out the basic foundations of computer science (Level 1). We then
proceed upward through five distinct layers of abstraction, from extremely low-level
machine details such as electronic circuits and computer hardware (Level 2), through
intermediate levels that address virtual machines (Level 3) and programming languages
and software development (Level 4), to higher levels that investigate computer
applications (Level 5), and address the use and misuse of information technology (Level
6). The material in each level provides a foundation to reveal the beauty and complexity
of a higher and more abstract view of the discipline of computer science.
E. Representing Algorithms
Before presenting any algorithms, we must first make an important decision. How
should we represent them? What notation should we use to express our algorithms so that
they are clear, precise, and unambiguous? One possibility is natural language, the
language we speak and write in our everyday lives. (This could be English, Spanish,
Arabic, Japanese, Swahili, or any language.) This is an obvious choice because it is the
language with which we are most familiar. If we use natural language, then our
algorithms would read much the same as a term paper or an essay. For example, when
expressed in natural language, the addition algorithm in Figure 1.2 might look something
like the paragraph shown in Figure 2.1.
Because natural languages are not sufficiently precise to represent algorithms, we
might be tempted to go to the other extreme. If we are ultimately going to execute our
algorithm on a computer, why not immediately write it out as a computer program using
a high-level programming language such as C++ or Java? If we adopt that approach, the
addition algorithm of Figure 1.2 might start out looking like the program fragment shown
in Figure 2.2. As an algorithmic design language, this notation is also seriously flawed.
During the initial phases of design, we should be thinking at a highly abstract level.
However, using a formal programming language to express our design forces us to deal
immediately with highly detailed language issues, such as punctuation, grammar, and
syntax. For example, the algorithm in Figure 1.2 contains an operation that says, “Set the
value of carry to 0.” This is an easy statement to understand.
Most computer scientists use a notation called pseudocode to design and represent
algorithms. This is a set of English-language constructs designed to more or less resemble
statements in a programming language but that do not actually run on a computer.
Pseudocode represents a compromise between the two extremes of natural and formal
languages. It is simple, highly readable, and has virtually no grammatical rules. (In fact,
pseudocode is sometimes jokingly referred to as “a programming language without the
details.”) However, because it contains only statements that have a well-defined structure,
it is easier to visualize the organization of a pseudocode algorithm than one represented
as long, rambling natural-language paragraphs. In addition, because pseudocode closely
resembles many popular programming languages, the subsequent translation of the
algorithm into a computer program is relatively simple.
Input operations provide the computing agent with data values from the outside
world that it may then use in later instructions. Output operations send results from the
computing agent to the outside world. When the computing agent is a computer,
communications with the outside world are done via the input/output equipment available
on a typical computer, tablet, or smartphone, such as a physical keyboard, virtual keypad,
screen, mouse, printer, hard drive, camera, or touch screen. However, when designing
algorithms, we generally do not concern ourselves with the technical specifications of a
particular device.
Assuming that the algorithm has already computed the area of the circle, this
instruction says to display that value to the outside world. This display may be viewed on
a screen (computer, tablet, smartphone) or printed on paper by a printer. Sometimes we
use an output instruction to display a message in place of the desired results. If, for
example, the computing agent cannot complete a computation because of an error
condition, we might have it execute something like the following operation. (We will use
‘single quotation marks’ to enclose messages so as to distinguish them from such
pseudocode constructs as “variable” and “arithmetic expression,” which are enclosed in
double quotation marks.)
The average miles per gallon algorithm in Figure 2.3 performs a set of operations
once and then stops. It cannot select among alternative operations or perform a block of
instructions more than once. A purely sequential algorithm of the type shown in Figure
2.3 is sometimes termed a straight-line algorithm because it executes its instructions in a
straight line from top to bottom and then stops. Unfortunately, virtually all real-world
problems are not straight-line in nature. They involve nonsequential operations such as
branching and repetition. To allow us to address these more interesting problems, our
pseudocode needs two additional statements to implement conditional and iterative
operations. Together, these two types of operations are called control operations; they
allow us to alter the normal sequential flow of control in an algorithm. As we saw in
Chapter 1, control operations are an essential part of all but the very simplest of
algorithms.
Conditional statements are the “question-asking” operations of an algorithm. They
allow an algorithm to ask a yes/no question and select the next operation to perform on
the basis of the answer to that question. The condition (ci ≥ 10) can be only true or false.
If it is true, then there is a carry into the next column, and we must do the first set of
instructions—subtracting 10 from ci and setting carry to 1. If the condition is false, then
there is no carry—we skip over these two operations and perform the second block of
operations, which simply sets the value of carry to 0.
This instruction initially evaluates the “true/false condition”—called the
continuation condition—to determine if it is true or false. If the condition is true, all
operations from Step i to Step j, inclusive, are executed. This block:of operations is called
the loop body. (Operations within the loop body should be indented so that it is clear to
the reader of the algorithm which operations belong inside the loop.) When the entire
loop body has:finished executing, the algorithm again evaluates the continuation
condition. If it is still true, then the algorithm executes the entire loop body, statements i
through j, again. This looping process continues until the continuation condition
evaluates to false, at which point execution of the loop body terminates and the algorithm
proceeds to the statement immediately following the loop—Step j + 1 in the above
pseudocode. If for some reason the continuation condition never becomes false, then we
have violated one of the fundamental properties of an algorithm, and we have the error,
first mentioned in Chapter 1, called an infinite loop.
F. Examples of Algorithmic Problem Solving
Our first example of algorithmic problem solving addresses a problem originally
posed in Chapter 1 (Exercise 12). That problem asked you to implement an algorithm to
multiply two numbers using repeated addition. Obviously, we need to create a loop that
executes exactly b times, with each execution of the loop adding the value of a to a
running total. These operations will not make any sense (that is, they will not be
effectively computable) until we have explicit values for a and b. So one of the first
operations in our algorithm must be to input these two values.
The original statement of the problem said that the two inputs a and b must satisfy
the following conditions: a ≥ 0 and b ≥ 0. The previous algorithm works for positive
values of a and b, but what happens when either a = 0 or b = 0? Does it still function
correctly? If b = 0, there is no problem. If you look at the while loop, you see that it
continues executing so long as (count< 0) is initially false, and the loop is never executed.
The variable product keeps its initial value of 0, and that is the output that is displayed,
which is the correct answer.
Finding a solution to a given problem is called algorithm discovery, and it is the
most challenging and creative part of the problem-solving process. We developed an
algorithm for a fairly simple problem (multiplication by repeated addition) in Example 1.
Discovering a correct and efficient algorithm to solve a complicated problem can be
difficult and can involve equal parts of intelligence, hard work, past experience, technical
skill, and plain good luck. In the remaining examples, we will develop solutions to a
range of problems to give you more experience in working with algorithms. Studying
these examples, together with lots of practice, is by far the best way to learn creative
problem solving, just as experience and practice are the best ways to learn how to write
essays, hit a golf ball, or repair cars.
The next problem we address involves finding a person’s name given his or her
telephone number, an application often referred to as reverse telephone lookup. This is
the type of important but rather menial repetitive task so well suited to computerization.
(Apple has a half-dozen reverse telephone lookup apps in its App Store.) This algorithm
could be used, for example, to implement Caller ID, in which the caller’s name (if it is
found) is shown on a screen so you can decide whether or not to answer the phone. It can
also be used with missed calls to determine whether the caller is someone with whom you
actually wish to speak. Since there are more than 350 million listed phone numbers in the
United States, reverse telephone lookup can only be implemented using computer-based
search techniques.
Because the numbers in our directory are not in numerical order, there is no clever
way to speed up the search. With a randomly ordered collection, there is no method more
efficient than starting at the beginning and looking at each number in the list, one at a
time, until we either find the one we are looking for or we come to the end of the list.
This rather simple and straightforward technique is called sequential search, and it is the
standard algorithm for searching an unordered list of values. For example, this is how we
would search a bookshelf for a book with a particular title if the books were sorted by the
author’s name instead of by title. It is also the way that we would search a shuffled deck
of cards trying to locate one particular card.
Not only is the algorithm excessively long and highly inefficient, it is also wrong.
If the desired NUMBER is not in the list, this algorithm simply stops (at Step 10,002)
rather than providing the desired result, a message that the number you requested could
not be found. An algorithm is deemed correct only when it produces the correct result for
all possible cases. The problem with this first attempt is that it does not use the powerful
algorithmic concept of iteration. Instead of writing an instruction 10,000 separate times, it
is far better to write it only once and indicate that it is to be repetitively executed 10,000
times, or however many times it takes to obtain the answer. As you learned in the
previous section, much of the power of a computer comes from being able to perform a
loop—the repetitive execution of a block of statements a large number of times. Virtually
every algorithm developed in this text contains at least one loop and most contain many.
The first time through the loop, the value of the index i is 1, so the algorithm
checks (in Step 4) to see whether NUMBER is equal to T1 , the first one on the list. If it
is, then the algorithm writes out the result and sets the variable Found to YES, which
causes the loop in Steps 4 through 7 to terminate. If T1 is not the desired NUMBER, then
i is incremented by 1 (in Step 7) so that it now has the value 2, and the loop is executed
again. The algorithm now checks to see whether NUMBER is equal to T2 , the second
number on the list.
However, the attempt shown in Figure 2.12 is not yet a complete and correct
algorithm because it still does not work correctly when the desired NUMBER does not
appear anywhere in our reverse directory. This final problem can be solved by
terminating the loop either when the desired phone number is found or when we reach the
end of the list. The algorithm can determine exactly what happened by checking the value
of Found when the loop terminates. If the value of Found is NO, then the loop terminated
because the index i exceeded 10,000, and we searched the entire list without finding the
desired NUMBER. The algorithm should then produce an appropriate message.
But because our reverse directory was not sorted into numerical order, we really
had no choice in the design of our search algorithm. However, in real life we can do
much better than sequential search, because these types of directories are sorted
numerically, and we can exploit this fact during the search process. For example, we
know that the digit 5 is about halfway through the set of decimal digits 0–9. So when
looking for the owner of phone number (555) 123-4567 in a sorted reverse directory, we
could start our search somewhere in the middle rather than on the first page. We then see
exactly where we are by looking at the first digit of the phone numbers on the current
page and then move forward or backward toward numbers beginning with 5. This
approach allows us to find the desired telephone number much more quickly than
searching the numbers sequentially from the beginning of the list.
The third algorithm we will develop is similar to the sequential search in Figure
2.13 in that it also searches a list of values. However, this time the algorithm will search
not for a particular value supplied by the user but for the numerically largest value in a
list of numbers. This type of “find largest” algorithm could be used to answer a number
of important questions. (With only a single trivial change, the same algorithm also finds
the smallest value, so a better name for it might be “find extreme values.”) For example,
given a list of examinations, which student received the highest (or lowest) score? Given
a list of annual salaries, which employee earns the most (or least) money? Given a list of
grocery prices from different stores, where should I shop to find the lowest price? All
these questions could be answered by executing this type of algorithm.
In addition to being important in its own right, such an algorithm can also be used
as a “building block” for the construction of solutions to other problems. For example,
the Find Largest algorithm that we will develop could be used to implement a sorting
algorithm that puts an unordered list of numbers into ascending order. (Find and remove
the largest item in list A and move it to the last position of list B. Now repeat these
operations, each time moving the largest remaining number in list A to the last unfilled
slot of list B.
The use of a “building-block” component is a very important concept in computer
science. The examples in this chapter might lead you to believe that every algorithm you
write must be built from only the most elementary and basic of primitives—the
sequential, conditional, and iterative operations shown in Figure 2.9. However, once an
algorithm has been developed, it may itself be used in the construction of other, more
complex algorithms, just as we will use Find Largest in the design of a sorting algorithm.
This is similar to what a builder does when constructing a home from prefabricated units
rather than bricks and boards. Our problem-solving task need not always begin at the
beginning but can instead build on ideas and results that have come before. Every
algorithm that we create becomes, in a sense, a primitive operation of our computing
agent and can be used as part of the solution to other problems. That is why a collection
of useful, prewritten algorithms, called a library, is such an important tool in the design
and development of algorithms.
The last algorithm we develop in this chapter solves a common problem in
computer science called pattern matching. For example, imagine that you have a large
collection of Civil War data files that you want to use as resource material for an article
on Abraham Lincoln. Your first step would probably be to search these files to locate
every occurrence of the text patterns “Abraham Lincoln,” “A. Lincoln,” and “Lincoln.”
The process of searching for a special pattern of symbols within a larger collection of
information is called pattern matching. Most good word processors provide this service
as a menu item called Find or something similar. Furthermore, most web search engines
try to match your search terms to the keywords that appear on a webpage.
Pattern matching can be applied to almost any kind of information, including
graphics, sound, and photographs. For example, an important medical application of
pattern matching is to input an X-ray or CT scan image into a computer and then have the
computer search for special patterns, such as dark spots, which represent conditions that
should be brought to the attention of a physician. This can help speed up the
interpretation of X-rays and avoid the problem of human error caused by fatigue or
oversight. (Computers do not get tired or bored!) One of the most interesting and exciting
applications of pattern matching is to assist microbiologists and geneticists studying and
analyzing the human genome, the basis for all human life. The Human Genome Project
was started in 1990 with the goal of determining the sequence of chemical base pairs that
comprise the human genome. The mammoth project was completed in April 2003, and
today this genetic information is available via online databases to biological and medical
researchers worldwide.
When a match is found, researchers examine the nucleotides located before and
after the probe to see whether they have located the desired gene:and, if so, whether the
gene is defective. Physicians hope someday to:be able to “clip out” a bad sequence and
insert in its place a correct sequence. (This goal took a giant step forward in 2016 with
the development of CRISPR, a powerful genome-editing tool that makes cutting-and-
pasting of DNA sequences far more precise and efficient.) This application of pattern
matching dispels any notion that the algorithms discussed here—sequential search
(Figure 2.13), Find Largest (Figure 2.14), and pattern matching—are nothing more than
academic exercises that serve as examples for introductory classes but have absolutely no
role in solving real-world problems. The algorithms that we have presented (or will
present) are important, either in their own right or as building blocks for algorithms used
by physical scientists, mathematicians, engineers, biologists, and social scientists.
A first draft of an algorithm that implements these ideas is shown in Figure 2.15,
in which not all of the operations are expressed in terms of the basic algorithmic
primitives of Figure 2.9. Although statements like “Set k, the starting location for the
attempted match, to 1” and “Print the value of k, the starting location of the match” are
just fine, the instructions “Attempt to match every character in the pattern beginning at
position k of the text” and “Keep going until we have fallen off the end of the text” are
certainly not primitives. On the contrary, they are high-level operations that, if written out
using only the operations in Figure 2.9, would expand into many instructions.
In computer science, we frequently use abstraction because of the complexity of
hardware and software. For example, abstraction allows us to view the hardware
component called “memory” as a single, indivisible high-level entity without paying heed
to the billions of electronic devices that go into constructing a memory unit. (Chapter 4
examines how computer memories are built, and it makes extensive use of abstraction.)
In algorithm design and software development, we use abstraction whenever we think of
an operation at a high level and temporarily ignore how we might actually implement that
operation. This allows us to decide which details to address now and which to postpone
until later. Viewing an operation at a high level of abstraction and fleshing out the details
of its implementation at a later time constitute an important computer science problem-
solving strategy called top-down design.
G. Attributes of Algorithms
First and foremost, we expect correctness from our algorithms. An algorithm
intended to solve a problem must, again by formal definition, give a result and then halt.
But this is not enough; we also want the result to be a correct solution to the problem.
You could consider this an inherent property of the definition of an algorithm (like a car
being capable of transporting us where we want to go), but it bears emphasizing. An
elegant and efficient algorithm that gives wrong results for the problem at hand is worse
than useless. It can lead to mistakes that are enormously expensive or even fatal.
If an algorithm to solve a problem exists and we determine, after taking into
account all the considerations of the previous paragraph, that it gives correct results, what
more can we ask? To many mathematicians, this would be the end of the matter. After
all, once a solution has been obtained and shown to be correct, it is no longer of interest
(except possibly for use in obtaining solutions to other problems). This is where computer
science differs significantly from theoretical disciplines such as pure mathematics and
begins to take on an “applied” character more closely related to engineering or applied
mathematics. The algorithms developed by computer scientists are not merely of
academic interest. They are also intended to be used.
Suppose, for example, that a road to the top of a mountain is to be built. An
algorithmic solution exists that gives a correct answer for this problem in the sense that a
road is produced: Just build the road straight up the mountain. Problem solved. But the
highway engineer knows that the road must be usable by real traffic and that this
constraint limits the grade of the road. The existence and correctness of the algorithm is
not enough; there are practical considerations as well.
Now let’s consider the real computers on which programs run. Although these
computers can execute instructions very rapidly and have some memory in which to store
information, time and space are not unlimited resources. The computer scientist must be
conscious of the resources consumed by a given algorithm, and if there is a choice
between two (correct) algorithms that perform the same task, the one that uses fewer
resources is preferable. The term used to describe an algorithm’s careful use of resources
is efficiency. Efficiency, in addition to correctness, ease of understanding, and elegance,
is an extremely desirable attribute of an algorithm.
This is not to say that you can’t obtain meaningful information by timing an
algorithm. Using the same input data (for example, searching for the same number in the
same reverse directory) and timing the algorithm on different machines gives a
comparison of machine speeds because the task is identical. Using the same machine and
the same reverse directory, but searching for different numbers, gives an indication of
how the choice of NUMBER affects the algorithm’s running time on that particular
machine. This type of comparative timing is called benchmarking. Benchmarks are useful
for rating one machine against another and for rating how sensitive a particular algorithm
is with respect to variations in input on one particular machine.
H. Measuring Efficiency
The study of the efficiency of algorithms is called the analysis of algorithms, and
it is an important part of computer science. As a first example of the analysis of an
algorithm, we’ll look at the sequential search algorithm that we created to solve the
reverse telephone lookup problem. The pseudocode description of the sequential search
algorithm from Chapter 2 appears in Figure 3.1, where we have assumed that the list
contains n entries instead of 10,000 entries. The central unit of work is the comparison of
the NUMBER being searched for against a single phone number in the list. The essence
of the algorithm is the repetition of this task against successive numbers in the list until
NUMBER is found or the list is exhausted. The comparison takes place at Step 4, within
the loop body composed of Steps 4 through 7. Peripheral tasks include setting the initial
value of the index i and the initial value of Found, writing the output, adjusting Found,
and moving the index forward in the list of numbers. Why are these considered peripheral
tasks?
Setting the initial value of the index and the initial value of Found requires
executing a single instruction, done at Step 2. Writing output requires executing a single
instruction, either at Step 5 if NUMBER is in the list or at Step 9 if NUMBER is not in
the list. Note that instruction 5, although it is part of the loop, writes output at most once
(if NUMBER equals Ti ). Similarly, setting Found to YES occurs at most once (if
NUMBER equals Ti ) at Step 6. We can ignore the small contribution of these single-
instruction executions to the total work done by the algorithm.
When we analyzed the time efficiency of the sequential search algorithm, we
glossed over the contribution of the constant factor for the peripheral work. To see why
this constant factor doesn’t particularly matter, we need to understand a concept called
order of magnitude. The worst-case behavior of the sequential search algorithm on a list
of n items requires n comparisons, and if c is a constant factor representing the peripheral
work, it requires cn total work.
Suppose we have a list of numbers to sort into ascending order—for example, 5,
7, 2, 8, 3. The result of sorting this list is the new list 2, 3, 5, 7, 8. The selection sort
algorithm performs this task. The selection sort “grows” a sorted subsection of the list
from the back to the front. We can look at “snapshots” of the progress of the algorithm on
our sample list, using a vertical line as the marker between the unsorted section at the
front of the list and the sorted section at the back of the list in each case. At first the
sorted subsection is empty; that is, the entire list is unsorted.
To analyze the amount of work the selection sort algorithm does, we must first
decide on the unit of work to count. When we analyzed sequential search, the unit of
work that we measured was the comparison between the item being searched for and the
items in the list. At first glance, there seem to be no comparisons of any kind going on in
the selection sort. Remember, however, that there is a subtask within the selection sort:
the task of finding the largest number in a list. The algorithm from Chapter 2 for finding
the largest value in a list begins by taking the first number in the list as the largest so far.
The largest-so-far value is compared against successive numbers in the list; if a larger
value is found, it becomes the largest so far.
The selection sort algorithm not only does comparisons, it also does exchanges.
Even if the largest number in the unsorted section of the list is already at the end of the
unsorted section, the algorithm exchanges this number with itself. Therefore, the
algorithm does n exchanges, one for each position in the list to put the correct value in
that position. With every exchange, the marker gets moved. However, the work
contributed by exchanges and marker moving is so much less than the amount
contributed by comparisons that it can be ignored. We haven’t talked here about a best
case, a worst case, or an average case for the selection sort. This algorithm does the same
amount of work no matter how the numbers are initially arranged. It has no way to
recognize, for example, that the list might already be sorted at the outset.
However, making assumptions about the size of the input on which an algorithm
will run can be dangerous. A program that runs quickly on small input size may at some
point be selected, perhaps because it seems efficient, to solve instances of the problem
with large input size, at which point the efficiency may go down the drain! (Software that
served Facebook well when it was a startup company with 1,000 active users may not
translate satisfactorily to managing 1.97 billion active users.) Part of the job of program
documentation is to make clear any assumptions or restrictions about the input size the
program was designed to handle.
I. Analysis of Algorithms
In this section, we’ll look at three different algorithms that solve the same
problem—the data cleanup problem—and then do an analysis of each. Suppose a survey
includes a question about the age of the person filling out the survey, and that some
people choose not to answer this question. When data from the survey are entered into the
computer, an entry of 0 is used to denote “no response” because a legitimate value for
age would have to be a positive number. For example, assume that the age data from 10
people who completed the survey are stored in the computer as the following 10-entry
list, where the positions in the list range from 1 (far left) to 10 (far right).
Algorithm 1 to solve the data cleanup problem works in the way we might solve
this problem using a pencil and paper (and an eraser) to modify the list. We proceed
through the list from left to right, pointing with a finger on the left hand to keep our
place, and passing over nonzero values. Every time we encounter a 0 value, we squeeze it
out of the list by copying each remaining data item in the list one cell to the left. We
could use a finger on the right hand to move along the list and point at what to copy next.
The value of legit, originally set to the length of the list, is reduced by 1 every time a 0 is
encountered. (Sounds complicated, but you’ll see that it is easy.)
The second algorithm for solving the data cleanup problem also works as we
might if we decided to write a new list using a pencil and paper. It scans the list from left
to right, copying every legitimate (nonzero) value into a new list that it creates. After this
algorithm is finished, the original list still exists, but so does a new list that contains only
nonzero values. For the third algorithm, imagine that we move one finger along the list
from left to right and another finger from right to left. The left finger slides to the right
over nonzero values. Whenever the left finger encounters a 0 item, we reduce the value of
legit by 1, copy whatever item is at the right finger into the left-finger position, and slide
the right finger one cell left.
The sequential search algorithm searches a list of n items for a particular item; it
is an (n) algorithm. Another algorithm, the binary search algorithm, is more efficient but
it works only when the search list is already sorted. To understand how binary search
operates, let us go back to the problem of searching for NUMBER in a reverse telephone
directory, but now we assume that the directory is sorted in increasing numerical order by
phone number. As we noted in Chapter 2, you would not search for (555) 123-4567 in
such a directory by starting with the first number and proceeding sequentially through the
list. Instead you would look for this number near the middle of the list, and if you didn’t
find it immediately, you would continue your search on the front half or the back half of
the list.
The binary search algorithm works only on a list that has already been sorted. An
unsorted list could be sorted before using a binary search, but sorting also takes a lot of
work, as we have seen. If a list is to be searched only a few times for a few particular
items, then it is more efficient to do sequential search on the unsorted list (a few Θ(n)
tasks). But if the list is to be searched repeatedly, it is more efficient to sort it and then
use binary search: one (n2 ) task and many (lg n) tasks, as opposed to many Θ(n) tasks.
As to space efficiency, binary search, like sequential search, requires only a small amount
of additional storage to keep track of beginning, end, and midpoint positions in the list.
Thus, it is space efficient; in this case, we did not have to sacrifice space efficiency to
gain time efficiency. But we did have to sacrifice generality—binary search works only
on a sorted list whereas sequential search works on any list.
