1、This le contains the exercises, hints, and solutions for Chapter 3 of the book ”Introduction to the Design and Analysis of Algorithms,” 2nd edition, byA. Levitin. The problems that might be challenging for at least some students are marked by ; those that might be dicult for a majority of students a
2、re marked by .Exercises 3.11. a. Give an example of an algorithm that should not be considered an application of the brute-force approach.b. Give an example of a problem that cannot be solved by a brute-force algorithm.2. a. What is the eciency of the brute-force algorithm for computing an as a func
3、tion of n? As a function of the number of bits in the binary representation of n?b. If you are to compute an mod m where a 1 and n is a large positive integer, how would you circumvent the problem of a very large magnitude of an?3. For each of the algorithms in Problems 4, 5, and 6 of Exercises 2.3,
4、 tell whether or not the algorithm is based on the brute-force approach.4. a. Design a brute-force algorithm for computing the value of a polynomialp(x)= anxn + an1xn1 + . + a1x + a0at a given point x0 and determine its worst-case eciency class.b. If the algorithm you designed is in (n2), design a l
5、inear algorithm for this problem.c. Is it possible to design an algorithm with a better than linear eciency for this problem?5. Sort the list E, X, A, M, P, L, E in alphabetical order by selection sort.6. Is selection sort stable? (The denition of a stable sorting algorithm was given in Section 1.3.
6、)7. Is it possible to implement selection sort for linked lists with the same(n2) eciency as the array version?8. Sort the list E, X, A, M, P, L, E in alphabetical order by bubble sort.9. a. Prove that if bubble sort makes no exchanges on its pass through a list, the list is sorted and the algorithm
7、 can be stopped.28b. Write a pseudocode of the method that incorporates this improve- ment.c. Prove that the worst-case eciency of the improved version is quadratic.10. Is bubble sort stable?11. Alternating disks You have a row of 2n disks of two colors, n dark and n light. They alternate: dark, lig
8、ht, dark, light, and so on. You want to get all the dark disks to the right-hand end, and all the light disks to the left-hand end. The only moves you are allowed to make are those which interchange the positions of two neighboring disks.Design an algorithm for solving this puzzle and determine the
9、number of moves it makes. Gar99, p.75Hints to Exercises 3.11. a. Think of algorithms that have impressed you with their eciency and/or sophistication. Neither characteristic is indicative of a brute- force algorithm.b. Surprisingly, it is not a very easy question to answer. Mathemati- cal problems (
10、including those you have studied in your secondary school and college courses) are a good source of such examples.2. a. The rst question was all but answered in the section. Expressing the answer as a function of the number of bits can be done by using the formula relating the two metrics.b. How can
11、 we compute (ab) mod m?3. It helps to have done the exercises in question.4. a. The most straightforward algorithm, which is based on substituting x0into the formula, is quadratic.b. Analyzing what unnecessary computations the quadratic algorithm does should lead you to a better (linear) algorithm.c
12、. How many coecients does a polynomial of degree n have? Can one compute its value at an arbitrary point without processing all of them?5. Just trace the algorithm on the input given. (It was done for another input in the section.)6. Although the majority of elementary sorting algorithms are stable,
13、 do not rush with your answer. A general remark about stability made in Section 1.3, where the notion of stability is introduced, could be helpful, too.7. Generally speaking, implementing an algorithm for a linked list poses prob- lems if the algorithm requires accessing the lists elements not in a
14、sequen- tial order.8. Just trace the algorithm on the input given. (See an example in the section.)9. a. A list is sorted if and only if all its adjacent elements are in a correct order. Why?b. Add a boolean ag to register the presence or absence of switches.c. Identify worst-case inputs rst.10. Can
15、 bubble sort change the order of two equal elements in its input?11. Thinking about the puzzle as a sorting-like problem may and may not lead you to the most simple and ecient solution.Solutions to Exercises 3.11. a. Euclids algorithm and the standard algorithm for nding the binary representation of
16、 an integer are examples from the algorithms previously mentioned in this book. There are, of course, many more examples in its other chapters.b. Solving nonlinear equations or computing denite integrals are ex- amples of problems that cannot be solved exactly (except for special in- stances) by any
17、 algorithm.2. a. M (n)= n 2b where M (n) is the number of multiplications made by the brute-force algorithm in computing an and b is the number of bits inthe ns binary representation. Hence, the eciency is linear as a function of n and exponential as a function of b.b. Perform all the multiplication
18、s modulo m, i.e.,ai mod m = (ai1 mod m a mod m) mod m for i = 1, ., n.13. Problem 4 (computes 艺 n i2): yesProblem 5 (computes the range of an arrays values): yes Problem 6 (checks whether a matrix is symmetric): yes4. a. Here is a pseudocode of the most straightforward version:Algorithm BruteForcePo
19、lynomialEvaluation(P 0.n, x)/The algorithm computes the value of polynomial P at a given point x/by the “highest-to-lowest term” brute-force algorithm/Input: Array P 0.n of the coecients of a polynomial of degree n,/stored from the lowest to the highest and a number x/Output: The value of the polyno
20、mial at the point x p 0.0for i n downto 0 dopower 1for j 1 to i dopower power x p p + P i powerreturn pWe will measure the inputs size by the polynomials degree n. The ba- sic operation of this algorithm is a multiplication of two numbers; the number of multiplications M (n) depends on the polynomia
21、ls degree only.Although it is not dicult to nd the total number of multiplications in this algorithm, we can count just the number of multiplications in the algorithms inner-most loop to nd the algorithms eciency class:2ninM (n)= 区区1= 区i = n(n + 1) (n2).i=0 j=1i=0b. The above algorithm is very ineci
22、ent: we recompute powers of x again and again as if there were no relationship among them. Thus, the obvious improvement is based on computing consecutive powers more eciently. If we proceed from the highest term to the lowest, we could computexi1 by using xi but this would require a division and he
23、nce a special treatment for x = 0. Alternatively, we can move from the lowest term to the highest and compute xi by using xi1. Since the second alternative uses multiplications instead of divisions and does not require any specialtreatment for x = 0, it is both more ecient and cleaner. It leads to t
24、he following algorithm:Algorithm BetterBruteForcePolynomialEvaluation(P 0.n, x)/The algorithm computes the value of polynomial P at a given point x/by the “lowest-to-highest term” algorithm/Input: Array P 0.n of the coecients of a polynomial of degree n,/from the lowest to the highest, and a number
25、x/Output: The value of the polynomial at the point x p P 0; power 1for i 1 to n dopower power x p p + P i powerreturn pThe number of multiplications here isnM (n)= 区2= 2ni=1(while the number of additions is n), i.e., we have a linear algorithm.Note: Horners Rule discussed in Section 6.5 needs only n
26、 multiplications (and n additions) to solve this problem.c. No, because any algorithm for evaluating an arbitrary polynomial of degree n at an arbitrary point x must process all its n +1 coecients. (Note that even when x = 1, p(x)= an + an1 + . + a1 + a0, which needsat least n additions to be comput
27、ed correctly for arbitrary an, an1, ., a0.)EXAMPLEAXEMPLEAEXMPLEAEEMPLXAEELPMXAEELMPXAEELMPX5.6. Selection sort is not stable: In the process of exchanging elements that are not adjacent to each other, the algorithm can reverse an ordering of equal elements. The list 21, 211, 1 is such an example.7.
28、 Yes. Both operationsnding the smallest element and swapping itcan be done as eciently with a linked list as with an array.8. E, X, A, M, P , L, E?E X AMPLEEAX?MPLEEAMX?PLEEAMPX?LEEAMPLX?EEAMPLE|X?E AMPLE?AE M P LE?AEMLP EAEMLE|PA?E?M?LAELMAELEA?E?L?EAEE|LA?E?E?LE?E|MThe algorithm can be stopped her
29、e (see the next question).9. a. Pass i (0 i n2) of bubble sort can be represented by the following diagram:?A0, ., Aj Aj+1, ., Ani1 | Ani . An1in their final positionsIf there are no swaps during this pass, thenA0 A1 . Aj Aj+1 . Ani1,with the larger (more accurately, not smaller) elements in positio
30、ns n ithrough n 1 being sorted during the previous iterations.b. Here is a pseudocode for the improved version of bubble sort:Algorithm BetterBubbleSort (A0.n 1)/The algorithm sorts array A0.n 1 by improved bubble sort/Input: An array A0.n 1 of orderable elements/Output: Array A0.n 1 sorted in ascen
31、ding order count n 1 /number of adjacent pairs to be compared sag true /swap agwhile sag dosag falsefor j 0 to count 1 do if Aj + 1 Ajswap Aj and Aj + 1sag truecount count 1c. The worst-case inputs will be strictly decreasing arrays. For them, the improved version will make the same comparisons as t
32、he original version, which was shown in the text to be quadratic.10. Bubble sort is stable.It follows from the fact that it swaps adjacent elements only, provided Aj + 1 Aj.5. Here is a simple and ecient (in fact, optimal) algorithm for this problem: Starting with the rst and ending with the last li
33、ght disk, swap it witheach of the i (1 i n) dark disks to the left of it. The ith iteration of the algorithm can be illustrated by the following diagram, in which 1sand 0s correspond to the dark and light disks, respectively.00.011.11010.1000.0011.1110.10 、i、,1 、i、,1、 、 i, 、 、 i, i=1The total number
34、 of swaps made is equal to 艺ni = n(n + 1)/2.Exercises 3.21. Find the number of comparisons made by the sentinel version of sequential searcha. in the worst case.b. in the average case if the probability of a successful search is p (0 p 1).2. As shown in Section 2.1, the average number of key compari
35、sons made by sequential search (without a sentinel, under standard assumptions about its inputs) is given by the formulaCavg(n)= p(n + 1)2+ n(1 p),where p is the probability of a successful search. Determine, for a xed n, the values of p (0 p 1) for which this formula yields the largest value of Cav
36、g(n) and the smallest value of Cavg(n).3. Gadgets testing A rm wants to determine the highest oor of its n- story headquarters from which a gadget can fall with no impact on the gadgets functionality. The rm has two identical gadgets to experiment with. Design an algorithm in the best eciency class
37、you can to solve this problem.4. Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the textTHERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED(Assume that the length of the textit is 47 characters longis known before the search starts.
38、)5. How many comparisons (both successful and unsuccessful) are made by the brute-force string-matching algorithm in searching for each of the following patterns in the binary text of 1000 zeros?a. 00001 b. 10000 c. 010106. Give an example of a text of length n and a pattern of length m that constit
39、utes the worst-case input for the brute-force string-matching al- gorithm. Exactly how many character comparisons are made for such input?7. Write a visualization program for the brute-force string-matching algo- rithm.8. In solving the string-matching problem, would there be any advantage in compar
40、ing pattern and text characters right-to-left instead of left-to-right?9. Consider the problem of counting, in a given text, the number of substrings that start with an A and end with a B. (For example, there are four such substrings in CABAAXBYA.)(a) Design a brute-force algorithm for this problem
41、and determine its eciency class.(b) Design a more ecient algorithm for this problem Gin04.10. Word Find A popular diversion in the United States, Word Find, asks the player to nd each of a given set of words in a square table lled with single letters. A word can read horizontally (left or right), ve
42、rtically (up or down), or along a 45 degree diagonal (in any of the four directions), formed by consecutively adjacent cells of the table; it may wrap around the tables boundaries but it must read in the same direction with no zigzagging. The same cell of the table may be used in dierent words, but,
43、 in a given word, the same cell may be used no more than once. Write a computer program for solving this puzzle.11. Battleship game Write a program for playing Battleship (a classic strat- egy game) on the computer which is based on a version of brute-force pattern matching. The rules of the game ar
44、e as follows. There are two opponents in the game (in this case, a human player and the computer). The game is played on two identical boards (10-by-10 tables of squares) on which each opponent places his or her ships, not seen by the opponent. Each player has ve ships, each of which occupies a cert
45、ain number of squares on the board: a destroyer (2 squares), a submarine (3 squares), a cruiser (3 squares), a battleship (4 squares), and an aircraft carrier (5 squares). Each ship is placed either horizontally or vertically, with no two ships touching each other. The game is played by the opponents taking turns “shooting” at each others ships. A result of every shot is displayed as either a hit or a miss. In case of a hit, the player gets to go again and keeps playing until this player misses. The goal is to sink all the o
