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.