Exa) m (elaborations TEST BANK FOR Introduction to The Design and Analysis of Algorithms By Anany Levitin (Solution Manual)-Converted

This file 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 difficult 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 official 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 computing
√ n for any positive integer n. Besides assignment and comparison, your algorithm may only use the four basic arithmetical operations. 5. a. Find gcd(31415, 14142) by applying Euclid’s algorithm. b. Estimate how many times faster it will be to find gcd(31415, 14142) by Euclid’s algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to gcd(m, n). 6.
Prove the equality gcd(m, n) = gcd(n,mmod 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 first 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. a. What is the smallest number of divisions made by Euclid’s algorithm among all inputs 1 ≤ m, n ≤ 10? b. What is the largest number of divisions made by Euclid’s algorithm among all inputs 1 ≤ m, n ≤ 10? 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. 1 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 first 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 finding integer solutions to the Diophantine equation ax + by = c with any set of integer coefficients 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 first 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 opened; the third time through you close the door of locker #3 (opened from the first 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 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 find arguments supporting either view. There is a well established principle pertinent to the matter though: scientific facts or mathematical expressions of them are not patentable. (Why do you think it 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. 4. There is a quite straightforward algorithm for this problem based on the definition of
√ n. 5. a. Just follow Euclid’s algorithm as described in the text. b. Compare the number of divisions made by the two 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 = mmod 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 mn. 8. The answer to part (a) can be given immediately; the answer to part (b) can be given by checking the algorithm’s performance on all pairs 1m n ≤ 10. 9. a. Use the equality gcd(m, n) = gcd(m − n, n) for m ≥ n 0. b. The key is to figure out the total number of distinct integers 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 coefficients, 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