Charles Dierbach, John Wiley and Sons (1st Edition)
CHAPTER 1 TEST BANK QUESTIONS
Section 1.1 What is Computer Science? True/False Questions
True or False? Programming defines the field of computer science.
True or False? A representation of a problem that includes the relevant aspects of what is being represented is known as an abstraction.
True or False? In order to solve a problem computationally, two things are needed: a representation that captures all the relevant aspects of the problem, and an algorithm that solves the problem by use of the representation.
True or False? In the Man, Cabbage, Goat and Wolf problem example, the state [W, E, W, E] indicates that the cabbage and wolf are on the east side of the river, and the man and goat are on the west side.
True or False? Regardless of your skills as a programmer, computing problem solving cannot be performed without the knowledge and use of computer algorithms.
True or False? The Traveling Salesman Problem becomes intractable using a brute-force approach for more than twenty cities.
True or False? There are more possible chess games that can be played than the number of grains of sand it would take to fill the universe solid.
True or False? Any algorithm that correctly solves a given problem must solve the problem in a reasonable amount of time; otherwise it is of limited practical use.
True or False? The brute force approach is one of the most widely used algorithmic programming solutions because it is such an efficient problem – solving method.
True or False? Any algorithm that solves a general computational problem is referred to as tractable.
The idea of a brute force approach can be described as
trying all possible solutions to a given problem
a computational approach that uses a great deal of memory
the most efficient, effective, and direct means to solve a problem
An algorithm is of practical use if it
uses the brute force approach
can find a solution a problem in a reasonable amount of time
bypasses the need for computational problem solving
An __algorithm___ is a finite number of clearly described, unambiguous, “doable” steps that can be systematically followed to produce a desired result for given input in a finite amount of time.
Open Response Questions
For the Man, Cabbage, Goat, Wolf problem, assume that each state is represented by a sequence of the form [man, cabbage, goat, wolf], in which a value of 0 indicates that the item is on the east side of the river, and a value of 1 indicates that the item is on the west side. For example, [1,0,1,0] would indicate that the cabbage and wolf are on the east side of the river, and the man and goat on the west side.
(a) Give a list of all the invalid states in this representation.
(b) Give a sequence of states that solves the problem (assuming that all items start on
the east side of the river, and the village is on the west side.)