Chapter 8 Review Question Solutions
1. TRUE or FALSE? An algorithm is a step-by-step sequence of instructions for carrying
out some task.
TRUE
2. TRUE or FALSE? A sequence of instructions for assembling a bookcase does not
qualify as an “algorithm” since the instructions are not written in formal, mathematical
notation.
FALSE
3. TRUE or FALSE? For a precise, clearly-stated problem, there can be only one algorithm
that solves that problem.
FALSE
4. TRUE or FALSE? Big-Oh notation is used to measure the exact number of seconds
required by a particular algorithm when executing on a particular computer.
FALSE
5. TRUE or FALSE? Suppose you have been given a sorted list of 100 names and need to
find a particular name in that list. Using sequential search, it is possible that you might
have to look at every location in the list before finding the desired name.
TRUE
6. TRUE or FALSE? Suppose you have been given a sorted list of 100 names and need to
find a particular name in that list. Using binary search, it is possible that you might have
to look at every location in the list before finding the desired name.
FALSE
7. TRUE or FALSE? Binary search is an example of an O(log N) algorithm, where the
number of items in the list to be searched is N.
8.2
TRUE
8. TRUE or FALSE? One advantage of assembly languages over machine languages is that
they enable the programmer to use words to identify instructions instead of using binarynumber
sequences.
TRUE
9. TRUE or FALSE? JavaScript, C++, and Java are all examples of high-level
programming languages.
TRUE
10. TRUE or FALSE? When a Web page is loaded into a Web browser, JavaScript code in
that page is executed by a JavaScript interpreter that is embedded in the browser.
TRUE
11. An algorithm must be clear to its intended executor in order to be effective. Give an
example of a real-world algorithm that you have encountered and felt was
not clear. Do
you think that the algorithm writer did a poor job, or do you think that the algorithm was
formalized with a different audience in mind? Explain your answer. Then, give an
example of a real-world algorithm that you felt was clearly stated. What features of this
algorithm allow you to understand it more easily?
Student responses will vary.
12. Write an algorithm for directing a person to your house, apartment, or dorm from a
central location. For example, if you live on campus, the directions might originate at a
campus landmark. Assume that the person following the directions is familiar with the
neighborhood or campus.
Student responses will vary.
13. Write an alternative algorithm for directing a person to your residence, but this time,
assume that the person is unfamiliar with the area. How does this condition affect the
way you describe the algorithm?
Student responses will vary.
14. Suppose that you were asked to arrange a group of people in sequence from oldest to
youngest. You must organize a line that begins with the oldest person and continues in
descending order according to age. Describe an algorithm for completing this task.
8.3
Student responses will vary. One possible solution is to apply the algorithm from the
book for finding the oldest person repeatedly. That is, find the oldest person using the
algorithm, and place that person at the front of a line. Then, repeat the process on the
remaining people, placing the next oldest second in line, and so on until all people have
been placed.
15. Suppose that you have been given an O(N) algorithm that averages student grades, where
N is the number of grades. If it takes 1 minute to average 100 grades using the algorithm,
how long would you expect it to take to average 200 grades? 400 grades? Justify your
answer.
Since the algorithm is O(N), doubling the size of the problem should roughly double the
time required for a solution. Thus, 200 grades would require roughly 2 minutes, and 400
grades would require roughly 4 minutes.
16. Suppose you needed to look up a number in your local phone book. Roughly, what is the
population of your city? How many checks would be required, in the worst case, to find
the phone number using sequential search? How many checks would be required, in the
worst case, to find the phone number using binary search?
Student answers will depend upon local population. For sequential search: In the best
case, the name will appear first in the book, requiring only 1 inspection. In the worst
case, the name will appear last in the book, requiring all entries to be inspected. For
binary search: In the best case, the name will appear in the exact middle of the book,
requiring only 1 inspection. There are many worst case positions, including the first and
last positions in the book, requiring log
2 N inspections, where N is the number of entries
in the book.
17. Consider the list of states from Figure 8.5. Which state in the list is the “easiest” to find
using binary search? That is, which state could be located in the fewest number of
checks? Generalize your answer so that it applies to any sorted list of items.
The easiest state to find would be “Missouri” since it appears at the middle position in the
list. In general, the middle position is the easiest since it is the first place inspected.
18. Again, consider the list of states from Figure 8.5. Which state in the list is the “hardest”
to find using binary search? That is, which state would require the largest number of
checks to be located? Generalize your answer so that it applies to any sorted list of items.
One of the hardest states would be “WY”, which appears at the end of the list. Since the
search always checks the middle of the range, the end will only be reached when the
range is reduced to size 1.
19. Refer to the
Newton.html page. How many refinements does Newton’s algorithm
require to compute the square root of 900? 10,000? 152,399,025?
8.4
900 converges to 300 in 10 refinements.
10,000 converges to 100 in 11 refinements.
152,399,025 converges to 12,345 in 18 refinements.
20. Imagine that, while you are using Newton’s algorithm, the approximations converge on
the actual square root of the number. What would happen if you tried to further refine the
square root? Would the value change? Why or why not?
Attempting to further refine the actual square root will produce no change, since
( +
N/ ) / 2 = ( + ) / 2 = .
21. A disadvantage of machine languages is that they are machine dependent. That is, each
machine language is specific to a particular computer, and different computers require
different machine languages. Describe why this is the case.
Machine language instructions correspond to the low-level operations that can be
executed by the hardware of the machine. Since different computers have different
CPUS, register configurations, and ALU operations, their machine languages will differ.
22. Describe two advantages of high-level language programming over machine-language
programming.
High-level languages allow the programmer to code at a higher level of abstraction,
focusing on problem-solving constructs such as conditionals and loops, instead of lowlevel
machine details. In addition, high-level languages are not specific to the underlying
computer’s hardware configuration, so programs are portable across computers.
23. What is the difference between a compiler and an interpreter? What characteristics of an
interpreter make it better suited for executing JavaScript programs?
A compiler is a program that translates an entire high-level language program into its
equivalent machine-language instructions. In contrast, an interpreter translates and
executes the statements in the high-level language program one statement at a time.
While this can make the execution of programs slower, it does provide immediate
feedback as the output of statements can be displayed as they are executed in turn.