SOLUTION MANUAL
All Chapters Included
Artificial
Intelligence A
Modern Approach
Fourth Edition
Stuart J. Russell and Peter Norvig
with contributions from
Nalin Chhibber, Ernest Davis, Nicholas J. Hay, Jared
Moore, Alex Rudnick, Mehran Sahami, Xiaocheng Mesut
Yang, and Albert Yu
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
,EXERCISES 1
INTRODUCTION
Note that for many of the questions in this chapter, we give references where
answers can be found rather than writing them out—the full answers would be far
too long.
1.1 What Is AI?
Exercise 1.1.#DEFA
Define in your own words: (a) intelligence, (b) artificial intelligence, (c) agent, (d) ra-
tionality, (e) logical reasoning.
a. Dictionary definitions of intelligence talk about “the capacity to acquire and
apply knowledge” or “the faculty of thought and reason” or “the ability to
comprehend and profit from experience.” These are all reasonable answers,
but if we want something quantifiable we would use something like “the ability
to act successfully across a wide range of objectives in complex environments.”
b. We define artificial intelligence as the study and construction of agent
programs that perform well in a given class of environments, for a given agent
architecture; they do the right thing. An important part of that is dealing with
the uncertainty of what the current state is, what the outcome of possible
actions might be, and what is it that we really desire.
c. We define an agent as an entity that takes action in response to percepts from
an envi- ronment.
d. We define rationality as the property of a system which does the “right
thing” given what it knows. See Section 2.2 for a more complete discussion.
The basic concept is perfect rationality; Section ?? describes the impossibility
of achieving perfect rational- ity and proposes an alternative definition.
e. We define logical reasoning as the a process of deriving new sentences from
old, such that the new sentences are necessarily true if the old ones are true.
(Notice that does not refer to any specific syntax or formal language, but it does
require a well-defined notion of truth.)
Exercise 1.1.#TURI
Read Turing’s original paper on AI (Turing, 1950). In the paper, he discusses several
objections to his proposed enterprise and his test for intelligence. Which objections still carry
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
, Section 1.1 What Is AI? 3
weight? Are his refutations valid? Can you think of new objections arising from develop-
ments since he wrote the paper? In the paper, he predicts that, by the year 2000, a computer
will have a 30% chance of passing a five-minute Turing Test with an unskilled interrogator.
What chance do you think a computer would have today? In another 25 years?
See the solution for exercise 26.1 for some discussion of potential objections.
The probability of fooling an interrogator depends on just how unskilled the
interrogator is. A few entrants in the Loebner prize competitions have fooled
judges, although if you look at the transcripts, it looks like the judges were having
fun rather than taking their job seriously. There certainly have been examples of a
chatbot or other online agent fooling humans. For example, see the description of
the Julia chatbot at www.lazytd.com/lti/ julia/. We’d say the chance today is
something like 10%, with the variation depending more on the skill of the
interrogator rather than the program. In 25 years, we expect that the
entertainment industry (movies, video games, commercials) will have made
sufficient investments in artificial actors to create very credible impersonators.
Note that governments and international organizations are seriously considering
rules that require AI systems to be identified as such. In California, it is already
illegal for machines to impersonate humans in certain circumstances.
Exercise 1.1.#REFL
Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
Yes, they are rational, because slower, deliberative actions would tend to result
in more damage to the hand. If “intelligent” means “applying knowledge” or “using
thought and reasoning” then it does not require intelligence to make a reflex action.
Exercise 1.1.#SYAI
To what extent are the following computer systems instances of artificial intelligence:
• Supermarket bar code scanners.
• Web search engines.
• Voice-activated telephone menus.
• Spelling and grammar correction features in word processing programs.
• Internet routing algorithms that respond dynamically to the state of the network.
• Although bar code scanning is in a sense computer vision, these are not AI
systems. The problem of reading a bar code is an extremely limited and
artificial form of visual interpretation, and it has been carefully designed to be
as simple as possible, given the hardware.
• In many respects. The problem of determining the relevance of a web page to
a query is a problem in natural language understanding, and the techniques
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
, 4 Exercises 1 Introduction
are related to those
we will discuss in Chapters 23 and 24. Search engines also use clustering
techniques analogous to those we discuss in Chapter 20. Likewise, other
functionalities provided by a search engines use intelligent techniques; for
instance, the spelling corrector uses a form of data mining based on observing
users’ corrections of their own spelling errors. On the other hand, the problem
of indexing billions of web pages in a way that allows retrieval in seconds is a
problem in database design, not in artificial intelligence.
• To a limited extent. Such menus tends to use vocabularies which are very limited –
e.g. the digits, “Yes”, and “No” — and within the designers’ control, which
greatly simplifies the problem. On the other hand, the programs must deal with
an uncontrolled space of all kinds of voices and accents. Modern digital
assistants like Siri and the Google Assistant make more use of artificial
intelligence techniques, but still have a limited repetoire.
• Slightly at most. The spelling correction feature here is done by string
comparison to a fixed dictionary. The grammar correction is more
sophisticated as it need to use a set of rather complex rules reflecting the
structure of natural language, but still this is a very limited and fixed task.
The spelling correctors in search engines would be considered much more
nearly instances of AI than the Word spelling corrector are, first, because the
task is much more dynamic – search engine spelling correctors deal very
effectively with proper names, which are detected dynamically from user
queries – and, second, because of the technique used – data mining from user
queries vs. string matching.
• This is borderline. There is something to be said for viewing these as intelligent
agents working in cyberspace. The task is sophisticated, the information
available is partial, the techniques are heuristic (not guaranteed optimal), and
the state of the world is dynamic. All of these are characteristic of intelligent
activities. On the other hand, the task is very far from those normally carried
out in human cognition. In recent years there have been suggestions to base
more core algorithmic work on machine learning.
Exercise 1.1.#COGN
Many of the computational models of cognitive activities that have been proposed involve
quite complex mathematical operations, such as convolving an image with a Gaussian or
finding a minimum of the entropy function. Most humans (and certainly all animals) never
learn this kind of mathematics at all, almost no one learns it before college, and almost no
one can compute the convolution of a function with a Gaussian in their head. What sense
does it make to say that the “vision system” is doing this kind of mathematics, whereas the
actual person has no idea how to do it?
Presumably the brain has evolved so as to carry out this operations on visual
images, but the mechanism is only accessible for one particular purpose in this
particular cognitive task of image processing. Until about two centuries ago there
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
All Chapters Included
Artificial
Intelligence A
Modern Approach
Fourth Edition
Stuart J. Russell and Peter Norvig
with contributions from
Nalin Chhibber, Ernest Davis, Nicholas J. Hay, Jared
Moore, Alex Rudnick, Mehran Sahami, Xiaocheng Mesut
Yang, and Albert Yu
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
,EXERCISES 1
INTRODUCTION
Note that for many of the questions in this chapter, we give references where
answers can be found rather than writing them out—the full answers would be far
too long.
1.1 What Is AI?
Exercise 1.1.#DEFA
Define in your own words: (a) intelligence, (b) artificial intelligence, (c) agent, (d) ra-
tionality, (e) logical reasoning.
a. Dictionary definitions of intelligence talk about “the capacity to acquire and
apply knowledge” or “the faculty of thought and reason” or “the ability to
comprehend and profit from experience.” These are all reasonable answers,
but if we want something quantifiable we would use something like “the ability
to act successfully across a wide range of objectives in complex environments.”
b. We define artificial intelligence as the study and construction of agent
programs that perform well in a given class of environments, for a given agent
architecture; they do the right thing. An important part of that is dealing with
the uncertainty of what the current state is, what the outcome of possible
actions might be, and what is it that we really desire.
c. We define an agent as an entity that takes action in response to percepts from
an envi- ronment.
d. We define rationality as the property of a system which does the “right
thing” given what it knows. See Section 2.2 for a more complete discussion.
The basic concept is perfect rationality; Section ?? describes the impossibility
of achieving perfect rational- ity and proposes an alternative definition.
e. We define logical reasoning as the a process of deriving new sentences from
old, such that the new sentences are necessarily true if the old ones are true.
(Notice that does not refer to any specific syntax or formal language, but it does
require a well-defined notion of truth.)
Exercise 1.1.#TURI
Read Turing’s original paper on AI (Turing, 1950). In the paper, he discusses several
objections to his proposed enterprise and his test for intelligence. Which objections still carry
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
, Section 1.1 What Is AI? 3
weight? Are his refutations valid? Can you think of new objections arising from develop-
ments since he wrote the paper? In the paper, he predicts that, by the year 2000, a computer
will have a 30% chance of passing a five-minute Turing Test with an unskilled interrogator.
What chance do you think a computer would have today? In another 25 years?
See the solution for exercise 26.1 for some discussion of potential objections.
The probability of fooling an interrogator depends on just how unskilled the
interrogator is. A few entrants in the Loebner prize competitions have fooled
judges, although if you look at the transcripts, it looks like the judges were having
fun rather than taking their job seriously. There certainly have been examples of a
chatbot or other online agent fooling humans. For example, see the description of
the Julia chatbot at www.lazytd.com/lti/ julia/. We’d say the chance today is
something like 10%, with the variation depending more on the skill of the
interrogator rather than the program. In 25 years, we expect that the
entertainment industry (movies, video games, commercials) will have made
sufficient investments in artificial actors to create very credible impersonators.
Note that governments and international organizations are seriously considering
rules that require AI systems to be identified as such. In California, it is already
illegal for machines to impersonate humans in certain circumstances.
Exercise 1.1.#REFL
Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
Yes, they are rational, because slower, deliberative actions would tend to result
in more damage to the hand. If “intelligent” means “applying knowledge” or “using
thought and reasoning” then it does not require intelligence to make a reflex action.
Exercise 1.1.#SYAI
To what extent are the following computer systems instances of artificial intelligence:
• Supermarket bar code scanners.
• Web search engines.
• Voice-activated telephone menus.
• Spelling and grammar correction features in word processing programs.
• Internet routing algorithms that respond dynamically to the state of the network.
• Although bar code scanning is in a sense computer vision, these are not AI
systems. The problem of reading a bar code is an extremely limited and
artificial form of visual interpretation, and it has been carefully designed to be
as simple as possible, given the hardware.
• In many respects. The problem of determining the relevance of a web page to
a query is a problem in natural language understanding, and the techniques
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
, 4 Exercises 1 Introduction
are related to those
we will discuss in Chapters 23 and 24. Search engines also use clustering
techniques analogous to those we discuss in Chapter 20. Likewise, other
functionalities provided by a search engines use intelligent techniques; for
instance, the spelling corrector uses a form of data mining based on observing
users’ corrections of their own spelling errors. On the other hand, the problem
of indexing billions of web pages in a way that allows retrieval in seconds is a
problem in database design, not in artificial intelligence.
• To a limited extent. Such menus tends to use vocabularies which are very limited –
e.g. the digits, “Yes”, and “No” — and within the designers’ control, which
greatly simplifies the problem. On the other hand, the programs must deal with
an uncontrolled space of all kinds of voices and accents. Modern digital
assistants like Siri and the Google Assistant make more use of artificial
intelligence techniques, but still have a limited repetoire.
• Slightly at most. The spelling correction feature here is done by string
comparison to a fixed dictionary. The grammar correction is more
sophisticated as it need to use a set of rather complex rules reflecting the
structure of natural language, but still this is a very limited and fixed task.
The spelling correctors in search engines would be considered much more
nearly instances of AI than the Word spelling corrector are, first, because the
task is much more dynamic – search engine spelling correctors deal very
effectively with proper names, which are detected dynamically from user
queries – and, second, because of the technique used – data mining from user
queries vs. string matching.
• This is borderline. There is something to be said for viewing these as intelligent
agents working in cyberspace. The task is sophisticated, the information
available is partial, the techniques are heuristic (not guaranteed optimal), and
the state of the world is dynamic. All of these are characteristic of intelligent
activities. On the other hand, the task is very far from those normally carried
out in human cognition. In recent years there have been suggestions to base
more core algorithmic work on machine learning.
Exercise 1.1.#COGN
Many of the computational models of cognitive activities that have been proposed involve
quite complex mathematical operations, such as convolving an image with a Gaussian or
finding a minimum of the entropy function. Most humans (and certainly all animals) never
learn this kind of mathematics at all, almost no one learns it before college, and almost no
one can compute the convolution of a function with a Gaussian in their head. What sense
does it make to say that the “vision system” is doing this kind of mathematics, whereas the
actual person has no idea how to do it?
Presumably the brain has evolved so as to carry out this operations on visual
images, but the mechanism is only accessible for one particular purpose in this
particular cognitive task of image processing. Until about two centuries ago there
© 2023 Pearson Education, Hoboken, NJ. All rights reserved.
