Ada Solution Manual

This ? le contains the exercises, hints, and solutions for Chapter 1 of the book †Introduction to the Design and Analysis of Algorithms,† 2nd edition, by A. Levitin. The problems that might be challenging for at least some students are marked by ; those that might be di? cult for a majority of students are marked by . Exercises 1. 1 1. Do some research on al-Khorezmi (also al-Khwarizmi), the man from whose name the word â€Å"algorithm† is derived. In particular, you should learn what the origins of the words â€Å"algorithm† and â€Å"algebra† have in common. 2. Given that the of? cial purpose of the U. S. patent system is the promotion of the â€Å"useful arts,† do you think algorithms are patentable in this country? Should they be? 3. a. Write down driving directions for going from your school to your home with the precision required by an algorithm. b. Write down a recipe for cooking your favorite dish with the precision required by an algorithm. 4. Design an algorithm for swapping two 3 digit non-zero integers n, m. Besides using arithmetic operations, your algorithm should not use any temporary variable. 5. Design an algorithm for computing gcd(m, n) using Euclid’s algorithm. 6. Prove the equality gcd(m, n) = gcd(n, m mod n) for every pair of positive integers m and n. 7. What does Euclid’s algorithm do for a pair of numbers in which the ? rst number is smaller than the second one? What is the largest number of times this can happen during the algorithm’s execution on such an input? 8. What is the smallest and the largest number of divisions possible in the algorithm for determining a prime number? 9. a. Euclid’s algorithm, as presented in Euclid’s treatise, uses subtractions rather than integer divisions. Write a pseudocode for this version of Euclid’s algorithm. b. Euclid’s game (see [Bog]) starts with two unequal positive numbers on the board. Two players move in turn. On each move, a player has to write on the board a positive number equal to the difference of two numbers already on the board; this number must be new, i. e. , different from all the numbers already on the board. The player who cannot move loses the game. Should you choose to move ? rst or second in this game? 10. The extended Euclid’s algorithm determines not only the greatest common divisor d of two positive integers m and n but also integers (not necessarily positive) x and y, such that mx + ny = d. a. Look up a description of the extended Euclid’s algorithm (see, e. g. , [KnuI], p. 13) and implement it in the language of your choice. b. Modify your program for ? nding integer solutions to the Diophantine equation ax + by = c with any set of integer coef? cients a, b, and c. 11. Locker doors There are n lockers in a hallway, numbered sequentially from 1 to n. Initially all the locker doors are closed. You make n passes by the lockers, each time starting with locker #1. On the ith pass, i = 1, 2, . . . n, you toggle the door of every ith locker: if the door is closed, you open it; if it is open, you close it. For example, after the ? rst pass every door is open; on the second pass you only toggle the even-numbered lockers (#2, #4, . . . ) so that after the second pass the even doors are closed and the odd ones are open; the third time through, you close the door of locker #3 (opened from the ? rst pass), open the door of locker #6 (closed from the second pass), and so on. After the last pass, which locker doors are open and which are closed? How many of them are open? 2 Hints to Selected Exercises 1. 1 1. It is probably faster to do this by searching the Web, but your library should be able to help, too. 2. One can ? nd arguments supporting either view. There is a well-established principle pertinent to the matter, though: scienti? c facts or mathematical expressions of them are not patentable. (Why do you think this is the case? ) But should this preclude granting patents for all algorithms? 3. You may assume that you are writing your algorithms for a human rather than a machine. Still, make sure that your descriptions do not contain obvious ambiguities. Knuth ([KnuI], p. 6) provides an interesting comparison between cooking recipes and algorithms. 6. Prove that if d divides both m and n (i. e. , m = sd and n = td for some positive integers s and t), then it also divides both n and r = m mod n and vice versa. Use the formula m = qn + r (0 ? r < n) and the fact that if d divides two integers u and v, it also divides u + v and u ? v. (Why? ) 7. Perform one iteration of the algorithm for two arbitrarily chosen integers m < n. 9. a. Use the equality gcd(m, n) = gcd(m ? n, n) for m ? n > 0. b. The key is to ? gure out the total number of distinct numbers that can be written on the board, starting with an initial pair m, n where m > n ? 1. You should exploit a connection of this question to the question of part (a). Considering small examples, especially those with n = 1 and n = 2, should help, too. 10. Of course, for some coef? cients, the equation will have no solutions. 11. Tracing the algorithm by hand for, say, n = 10 and studying its outcome should help answering both questions. 3 Solutions to Exercises 1. 1. Al-Khwarizmi (9th century C. E. ) was a great Arabic scholar, most famous for his algebra textbook. In fact, the word â€Å"algebra† is derived from the Arabic title of this book while the word â€Å"algorithm† is derived from a translation of Al-Khwarizmi’s last name (see, e. g. , [KnuI], pp. 1-2, [Knu96], pp. 88-92, 114). 2. This legal issue has yet to be settled. The current lega l state of a? airs distinguishes mathematical algorithms, which are not patentable, from other algorithms, which may be patentable if implemented as computer programs (e. g. , [Cha00]). 3. n/a 4. ALGORITHM Exchange valueswithoutT(a,b) //exchange the two values without using temporary variable //Input:two numbers a,b. //Output:exchange values of a,b a=a+b; b=a-b; a=a-b; ALGORITHM Euclid (m,n) // Computes gcd(m. n) by Euclid’s algorithm // Input: Two nonnegative, not-both-zero integers m and n // Output : Greatest common divisor of m and n while n ? 0 do r 5. 6. Let us ? rst prove that if d divides two integers u and v, it also divides both u + v and u ? v. By de? nition of division, there exist integers s and t such that u = sd and v = td. Therefore u  ± v = sd  ± td = (s  ± t)d, i. . , d divides both u + v and u ? v. 4 Also note that if d divides u, it also divides any integer multiple ku of u. Indeed, since d divides u, u = sd. Hence ku = k(sd) = (ks)d, i. e. , d divides ku. Now we can prove the assertion in question. For any pair of positive integers m and n, if d divides both m and n, it also divides both n and r = m mod n = m ? qn. Similarly, if d divides bot h n and r = m mod n = m ? qn, it also divides both m = r + qn and n. Thus, the two pairs (m, n) and (n, r) have the same ? nite nonempty set of common divisors, including the largest element in the set, i. . , gcd(m, n) = gcd(n, r). 7. For any input pair m, n such that 0 ? m < n, Euclid’s algorithm simply swaps the numbers on the ? rst iteration: gcd(m, n) = gcd(n, m) because m mod n = m if m < n. Such a swap can happen only once since gcd(m, n) = gcd(n, m mod n) implies that the ? rst number of the new pair (n) will be greater than its second number (m mod n) after every iteration of the algorithm. 8. Algorithm: While i 0) && (numbers[j-1] > index)) { numbers[j] = numbers[j-1]; j = j – 1; } numbers[j] = index; } } 3. Align the pattern with the beginning of the text. Compare the corresponding characters of the pattern and the text left-to right until either all the pattern characters are matched (then stop–the search is successful) or the algorithm runs out of the text’s characters (then stop–the search is unsuccessful) or a mismatching pair of characters is encountered. In the latter case, shift the pattern one position to the right and resume the comparisons. 4. a. If we represent each of the river’s banks and each of the two islands by vertices and the bridges by edges, we will get the following graph: 0 a a b c b c d d (This is, in fact, a multigraph, not a graph, because it has more than one edge between the same pair of vertices. But this doesn’t matter for the issue at hand. ) The question is whether there exists a path (i. e. , a sequence of adjacent vertices) in this multigraph that traverses all the edges exactly once and returns to a starting vertex. Such paths are called Eulerian circuits; if a path traverses all the edges exactly once but does not return to its starting vertex, it is called an Eulerian path. b. Euler proved that an Eulerian circuit exists in a connected (multi)graph if and only if all its vertices have even degrees, where the degree of a vertex is de? ned as the number of edges for which it is an endpoint. Also, an Eulerian path exists in a connected (multi)graph if and only if it has exactly two vertices of odd degrees; such a path must start at one of those two vertices and end at the other. Hence, for the multigraph of the puzzle, there exists neither an Eulerian circuit nor an Eulerian path because all its four vertices have odd degrees. If we are to be satis? d with an Eulerian path, two of the multigraph’s vertices must be made even. This can be accomplished by adding one new bridge connecting the same places as the existing bridges. For example, a new bridge between the two islands would make possible, among others, the walk a ? b ? c ? a ? b ? d ? c ? b ? d a a b c b c d d If we want a walk that returns to its starting point, all the vertices in the 21 corres ponding multigraph must be even. Since a new bridge/edge changes the parity of two vertices, at least two new bridges/edges will be needed. For example, here is one such â€Å"enhancement†: a a c b c d d This would make possible a ? b ? c ? a ? b ? d ? c ? b ? d ? a, among several other such walks. 5. A Hamiltonian circuit is marked on the graph below: 6. a. At least three â€Å"reasonable†criteria come to mind: the fastest trip, a trip with the smallest number of train stops, and a trip that requires the smallest number of train changes. Note that the ? rst criterion requires the information about the expected traveling time between stations and the time needed for train changes whereas the other two criteria do not require such information. . A natural approach is to mimic subway plans by representing stations by vertices of a graph, with two vertices connected by an edge if there is a train line between the corresponding stations. If the time spent on changing a tra in is to be taken into account (e. g. , because the station in question is on more than one line), the station should be represented by more then one vertex. 22 7. procedure Queens(unused, board, col, N) if col > N then print board else{ col