Assignment

1. Design an algorithm for finding all the factors of a positive integer. For example, in the case of the integer 12, your algorithm should report the values 1, 2, 3, 4, 6, and 12.

2. Does the following program represent an algorithm in the strict sense? Why or why not?

Count = 0
while (Count != 5):
Count = Count + 2

3. Rewrite the following program segment using a repeat structure rather than a while structure. Be sure the new version prints the same values as the original.

Count = 2
while (Count < 7):
print(Count)
Count = Count + 1

4. The following program segment is designed to compute the product of two nonnegative integers X and Y by accumulating the sum of X copies of Y; that is, 3 times 4 is computed by accumulating the sum of three 4s. Is the program segment correct? Explain your answer.

Product = 0
Count = 0
repeat:
Product = Product + Y
Count = Count + 1

until (Count == X)

5. Design an algorithm that, when given an arrangement of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, rearranges the digits so that the new arrangement represents the next larger value that can be represented by these digits (or reports that no such rearrangement exists if no rearrangement produces a larger value). Thus 5647382901 would produce 5647382910.

6. Four prospectors with only one lantern must walk through a mine shaft. At most, two prospectors can travel together and any prospector in the shaft must be with the lantern. The prospectors, named Andrews, Blake, Johnson, and Kelly, can walk through the shaft in one minute, two minutes, four minutes, and eight minutes, respectively. When two walk together they travel at the speed of the slower prospector. How can all four prospectors get through the mine shaft in only 15 minutes? After you have solved this problem, explain how you got your foot in the door.

7. Identify the body of the following loop struc- ture and count the number of times it will be executed. What happens if the test is changed to read "(Count != 6)"?

Count = 1
while (Count != 7):
print(Count)
Count = Count + 3

8. In what sense do the following three steps not constitute an algorithm?

Step 1: Draw a straight line segment between the points with rectangular coordinates (2,5) and (6,11).

Step 2: Draw a straight line segment between the points with rectangular coordinates (1,3) and (3,6).

Step 3: Draw a circle whose center is at the intersection of the previous line segments and whose radius is two

9. Rewrite the following program segment using a while structure rather than a repeat structure. Be sure the new version prints the same values as the original.

Count = 1
repeat:
print(Count)
Count = Count + 1
until (Count >= 7)

10. What is the difference between a formal programming language and a pseudocode?

11. What is the difference between syntax and semantics?

12. What letters are interrogated by the binary search (Figure 5.14) if it is applied to the list A, B, C, D, E, F, G, H, I, J, K, L, M, N, O when searching for the value J? What about search- ing for the value Z?

13. Write an algorithm to take a positive integer n as input and produce the sum of 1+2+..+n. Your algorithm must use while loop control

14. Write an algorithm to take a positive integer n as input and produce the sum of 1+2+..+n. Your algorithm must use recursive control.