Chapter 5

Explain the distinction between an ambiguity in a proposed algorithm and an ambiguity in the representation of an algorithm.

Describe how the use of primitives helps remove ambiguities in an algorithm's representation.

Select a subject with which you are familiar and design a pseudocode for giving directions in that subject. In particular, describe the primitives you would use and the syntax you would use to represent them. (If you are having trouble thinking of a subject, try sports, arts, or crafts.)

Does the following program represent an algorithm in the strict sense? Why or why not? Count \(=0\) white (Count != 5): Count \(=\) Count \(+2\)

In what sense do the following three steps not constitute an algorithm? Step 1: Draw a circle with center coordinates \((2,5)\) and radius 3 . Step 2: Draw a circle with center coordinates \((6,5)\) and radius \(5 .\) Step 3: Draw a line segment whose endpoints are at the intersections of the previous two circles.

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. Initialization: num \(=0\) while \((\) num \(<50)\) : if (num is Odd) : print (num is Odd) \(=\) num \(+1\) num \(=\) num \(+1\)

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. num \(=100\) repeat: print (num) num \(=\) num \(-1\) until \((\) num \(>0)\)

What must be done to translate a posttest loop expressed in the form repeat: (...) until (...) into an equivalent posttest loop expressed in the form do: (...) while (...)

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 .

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 .

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

What is the difference between syntax and semantics?

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.

Two bees, named Romeo and Juliet, live in different hives but have met and fallen in love. On a windless spring morning, they simultaneously leave their respective hives to visit each other. Their routes meet at a point 50 meters from the closest hive, but they fail to see each other and continue on to their destinations. At their destinations, they spend the same amount of time to discover that the other is not home and begin their return trips. On their return trips, they meet at a point that is 20 meters from the closest hive. This time they see each other and have a picnic lunch before returning home. How far apart are the two hives? After you have solved this problem, explain how you got your foot in the door.

Design an algorithm that, given two strings of characters, tests whether the second string is the same as the first string or not.

After performing many sequential searches on a list of 6,000 entries, what would you expect to be the average number of times that the target value would have been compared to a list entry? What if the search algorithm was the binary search?

Identify the termination condition in each of the following iterative statements. a. while (Count \(<5\) ): b. repeat: until (Count \(==1\) ) c. while \(((\) Count \(<5)\) and \((\) Total \(<56))\) :

Identify the body of the following loop structure 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\)

What problems do you expect to arise if the following program is implemented on a computer? (Hint: Remember the problem of round-off errors associated with floating-point arithmetic.) Count = one_tenth repeat: print (Count) Count = Count \(+\) one_tenth until (Count == 1)

Design an algorithm to generate the sequence of positive integers (in increasing order) whose only prime divisors are 2 and 3 ; that is, your program should produce the sequence \(2,3,4,6,8\), \(9,12,16,18,24,27, \ldots\). Does your program represent an algorithm in the strict sense?

A positive integer is called an Armstrong number if the sum of the cubes of the individual digits of that number is equal to that number itself. For example, the sum of the cubes of the individual digits of 153 is \((1 \times 1 \times 1)+(5 \times 5 \times 5)+(3 \times 3 \times 3)=153\). Hence, 153 is an Armstrong number. Design an algorithm that checks whether a given number is an Armstrong number or not.

a. Suppose you must sort a list of five names, and you have already designed an algorithm that sorts a list of four names. Design an algorithm to sort the list of five names by taking advantage of the previously designed algorithm. b. Design a recursive algorithm to sort arbitrary lists of names based on the technique used in (a).

The puzzle called the Towers of Hanoi consists of three pegs, one of which contains several rings stacked in order of descending diameter from bottom to top. The problem is to move the stack of rings to another peg. You are allowed to move only one ring at a time, and at no time is a ring to be placed on top of a smaller one. Observe that if the puzzle involved only one ring, it would be extremely easy. Moreover, when faced with the problem of moving several rings, if you could move all but the largest ring to another peg, the largest ring could then be placed on the third peg, and then the problem would be to move the remaining rings on top of it. Using this observation, develop a recursive algorithm for solving the Towers of Hanoi puzzle for an arbitrary number of rings.

Develop two algorithms, one based on a loop structure and the other on a recursive structure, to print the daily salary of a worker who each day is paid twice the previous day's salary (starting with one penny for the first day's work) for a 30 -day period. What problems relating to number storage are you likely to encounter if you implement your solutions on an actual machine?

Design an algorithm to find the square root of a positive number by starting with the number itself as the first guess and repeatedly producing a new guess from the previous one by averaging the previous guess with the result of dividing the original number by the previous guess. Analyze the control of this repetitive process. In particular, what condition should terminate the repetition?

Design an algorithm to find the square root of a positive number by starting with the number itself as the first guess and repeatedly producing a new guess from the previous one by averaging the previous guess with the result of dividing the original number by the previous guess. Analyze the control of this repetitive process. In particular, what condition should terminate the repetition?

Design an algorithm that, given a list of names, finds the longest name in the list. Use the for loop structure. Determine what your solution does if there are several "longest" names in the list. In particular, what would your algorithm do if all the names had the same length?

Design an algorithm that, given a list of five or more numbers, finds the five smallest and five largest numbers in the list without sorting the entire list.

What is the largest number of entries that are interrogated if the binary search algorithm (Figure 5.14) is applied to a list of 4000 names? How does this compare to the sequential search (Figure 5.6)?

Use big-theta notation to classify the traditional grade school algorithms for addition and multiplication. That is, if asked to add two numbers each having n digits, how many individual additions must be performed. If requested to multiply two n-digit numbers, how many individual multiplications are required?

From a given a list of 1000 integers from 1 to 1000 , extract pairs of numbers whose product is 2424 .

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 \(4 \mathrm{~s}\). Is the program segment correct? Explain your answer. Product \(=0\) Count \(=0\) repeat: Product \(=\) Product \(+Y\) Count \(=\) Count \(+1\) until (Count \(==X\) )