Real World Algorithms: A Beginners Guide Errata To The .

10m ago
30 Views
1 Downloads
499.70 KB
16 Pages
Last View : 1d ago
Last Download : 6m ago
Upload by : Elisha Lemon
Transcription

1Real World Algorithms: A Beginners GuideErrata to the First PrintingLast updated 8 February 2018This document lists the changes that should be made to Real World Algorithmsto correct mistakes that made their way to printing, to improve infelicities thatthe author spotted too late, or update the material with something that theauthor did not know at the time of writing the book.There are three different kinds of changes noted here. In all of them the datethat they became known to the author is given at the first line of each item.The name of the person who suggested the change is also given at the end ofeach change.I Page 1, line 11 Jan 1These are technical or typographical errors.Page 1, line 11 Jan 1These as changes that improve the book, even if they do not correct an error.They include small rewordings, or material that became known to the authorafter the book was published.1 Jan 1These are minor fixes that although they do not make a big difference they do hurt the author.Some of them might strain the reader’s eye to see where the improvement is exactly.Page 1, line 1

2I Page xii, line 224 Apr 2017they can proved y they can be proved(S. Subramanya)08 Feb 2018Page 5, line 17and its last element is the (n 1)th y and so its last element is the (n 1)th08 Feb 2018Page 5, line 10Move “y;” to previous line.Page 8, line 8 and 212 Aug 2017big-Oh y big O12 Aug 2017Page 9, line 4big-Ohs y big Os12 Aug 2017Page 9, line 11In terms of big-Oh notation, we have by definition that y In terms of big O notation, we have,by definition, that08 Feb 2018Page 10, line 15Move “of” to the next line.I Page 11, line 2f (n) exy f (n)01 Apr 2017 enPage 13, line 11(P. Tsanakas)12 Aug 2017big-Oh y big OI Page 13, line 812 Aug 2017This is called “big-Omega,” or Ω(n), and the precise definition y This iscalled “big Omega,” Ω(f (n)); the precise definitionPage 13, line 612 Aug 2017Having defined big-Oh and big-Omega y Having defined big O and big OmegaPage 13, line 512 Aug 2017big-Theta y big ThetaI Page 20, line 430 Mar 2017line 3 y line 4I Page 20, line 330 Mar 2017line 11 y line 12I Page 20, line 130 Mar 2017line 6 y line 7Page 40, line 17Using big-Oh notation y Using the big O notation12 Aug 2017

3I Page 41, lines 4 to 330 Jan 2018Room 6 still has one unvisited room y Room 5 still has one unvisited room(Yi-Ming Lai)I Page 57, line 424 Apr 2017When you insert an item in the queue, you increase the index of the head;similarly, when you remove an item from the queue, you increase the indexof the tail. y When you insert an item in the queue, you increase the indexof the tail; similarly, when you remove an item from the queue, you increasethe index of the head.(S. Subramanya)I Page 65, line 206 Mar 2017011110 y 011011I Page 71, algorithm 3.1, line 126 Mar 2017Size y SizePQI Page 73, line 11root of the three y root of the treeI Page 80, line 624 Apr 2017(S. Subramanya)25 May 2017Joyces’s y Joyce’sI Page 80, line 529 Jun 201741% y 53%I Page 84, line 630 Jan 2018by assigning it to wc in line 13 y by assigning to it wc in line 13 (Yi-Ming Lai)Page 91, line 1714 Dec 2017"1110" y “1110”I Page 95, figure 4.1, caption21 Apr 2017An encryption y A decryptionI Page 140, lines 2 to 117 Jul 2017SHA-2 (Secure Hash Standard-2) y SHA-2 (Secure Hash Algorithm 2)Page 144, line 221 Apr 2017command packet y command packetI Page 145, line 14OR 3 y OR 201 Jun 2017

4I Page 145, line 1201 Jun 2017Alice y OR 1I Page 147, line 1317 Jul 2017SHA-224. y SHA-224,I Page 157, figure 6.6, caption21 Mar 2017weigthed y weightedI Page 162, line 130 Jan 2018prev, that is, prev[i] y pred, that is, pred[i](Yi-Ming Lai)01 Feb 2018Page 165, lines 2 to 1move line break before “then”I Page 166, figure 6.13, second panel, label under t21 Apr 201713 y 13/ I Page 166, figure 6.13, fourth panel, label under t21 Apr 201713 y 13/ I Page 166, figure 6.13, fifth panel, label under t21 Apr 2017 in f ty y I Page 170, figure 7.1, caption30 Jan 2018Breaking lines into paragraphs y Breaking paragraphs into lines(Yi-MingLai)23 Apr 2017Page 178, algorithm 7.1, line 12ExtractMinFromPQ(pq) y ExtractMinFromPQ(pq)I Page 179, line 1024 Apr 2017line 11 y line 14(S. Subramanya)I Page 179, line 1224 Jul 2017line 11 y line 14I Page 180, line 1326 Mar 2017lines 1–7 y lines 1–1023 Jul 2017Page 181, line 4re-weighting y reweightingI Page 182, figure 7.110822 Jul 201787link 0 2 y 0 2 and link 0 3 y 0 3

5Page 182, figure 7.11, caption23 Jul 2017re-weighted y reweightedI Page 184, line 12, exercise 119 Dec 2017a better path goes through u, we can check whether u y a better path goesthrough v, we can check whether vI Page 196, line 1030 Jan 2018We underline edges y We underline nodes(Yi-Ming Lai)Page 206, line 123 Apr 2017Euros y eurosI Page 214, line 804 Apr 2017PBj y BPjI Page 217, line 304 Apr 2017page 3 y page 6I Page 217, line 204 Apr 2017page 4 y page 5I Page 219, line 1030 Jan 2018from node 4 to nodes 3 and 2 y from node 4 to nodes 2 and 1(Yi-Ming Lai)Page 222, figure 9.628 Apr 2017arrow tipsyI Page 229, line 1604 May 2017support y supportedI Page 230, line 323 Apr 2017If there are n voters, then candidate A gets (60 2)n 120n points y If thereare 100m voters, candidate A gets (60 2)m 120m pointsI Page 230, line 223 Apr 2017(60 2 40)n 140n y (60 2 40)m 140mI Page 230, line 223 Apr 201740n y 40mI Page 231, heading 10.2Shulze y Schulze23 Apr 2017

6I Page 233, algorithm 10.1, line 423 Apr 2017P[i][j] y P[i, j]I Page 234, line 804 May 2017P[i, j] y P[c i , c j ]I Page 234, line 704 May 2017P[j, i] y P[c j , c i ]I Page 234, line 604 May 2017P[i, j] P[j, i] y P[c i , c j ] P[c j , c i ]28 Apr 2017Page 236, line 4(k 1) y k 1I Page 238, algorithm 10.2, line 623 Apr 2017S[i][j] y S[i, j]I Page 238, algorithm 10.2, line 923 Apr 2017S[i][j] y S[i, j]I Page 241, algorithm 10.3, second line of output23 Apr 2017s[i, jk ] s[jk , i] y S[i, jk ] S[jk , i]I Page 242, line 630 Jan 2018D would beat B, C, and D, while A would beat C, B would beat D y D wouldbeat both B and C, while A would beat C, B would beat C(Yi-Ming Lai)23 Apr 2017Page 244, algorithm 10.4all pr ed and dist y pred and distI Page 249, algorithm 11.124 Apr 2017a array of items y an array of items(S. Subramanya)I Page 249, algorithm 11.124 Apr 2017a element we are searching for y an element we are searching for (S. Subramanya)Page 249, figure 11.128 Apr 2017Change the array to:114480149903777656804374181613551We need not use sequential search in a sorted array.1031782507

7I Page 250, line 3real and complex parts y real and imaginary partsI Page 254, line 530 Jan 2018(Yi-Ming Lai)24 Apr 2017figure 11.3 y figure 11.6I Page 259, line 830 Jan 2018whether the match is in the head of the list y whether the match is not inthe head of the list(Yi-Ming Lai)I Page 260, algorithm 11.224 Apr 2017a element we are searching for y an element we are searching for (S. Subramanya)I Page 260, algorithm 11.2, line 1024 Apr 2017null; y nullI Page 261, algorithm 11.328 Jul 2017TranspositionSearch(A, s ) y TranspositionSearch(L, s )Page 261, algorithm 11.324 Apr 2017a list of items, y a list of itemsI Page 261, algorithm 11.324 Apr 2017a element we are searching for y an element we are searching for (S. Subramanya)I Page 261, algorithm 11.3, line 1225 Apr 2017null; y nullI Page 262, algorithm 11.4a array of items y an array of itemsI Page 262, algorithm 11.424 Apr 2017(S. Subramanya)24 Apr 2017a element we are searching for y an element we are searching for (S. Subramanya)I Page 262, line 130 Jan 2018the same search as in figure 11.11 y the same search as in figure 11.10 (YiMing Lai)I Page 264, algorirthm 11.5SecretarySearch(A, s ) y SecretarySearch(A)25 Apr 2017

8I Page 264, algorithm 11.5a array of items y an array of itemsI Page 264, algorirthm 11.5, line 4Compare(A[i], A[b]) y Compare(A[i], A[c])I Page 264, algorirthm 11.5, line 624 Apr 2017(S. Subramanya)24 Apr 2017(S. Subramanya)25 Apr 2017i m 1 yi mI Page 267, line 186 May 2017Unless you are not psychic y Unless you are psychicI Page 268, algorithm 11.624 Apr 2017a element we are searching for y an element we are searching for (S. Subramanya)I Page 270, figure 11.14b, last rowl 7m 7yl 8m 8I Page 275, line 231 May 2017(I. Kafetzaki)02 May 2017one’s complement y ones’ complementI Page 278, algorithm 11.724 Apr 2017a element we are searching for y an element we are searching for (S. Subramanya)I Page 287, algorithm 12.1a array of items y an array of itemsI Page 289, algorithm 12.2a array of items y an array of itemsI Page 291, algorithm 12.3a array of items y an array of itemsI Page 297, line 5we want to have A[i] A[i] y we want to have A[0] A[i]I Page 298, figure 12.6b, caption1 y one24 Apr 2017(S. Subramanya)24 Apr 2017(S. Subramanya)24 Apr 2017(S. Subramanya)30 Jan 2018(Yi-Ming Lai)28 Apr 2017

9I Page 299, algorithm 12.4a array of items y an array of itemsI Page 310, figure 12.12, third panel24 Apr 2017(S. Subramanya)08 May 2017i 5 y i 37Page 327, line 16, exercise 220 Dec 2017characters like “ ”, “ ”, and “ ” y characters like “ ”, “-”, and “ ”I Page 327, line 15, exercise 320 Dec 2017The in-place array merge, algorithm 12.7 y The in-place array merge, algorithm 12.7,Page 333, line 1109 May 2017minimal perfect mapping y minimal perfect mappingPage 340, line 309 May 2017456, 976 y 456,976Page 343, figure 13.509 May 20174, 847 y 4,847Page 343, figure 13.509 May 2017126, 033 y 126,033Page 343, figure 13.509 May 20173, 276, 872 y 3,276,872I Page 343, line 830 Jan 2018in line 4 y in line 3(Yi-Ming Lai)Page 346, line 309 May 2017binary fractional number y binary fractional numberI Page 353, line 1223 Jul 2017An successful search cannot take longer than a successful one y A successful search cannot take longer than an unsuccessful onePage 359, line 913 May 2017z-values y z-valuesPage 359, line 913 May 2017z-axis y z-axisPage 361, line 731 May 2017the number of frequency peaks in the song, and there is even a notation for it: y being thenumber of frequency peaks in the song, and there is even a notation for it:Page 361, line 16move “of” to the next line31 May 2017

10I Page 362, line 131 May 2017the data are not the y the data are not in the13 May 2017Page 367, line 7k(1 1/m)m( m ) km my (1 1/m)I Page 370, figure 13.20, third panel13 May 2017The solid arrows should emanate from “this”.I Page 371, line 230 Jan 2018Our hash algorithms take a specific and produce a specific output. y Ourhash algorithms take a specific input and produce a specific output. (Yi-MingLai)Page 383, table 14.1, caption14 May 2017letter y lettersPage 385, line 314 May 2017Move “J.” to the next line.I Page 386, line 9, 12, 1925 May 2017Gibb’s y Gibbs’sPage 387, line 1416 May 2017“ineligible” y “ineligible.”I Page 390, line 316 May 2017six y fiveI Page 395, line 1530 Jan 2018we get the values shown in figure 14.7 y we get the values shown in figure 14.8(Yi-MingLai)I Page 396, figure 14.8, fourth panel17 May 2017H 0.40 y H 0.940I Page 397, line 916 May 2017tox y toI Page 400, figure 14.10{1, 2, . . . , 14 }: outlook y {1, 2, . . . , 15}: outlookI Page 400, line 5happens in the normal branch y happens in the high branch08 Jun 2017(V. Malandrakis)30 Jan 2018(Yi-Ming Lai)

11I Page 402, algorithm 15.2, line 130 Jan 2018r CreateMap() y dt CreateMap()(Yi-Ming Lai)Page 413, figure 14.1222 Dec 2017add label “high” on the first, left, edge emanating from the root nodePage 414, line 312 Aug 2017because in terms of the big-Oh notation it is y because in terms of the big O notation they arePage 417, line 326 Feb 2017Witten, Frank, and Hall y Witten, Frank, Hall, and PalPage 426, figure 15.103 Feb 2018Change the gray letters from 40% gray to gray.Page 427, graphics03 Feb 2018Change the gray letters from 40% gray to gray.Page 428, second and fourth graphics03 Feb 2018Change the gray letters from 40% gray to gray.Page 430, line 1723 May 2017at the start of a string y at the start of the stringPage 430, line 1623 May 2017at the end of a string is its suffix y at the end of the string is a suffixI Page 430, line 4all A, AB, and ABA are y substrings A and ABA areI Page 431, fourth graphic14 Sep 2017(P. Mpellos)23 May 2017yI Page 431, line 1023 May 2017of the pattern y of the matched patternI Page 431, fifth graphicy23 May 2017

12I Page 431, line 924 May 2017So we get: y So we get, indicating the mismatched character:24 May 2017Page 431, line 1longer shifts y longer shiftsI Page 432, second graphic23 May 2017yI Page 432, line 724 May 2017AABAABAA y AABAABAAAAI Page 432, third graphic24 May 2017A A B A A B A AA A B A A B A A A AA A B A A AA A B A A AyPage 432, fifth graphic03 Feb 2018Change the gray letters from 40% gray to gray.I Page 432, line 424 May 2017define its length to be zero y define its border length as zeroI Page 433, line 1325 May 2017borders array y border arrayI Page 434, algorithm 15.2, line 9p[i] y p[j]Page 434, line 402 Jun 2017(A. Tsalapatis)22 Dec 2017to a queue q y to the queue qI Page 435, figure 15.5 caption24 May 2017Another trace the Knuth-Morris-Pratt algorithm; the borders array is at thebottom. y Another trace of the Knuth-Morris-Pratt algorithm; the borderarray is at the bottom.I Page 437, line 325 May 2017borders array y border arrayPage 439, figure 15.8Change the gray letters from 40% gray to gray.03 Feb 2018

13I Page 440, line 1230 May 2017mattern y pattern02 Feb 2018Page 441, figure 15.9b S E P T E M B E R E M B E Rr 1y S E P T E M B E RE M B E Rr 1I Page 443, algorithm 15.423 Dec 2017CreateRtOccurrencesTable(p, t, s ) y CreateRtOccurrencesTable(p, s )I Page 448, line 723 Dec 2017Try using a different data structure, like a hash table or a set, instead. y Trythen using a different data structure, like a hash table, instead.Page 449, line 1623 May 201750-50 y 50–50I Page 462, line 1020 May 2017line 6 y line 7I Page 463, line 420 May 2017change y maybe fixI Page 466, lines 18, 21, 2320 May 2017ECC y EECI Page 466, line 17Counting of Ministers y Council of MinistersI Page 467, lines 12, 19, 2330 Jan 2018(Yi-Ming Lai)20 May 2017ECC y EECI Page 467, paragraph 222 May 2017Rewrite the paragraph as follows:To tackle this kind of question, we must adopt a systematic approach.We have a set of voters, V {v 1,v 2, . . . ,vn }, and a set of weights, W {w 1, w 2, . . . , wm }. A voter vi has a weight w j given by a mapping f : V W .For a decision to be taken, it needs to meet a quota Q. In the example of theEEC, we have Q 12. The setup of V , W , f , and Q is called a voting game.

14I Page 468, line 321 May 2017such as y such thatI Page 468, line 421 May 2017in obtaining losing coalition y in obtaining a losing coalitionI Page 468, line 1421 May 2017ECC y EECI Page 468, line 721 May 2017then then y then theI Page 468, lines 3 to 130 May 2017As an example, take four voters V {A, B, C, D} with corresponding weightsW {4, 2, 1, 3} and quota Q 6. The critical coalitions are (we underline thecritical voters) {A, B}, {A, D}, {A, B,C}, {A, B, D}, {A,C, D}, {B,C, D}.yAs an example, let us take four voters A, B, C, D with corresponding weightsequal to 4, 2, 1, 3, and quota Q 6. The critical coalitions then are, underliningthe critical voters: {A, B}, {A, D}, {A, B,C}, {A, B, D}, {A,C, D}, and {B,C, D}.I Page 469, lines 6–730 Jan 2018Voter D has a greater voting weight than voter D y Voter D has a greatervoting weight than voter B(Yi-Ming Lai)I Page 472, line 1zero y oneI Page 473, line 1one y zero05 Sep 2017(N. Batsal)05 Sep 2017(N. Batsal)

1505 Feb 2017Table 16.3 was built with data from 2008. To update it for 2016, it should be as follows:Page 476, table 16.3Table 16.32016 U.S. electoral college number of electors and Banzhaf 30.0230.0230.0230.0230.0230.02305 Feb 2017Page 476, lines 6 to 5In 2015 y In 201605 Feb 2017Page 476, lines 3 to 2California’s Banzhaf measure is about 20.65 times that of Vermont. y California’s Banzhafmeasure is about 20.48 times that of Vermont.I Page 479, line 421 May 2017primes y compositesI Page 479, lines 4 to 321 May 2017n(1/2 1/3 1/5 · · · 1/k) y n(1/2 1/3 1/5 · · · 1/k)I Page 479, line 321 May 2017(1/2 1/3 1/5 · · · 1/k) y (1/2 1/3 1/5 · · · 1/k)Page 485, algorithm 16.11Output: (r, q), such that n odd23 May 20172r qy Output: (r, q), such that n 2r q with q

16Page 498, reference 21926 Mar 2017Ian H. Witten, Eibe Frank, and Mark A. Hall. Data Mining: Practical MachineLearning Tools and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, 3rd edition, 2011.yIan H. Witten, Eibe Frank, Mark A. Hall, and Christopher J. Pal. Data Mining:Practical Machine Learning Tools and Techniques. Elsevier, Cambridge, MA,4th edition, 2016.I Page 502, first column12 2017big-Oh (O(f (n)) y big O (O(f (n)))big-Omega (Ω(f (n))) y big Omega (Ω(f (n)))add big Theta (Θ(f (n))), 13Page 502, first column09 May 2017added binary fractional numberI Page 503, second column20 May 2017European Economic Community (ECC) y European Economic Community(EEC)Page 504, first column23 Jul 2017graph re-weighting y graph reweightingPage 504, first column03 Feb 2018remove length (move to path, length)I Page 505, first column30 Jan 2018Lember-Ziv-Welch y Lempel-Ziv-Welch(Yi-Ming Lai)Page 505, second column09 May 2017added mapping, minimal perfectPage 506, first columnadd path, length03 Feb 2018

Having de ned big-Oh and big-Omega y Having de ned big O and big Omega Page 13, line 12 Aug 20175 big-Theta y big Theta I Page 20, line 4 30 Mar 2017 line 3 y line 4 I Page 20, line 3 30 Mar 2017 line 11 y line 12 I Page 20, line 1 30 Mar 2017 line 6 y line 7 Page 40, line 17 12 Aug 2017 Using big

Related Documents:

Feb 20, 2010 · Static IP Firewall SAN Monitoring . EC2 Beginners Workshop 4 Public EC2 Images Fedora Red Hat CentOS Ubuntu Debian OpenSuse Gentoo (OpenSolaris) (Windows 2003) (Windows 2008) Eric Hammond Alestic.com. EC2 Beginners Workshop 5 Sign Up for AWS Account (already done) Eric Hammond Alestic.com. EC2 Beginners Workshop 6 Sign In to AWS Console

THIRD EDITION Naveed A. Sherwani Intel Corporation. KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW. eBook ISBN: 0-306-47509-X . Graph Search Algorithms Spanning Tree Algorithms Shortest Path Algorithms Matching Algorithms Min-Cut and Max-Cut Algorithms

Collectively make tawbah to Allāh S so that you may acquire falāḥ [of this world and the Hereafter]. (24:31) The one who repents also becomes the beloved of Allāh S, Âَْ Èِﺑاﻮَّﺘﻟاَّﺐُّ ßُِ çﻪَّٰﻠﻟانَّاِ Verily, Allāh S loves those who are most repenting. (2:22

Graph algorithms Geometric algorithms . Textbook Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, McGraw-Hill, 2009. 4 Suggested Reading Polya, How to Solve it, Princeton University Press, 1957. Preparata and Shamos, Computational Geometry, an . limitations of algorithms? Computability .

Swarm Intelligence and bio-inspired computation have become increasingly popular in the last two decades. Bio-inspired algorithms such as ant colony algorithms, bat algorithms, bee algorithms, firefly algorithms, cuckoo search and particle swarm optimization have been

Metaheuristic Algorithms Genetic Algorithms: A Tutorial “Genetic Algorithms are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might not otherwise find in a lifetime.” - Salvatore Mangano Computer Design, May 1995 Genetic Algorithms: A Tutorial

algorithms, which are very different in principle than the above algorithms, are covered in Chapter 6. Genetic algorithms—search and optimization algorithms that mimic natural evolution and genetics—are potential optimization algorithms and have been applied to many engineering design problems in the recent past.

In this course we study algorithms for combinatorial optimization problems. Those are . and so it is unlikely that we can design exact e cient algorithms for them. For such problems, we will study algorithms that are worst-case e cient, but that output . make us give a second look at the theory of linear programming duality. Online Algorithms.File Size: 832KB