Solution Manual For Introduction To The Design And Analysis Of Algorithms, 3rd Edition

Preview (16 of 499 Pages)

100%

Purchase to unlock

Loading page image...

Thisfile contains the exercises, hints, and solutions for Chapter 1 of thebook ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, byA. Levitin.The problems that might be challenging for at least some studentsare marked byB;those that might be difficult for a majority of students aremarked byIExercises 1.11. Do some research on al-Khorezmi (also al-Khwarizmi), the man fromwhose name the word “algorithm” is derived.In particular, you shouldlearn what the origins of the words “algorithm” and “algebra” have incommon.2. Given that the official purpose of the U.S. patent system is the promo-tion of the “useful arts,” do you think algorithms are patentable in thiscountry?Should they be?3. a. Write down driving directions for going from your school to your homewith the precision required from an algorithm’s description.b. Write down a recipe for cooking your favorite dish with the precisionrequired by an algorithm.4. Design an algorithm for computingb√cfor any positive integer.Be-sides assignment and comparison, your algorithm may only use the fourbasic arithmetical operations.5. Design an algorithm tofind all the common elements in two sorted listsof numbers.For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, theoutput should be 2, 5, 5. What is the maximum number of comparisonsyour algorithm makes if the lengths of the two given lists areandrespectively?6. a. Findgcd(31415, 14142) by applying Euclid’s algorithm.b.Estimate how many times faster it will be tofindgcd(31415, 14142)by Euclid’s algorithm compared with the algorithm based on checkingconsecutive integers frommin{ }down togcd( )7.BProve the equalitygcd( )=gcd( mod)for every pair of positiveintegersand.8. What does Euclid’s algorithm do for a pair of integers in which thefirstis smaller than the second? What is the maximum number of times thiscan happen during the algorithm’s execution on such an input?9. a. What is the minimum number of divisions made by Euclid’s algorithmamong all inputs1≤ ≤10?1

Loading page image...

b. What is the maximum number of divisions made by Euclid’s algorithmamong all inputs1≤ ≤10?10. a. Euclid’s algorithm, as presented in Euclid’s treatise, uses subtractionsrather than integer divisions.Write pseudocode for this version of Euclid’salgorithm.b.IEuclid’s game(see [Bog]) starts with two unequal positive in-tegers on the board.Two players move in turn.On each move, a playerhas to write on the board a positive number equal to the difference of twonumbers already on the board; this number must be new, i.e., differentfrom all the numbers already on the board.The player who cannot moveloses the game.Should you choose to movefirst or second in this game?11. Theextended Euclid’s algorithmdetermines not only the greatestcommon divisorof two positive integersandbut also integers (notnecessarily positive)and, such that+=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 tofind integer solutions to the Diophantineequation+=with any set of integer coefficients,, and.12.BLocker doorsThere arelockers in a hallway, numbered sequentiallyfrom 1 to. Initially, all the locker doors are closed. You makepassesby the lockers, each time starting with locker #1.On theth pass,=12  , you toggle the door of everyth locker: if the door is closed, youopen it; if it is open, you close it. After the last pass, which locker doorsare open and which are closed? How many of them are open?2

Loading page image...

Hints to Exercises 1.11. It is probably faster to do this by searching the Web, but your libraryshould be able to help, too.2. One canfind arguments supporting either view.There is a well establishedprinciple pertinent to the matter, though: scientific facts or mathematicalexpressions 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 ratherthan a machine.Still, make sure that your descriptions do not containobvious ambiguities.Knuth provides an interesting comparison betweencooking recipes and algorithms [KnuI, p.6].4. There is a quite straightforward algorithm for this problem based on thedefinition ofb√c.5. Try to design an algorithm that always makes less thancomparisons.6. a. Just follow Euclid’s algorithm as described in the text.b. Compare the number of divisions made by the two algorithms.7. Prove that ifdivides bothand(i.e.,=and=for somepositive integersand), then it also divides bothand=modand vice versaUse the formula=+(0≤  )and the fact thatifdivides two integersandit also divides+and−(Why?)8. Perform one iteration of the algorithm for two arbitrarily chosen integers  9. 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 pairs1   ≤1010. a. Use the equalitygcd( ) = gcd(− )for≥ 0b. The key is tofigure out the total number of distinct integers that can bewritten on the board, starting with an initial pair where  ≥1You should exploit a connection of this question to the question of part(a).Considering small examples, especially those with= 1and= 2should help, too.11.Of course, for some coefficients, the equation will have no solutions.12. Tracing the algorithm by hand for, say,= 10and studying its outcomeshould help answering both questions.3

Loading page image...

Solutions to Exercises 1.11. Al-Khwarizmi (9th centuryC.E.) was a great Arabic scholar, most famousfor his algebra textbook.In fact, the word “algebra” is derived from theArabic title of this book while the word “algorithm” is derived from atranslation 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 legal state of affairsdistinguishes mathematical algorithms, which are not patentable, fromother algorithms, which may be patentable if implemented as computerprograms (e.g., [Cha00]).3. n/a4. A straightforward algorithm that does not rely on the availability of anapproximate value of√can check the squares of consecutive positiveintegers until thefirst square exceedingis encountered.The answer willbe the number’s immediate predecessor.Note: A much faster algorithmfor solving this problem can be obtained by using Newton’s method (seeSections 11.4 and 12.4).5. Initialize the list of common elements to empty. Starting with thefirst ele-ments of the lists given, repeat the following until one of the lists becomesempty.Compare the current elements of the two lists: if they are equal,add this element to the list of common elements and move to the nextelements of both lists (if any); otherwise, move to the element followingthe smaller of the two involved in the comparison.The maximum number of comparisons, which is made by this algorithmon some lists with no common elements such as thefirstpositive oddnumbers and thefirstpositive even numbers, is equal to+−16. a.gcd(3141514142) = gcd(141423131) = gcd(31311618) =gcd(16181513) = gcd(1513105) = gcd(1513105) = gcd(10543) =gcd(4319) = gcd(195) = gcd(54) = gcd(41) = gcd(10) = 1b. To answer the question, we need to compare the number of divisionsthe algorithms make on the input given. The number of divisions madeby Euclid’s algorithm is 11 (see part a).The number of divisions madeby the consecutive integer checking algorithm on each of its 14142 itera-tions is either 1 and 2; hence the total number of multiplications is be-tween 1·14142 and 2·14142.Therefore, Euclid’s algorithm will be between1·1414211≈1300and 2·1414211≈2600times faster.4

Loading page image...

7. Let usfirst prove that ifdivides two integersandit also dividesboth+and−.By definition of division, there exist integersandsuch that=and=Therefore±=±= (±)i.e.,divides both+and−Also note that ifdividesit also divides any integer multipleofIndeed, sincedivides =Hence=() = ()i.e.,dividesNow we can prove the assertion in question.For any pair of positiveintegersandifdivides bothand, it also divides bothand=mod=−Similarly, ifdivides bothand=mod=−it also divides both=+andThus, the two pairs( )and( )have the samefinite nonempty set of common divisors,including the largest element in the set, i.e.,gcd( ) = gcd( )8. For any input pair such that0≤  Euclid’s algorithm simplyswaps the numbers on thefirst iteration:gcd( ) = gcd( )becausemod=if  Such a swap can happen only once sincegcd( ) = gcd( mod)implies that thefirst number of the new pair()will be greater than its second number(mod)after every iterationof the algorithm.9. a. For any input pair≥≥1in whichis a multiple ofEuclid’salgorithm makes exactly one division; it is the smallest number possiblefor two positive numbers.b.The answer is 5 divisions, which is made by Euclid’s algorithm incomputinggcd(58)It is not too time consuming to get this answer byexamining the number of divisions made by the algorithm on all inputpairs1   ≤10Note:A pertinent general result (see [KnuII, p.360]) is that for anyinput pair where0≤  the number of divisions required byEuclid’s algorithm to computegcd( )is at mostblog(3−))cwhere= (1 +√5)2.5

Loading page image...

10. a. Here is a nonrecursive version:AlgorithmEuclid2( )//Computesgcd( )by Euclid’s algorithm based on subtractions//Input: Two nonnegative integersandnot both equal to 0//Output: The greatest common divisor ofandwhile6= 0doif  swap( )←−returnb. It is not too difficult to prove that the integers that can be written onthe board are the integers generated by the subtraction version of Euclid’salgorithm and only them.Although the order in which they appear onthe board may vary, their total number always stays the same: It is equaltogcd( )whereis the maximum of the initial numberswhichincludes two integers of the initial pair.Hence, the total number ofpossible moves isgcd( )−2Consequently, ifgcd( )is odd,one should choose to gofirst; if it is even, one should choose to go second.11. n/a12. Since all the doors are initially closed, a door will be open after the lastpass if and only if it is toggled an odd number of times.Door(1≤≤)is toggled on pass(1≤≤)if and only ifdividesHence, the totalnumber of times dooris toggled is equal to the number of its divisors.Note that ifdividesi.e.=thendividestoo.Hence all thedivisors ofcan be paired (e.g., for= 12such pairs are 1 and 12, 2and 6, 3 and 4) unlessis a perfect square (e.g., for= 164 does nothave another divisor to be matched with).This implies thathas anodd number of divisors if and only if it is a perfect square, i.e.,=2Hence doors that are in the positions that are perfect squares and onlysuch doors will be open after the last pass.The total number of suchpositions not exceedingis equal tob√c: these numbers are the squaresof the positive integers between 1 andb√cinclusively.6

Loading page image...

Exercises 1.21.Old World puzzleA peasantfinds himself on a riverbank with a wolf,a goat, and a head of cabbage.He needs to transport all three to theother side of the river in his boat. However, the boat has room for onlythe peasant himself and one other item (either the wolf, the goat, or thecabbage). In his absence, the wolf would eat the goat, and the goat wouldeat the cabbage.Solve this problem for the peasant or prove it has nosolution.(Note: The peasant is a vegetarian but does not like cabbageand hence can eat neither the goat nor the cabbage to help him solve theproblem. And it goes without saying that the wolf is a protected species.)2.New World puzzleThere are four people who want to cross a ricketybridge; they all begin on the same side. You have 17 minutes to get themall across to the other side. It is night, and they have oneflashlight. Amaximum of two people can cross the bridge at one time. Any party thatcrosses, either one or two people, must have theflashlight with them. Theflashlight must be walked back and forth; it cannot be thrown, for example.Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes,person 3 takes 5 minutes, and person 4 takes 10 minutes.A pair mustwalk together at the rate of the slower person’s pace. (Note: According toa rumor on the Internet, interviewers at a well-known software companylocated near Seattle have given this problem to interviewees.)3. Which of the following formulas can be considered an algorithm for com-puting the area of a triangle whose side lengths are given positive numbers,, and?a.=p(−)(−)(−)where= (++)2b.=12sinwhereis the angle between sidesandc.=12whereis the height to base4. Write pseudocode for an algorithm forfinding real roots of equation2++= 0for arbitrary real coefficients and(You may assume theavailability of the square root function())5. Describe the standard algorithm forfinding the binary representation ofa positive decimal integera. in English.b. in pseudocode.6. Describe the algorithm used by your favorite ATM machine in dispensingcash.(You may give your description in either English or pseudocode,whichever youfind more convenient.)7

Loading page image...

7. a. Can the problem of computing the numberbe solved exactly?b. How many instances does this problem have?c. Look up an algorithm for this problem on the Internet.8. Give an example of a problem other than computing the greatest commondivisor for which you know more than one algorithm.Which of them issimpler?Which is more efficient?9. Consider the following algorithm forfinding the distance between the twoclosest elements in an array of numbers.AlgorithmMinDistance([0−1])//Input: Array[0..−1]of numbers//Output: Minimum distance between two of its elements← ∞for←0to−1dofor←0to−1doif6=and|[]−[]| ←|[]−[]|returnMake as many improvements as you can in this algorithmic solution to theproblem.If you need to, you may change the algorithm altogether; if not,improve the implementation given.10. One of the most influential books on problem solving, titledHow To SolveIt[Pol57], was written by the Hungarian-American mathematician GeorgePólya (1887—1985).Pólya summarized his ideas in a four-point summary.Find this summary on the Internet or, better yet, in his book, and compareit with the plan outlined in Section 1.2.What do they have in common?How are they different?8

Loading page image...

Hints to Exercises 1.21. The peasant would have to make several trips across the river, startingwith the only one possible.2. Unlike the Old World puzzle of Problem 1, thefirst move solving thispuzzle is not obvious.3. The principal issue here is a possible ambiguity.4. Your algorithm should work correctly for all possible values of the coeffi-cients, including zeros.5. You almost certainly learned this algorithm in one of your introductoryprogramming courses.If this assumption is not true, you have a choicebetween designing such an algorithm on your own or looking it up.6. You may need to make afield trip to refresh your memory.7. Question (a) is difficult, though the answer to it–discovered in 1760sby the German mathematician Johann Lambert –is well-known.Bycomparison, question (b) is incomparably simpler.8. You probably know two or more different algorithms for sorting an arrayof numbers.9. You can: decrease the number of times the inner loop is executed, makethat loop run faster (at least for some inputs), or, more significantly, designa faster algorithm from scratch.10. n/a9

Loading page image...

Solutions to Exercises 1.21. LetP,w,g, andcstand for the peasant, wolf, goat, and cabbage head,respectively.The following is one of the two principal sequences thatsolve the problem:PwgcP gw cgPw cPwgcwP gcPw cgw cP gPwgcNote: This problem is revisited later in the book (see Section 6.6).2. Let 1, 2, 5, 10 be labels representing the men of the problem,representtheflashlight’s location, and the number in the parenthesis be the totalamount of time elapsed.The following sequence of moves solves theproblem:(0)1,2,5,101,2(2)5,102(3)1,5,102,5,10(13)15,10(15)1,21,2,5,10(17)3. a. The formula can be considered an algorithm if we assume that we knowhow to compute the square root of an arbitrary positive number.b.The difficulty here lies in computingsinSince the formula saysnothing about how it has to be computed, it should not be considered analgorithm.This is true even if we assume, as we did for the square rootfunction, that we know how to compute the sine of a given angle. (Thereare several algorithms for doing this but only approximately, of course.)The problem is that the formula says nothing about how to compute angleeither.c. The formula says nothing about how to compute.4.AlgorithmQuadratic(  )//The algorithmfinds real roots of equation2++= 0//Input: Real coefficients  //Output: The real roots of the equation or a message about their absenceif6= 0←∗−4∗∗if 0←2∗1←(−+())2←(−−())10

Loading page image...

return1 2else if= 0return−(2∗)else return ‘no real roots’else //= 0if6= 0return−else //== 0if= 0return‘all real numbers’else return‘no real roots’Note: See a more realistic algorithm for this problem in Section 11.4.5. a.Divide the given numberby 2:the remainder(0 or 1) will bethe next (from right to left) digit of the binary representation in question.Replaceby the quotient of the last division and repeat this operationuntilbecomes 0.b.AlgorithmBinary()//The algorithm implements the standard method forfinding//the binary expansion of a positive decimal integer//Input: A positive decimal integer//Output: The list−110of’s binary digits←0while6= 0←mod 2←b2c←+ 16. n/a7. a., as an irrational number, can be computed only approximately.b.It is natural to consider, as an instance of this problem, computing’s value with a given level of accuracy, say, withcorrect decimal digits.With this interpretation, the problem has infinitely many instances.8. n/a9. The following improved version considers the same pair of elements onlyonce and avoids recomputing the same expression in the innermost loop:AlgorithmMinDistance2([0−1])//Input: An array[0..−1] of numbers//Output: The minimum distancebetween two of its elements11

Loading page image...

← ∞for←0to−2dofor←+ 1to−1do←|[]−[]|if  ←returnA faster algorithm is based on the idea of presorting (see Section 6.1).10. Pólya’s general four-point approach is:1. Understand the problem2. Devise a plan3. Implement the plan4. Look back/check12

Loading page image...

Exercises 1.31. Consider the algorithm for the sorting problem that sorts an array bycounting, for each of its elements, the number of smaller elements andthen uses this information to put the element in its appropriate positionin the sorted array:AlgorithmComparisonCountingSort([0−1],[0−1])//Sorts an array by comparison counting//Input: Array[0−1]of orderable values//Output: Array[0−1]of’s elements sorted in nondecreasing orderfor←0to−1do[]←0for←0to−2dofor←+ 1to−1doif[] [][]←[] + 1else[]←[] + 1for←0to−1do[[]]←[]a. Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47.b. Is this algorithm stable?c. Is it in place?2. Name the algorithms for the searching problem that you already know.Give a good succinct description of each algorithm in English.(If youknow no such algorithms, use this opportunity to design one.)3. Design a simple algorithm for the string-matching problem.4.Königsberg bridgesThe Königsberg bridge puzzle is universally acceptedas the problem that gave birth to graph theory.It was solved by the greatSwiss-born mathematician Leonhard Euler (1707—1783).The problemasked whether one could, in a single stroll, cross all seven bridges of thecity of Königsberg exactly once and return to a starting point.Followingis a sketch of the river with its two islands and seven bridges:13

Loading page image...

a. State the problem as a graph problem.b. Does this problem have a solution?If you believe it does, draw sucha stroll; if you believe it does not, explain why and indicate the small-est number of new bridges that would be required to make such a strollpossible.5.Icosian GameA century after Euler’s discovery (see Problem 4), an-other famous puzzle–this one invented by the renown Irish mathemati-cian Sir William Hamilton (1805-1865)–was presented to the world underthe name of the Icosian Game.The game was played on a circular woodenboard on which the following graph was carved:Find aHamiltonian circuit–a path that visits all the graph’s verticesexactly once before returning to the starting vertex–for this graph.6. Consider the following problem:Design an algorithm to determine thebest route for a subway passenger to take from one designated station toanother in a well-developed subway system similar to those in such citiesas Washington, D.C., and London, UK.a. The problem’s statement is somewhat vague, which is typical of real-life problems.In particular, what reasonable criterion can be used fordefining the “best” route?b. How would you model this problem by a graph?7. a. Rephrase the traveling salesman problem in combinatorial object terms.b. Rephrase the graph-coloring problem in combinatorial object terms.14

Loading page image...

8. Consider the following map:abcdefa. Explain how we can use the graph-coloring problem to color the mapso that no two neighboring regions are colored the same.b. Use your answer to part (a) to color the map with the smallest numberof colors.9. Design an algorithm for the following problem: Given a set ofpointsin the Cartesian plane, determine whether all of them lie on the samecircumference.10. Write a program that reads as its inputs the( )coordinates of theendpoints of two line segments11and22and determines whetherthe segments have a common point.15

Preview Mode

This document has 499 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools