Questions & Exercises 1. A primitive in one context might turn out to be a composite of primitives in another. For instance, our while statement is a primitive in our pseudo- code, yet it is ultimately implemented as a composite of machine-language instructions. Give two examples of this phenomenon in a non-computer setting. 2. In what sense is the construction of functions the construction of primitives? 3. The Euclidean algorithm finds the greatest common divisor of two posi- tive integers X and Y by the following process: As long as the value of neither X nor Y is zero, assign the larger the remainder of dividing the larger by the smaller. The greatest common divisor, if it exists, will be the remaining non-zero value. Express this algorithm in our pseudocode. 4. Describe a collection of primitives that are used in a subject other than computer programming. Questions & Exercises 1. a. Find an algorithm for solving the following problem: Given a posi- tive integer n, find the list of positive integers whose product is the largest among all the lists of positive integers whose sum is n. For example, if n is 4, the desired list is 2, 2 because 2 2 is larger than 1 X 1 X 1 X 1, 2 X 1 X 1, and 3 x 1. If n is 5, the desired list is 2, 3. b. What is the desired list if n = 2001? c. Explain how you got your foot in the door. Chapter 5 Algorithms 2. a. Suppose we are given a checkerboard consisting of 2" rows and 2" columns of squares, for some positive integer n, and a box of L-shaped tiles, each of which can cover exactly three squares on the board. If any single square is cut out of the board, can we cover the remaining board with tiles such that tiles do not overlap or hang off the edge of the board? b. Explain how your solution to (a) can be used to show that 22 - 1 is divisible by 3 for all positive integers n. c. How are (a) and (b) related to Polya's phases of problem solving? 3. Decode the following message, then explain how you got your foot in the door. Pdeo eo pda yknnayp wjosan. 4. Would you be following a top-down methodology if you attempted to solve a picture puzzle merely by pouring the pieces out on a table and trying to piece them together? Would your answer change if you looked at the puzzle box to see what the entire picture was supposed to look like? Questions & Exercises 1. Modify the sequential search function in Figure 5.6 to allow for lists that are not sorted. 2. Convert the pseudocode routine Z=0 X = 1 while (X < 6): Z-Z+X X = x + 1 to an equivalent routine using a repeat statement. 3. Some of the popular programming languages today use the syntax while (...) do (...) to represent a pretest loop and the syntax do (...) while (...) to represent a posttest loop. Although elegant in design, what problems could result from such similarities? 4. Suppose the insertion sort as presented in Figure 5.11 was applied to the list Gene, Cheryl, Alice, and Brenda. Describe the organization of the list at the end of each execution of the body of the outer while structure. 5. Why would we not want to change the phrase "greater than" in the while statement in Figure 5.11 to "greater than or equal to"? 6. A variation of the insertion sort algorithm is the selection sort. It begins by selecting the smallest entry in the list and moving it to the front. It then selects the smallest entry from the remaining entries in the list and moves it to the second position in the list. By repeatedly selecting the smallest entry from the remaining portion of the list and moving that entry forward, the sorted version of the list grows from the front of the list, while the back portion of the list consisting of the remaining unsorted entries shrinks. Use our pseudocode to express a function similar to that in Figure 5.11 for sorting a list using the selection sort algorithm. 5.5 Recursive Structures 233 7. Another well-known sorting algorithm is the bubble sort. It is based on the process of repeatedly comparing two adjacent names and interchang- ing them if they are not in the correct order relative to each other. Let us suppose that the list in question has n entries. The bubble sort would begin by comparing (and possibly interchanging) the entries in positions n and n-1. Then, it would consider the entries in positions n - 1 and n - 2, and continue moving forward in the list until the first and sec- ond entries in the list had been compared (and possibly interchanged). Observe that this pass through the list will pull the smallest entry to the front of the list. Likewise, another such pass will ensure that the next to the smallest entry will be pulled to the second position in the list. Thus, by making a total of n - 1 passes through the list, the entire list will be sorted. (If one watches the algorithm at work, one sees the small entries bubble to the top of the list-an observation from which the algorithm gets its name.) Use our pseudocode to express a function similar to that in Figure 5.11 for sorting a list using the bubble sort algorithm. 1. What names are interrogated by the binary search (Figure 5.14) when searching for the name Joe in the list Alice, Brenda, Carol, Duane, Evelyn, Fred, George, Henry, Irene, Joe, Karl, Larry, Mary, Nancy, and Oliver? 2. What is the maximum number of entries that must be interrogated when applying the binary search to a list of 200 entries? What about a list of 100,000 entries? Questions & Exercises 3. What sequence of numbers would be printed by the following recursive function if we started it with N assigned the value 1? def Exercise (N): print (N) if (N < 3): Exercise (N+1) print(N) 4. What is the termination condition in the recursive function of question 3?