jeffgerickson / algorithms Goto Github PK

Page 113 has the edit distance memo table for ALGORITHM to ALTRUISTIC - the entry for ALGORIT to ALT has a cost of 4 with both a free replacement and a deletion from a cost of 4 - should the deletion arrow be there ? I very much like your notes and have been using them for a couple of years (with attribution) - I recalculated the table and my version is on my slide 108/142 of http://www.pmolyneux.co.uk/OU/M269/M269TutorialNotes/M269TutorialGraphs/M269TutorialGraphs2017J.beamer.pdf - it looks like your notes are produced in LaTeX - I used LaTeX with the PGF/TikZ package to typeset the table (though I used Haskell to calculate the PGF/TikZ for the table)

I believe the last swap in the partition pseudocode should be :
swap A[ n ] <-> A[ l + 1 ]
since the pivot is set to the back of the array and not the front

"people who are wrong" -> "people who are wrong."

I might be mistaken, but I believe that there's an error in the average run-time analysis of the quicksort algorithm on page 30.

Specifically, if we substitute a pivot about the median element (i.e., ⌈n/2⌉) into the first recurrence, we should end up with

T(n) = T(⌈n/2⌉ - 1) + T(⌊n/2⌋) + O(n) <= 2T(n/2) + O(n)

instead of

T(n) = 2T(⌈n/2⌉ - 1) + T(⌊n/2⌋) + O(n) <= 2T(n/2) + O(n).

That is, there appears to be an errant 2 on the left side of the equality statement.

On a related (but minor) note, in the recurrence analysis of the worst case run-time that follows, I believe the parentheses around the max(...) function can be scoped tighter, since O(n) is constant for all values of r.

Add Don Sheehy's data structures literate program / textbook (https://github.com/donsheehy/datastructures) to recommended prerequisite references in the Preface.

There is a typo in the formula in footnote 10 on page 41. It should be
(a+b)(c+d)-ac-bd = bc+ad
So the first part has b and c swapped.

Section 12.4
... A Turing machine is a very restrictive type of computer whose precise definition is surprisingly unimportant.

(incredible book by the way !)

Footnote 9, missing period.

I'll add any more if I notice them.

Or anybody else is welcome to comment. Why perhaps do you not open a set of Issues "Typos in " and let people comment?

Top of page 14, " (Slide) " appears to be an extraneous remnant. Or a joke I don't get?

It is a very minor issue but while solving Question 36 in the dynamic programming section I noticed that
( 1 + 3 ) × 2 × ( 0 + 1 ) × ( 6 + 7 )= 208 is incorrect, it should be
( 1 + 3 ) × 2 × ( 0 + 1 ) × ( 6 + 7 )= 104.

It should be written "mnemonic"

"An edge is safe if it is the minimum-weight edge with with exactly one endpoint in some component of F." in section 7.2 The Only Minimum Spanning Tree Algorithm

This sentence appears to be missing a verb:

For example, in 1999, Uwe Schöning
the running time of the randomized local search algorithm to O((4/3)
n poly(n)).

In the second paragraph, it says

We can’t move it at the beginning, because all the other disks are in the way. So first we have to move those n−1 disks to the third peg

It's actually, move those n-1 disks to the second peg

All the extra n-1 disks have to be moved to second peg, the largest n^th disk has to be moved to the 3rd peg and all n-1 disks have to be moved on top of the n^th disk in 3rd peg.

I tested these files using iBooks (EPUB), the Kindle Mac app (MOBI), and Calibre (both); they're complete garbage. Apparently those files were created by extracting OCR'd text from the PDF file, including OCRing text in figures, but completely bollixing graphics and math and tables and everything.

Producing a true reflowable e-book format is preactically impossible, but at least this crap should be removed.

Section 2.1 reads:

If we try to match a nut witch a bolt

witch to with

To quote Acrobat's report:

Warning:

• Document images on CMY plates (45 matches on 3 pages): 23, 344, 417
• Uses device-independent color (3 matches on 2 pages): 23, 344

Info:

• Resolution of bitmap images is less than 550 ppi (1 match on 1 page): 23 — [Eutocius in Greek]
• Text is smaller than 5 pt (250 matches on 16 pages): 69, 91, 183, 212, 244, 248, 255, 257, 299, 300, 302, 306, 310, 344, 375, 426 — [mostly sub/superscripts in figure labels]
• Uses CID Type 0 font (2 matches on 1 page): 228 — [star in number maze]

5.7 Graph Reductions, Flood Fill

"The flood-fill problem can be reduced to the reachability problem by chasing
the definitions" -> "The flood-fill problem can be reduced to the reachability problem by changing
the definitions"

Please correct me if I am wrong, but I think the lemma asked to be proven in the exercise 3(c) of chapter 6 is incorrect.

Let T be an arbitrary spanning tree of G, rooted at an arbitrary vertex r.
For each vertex v, let T_v denote the subtree of T rooted at v; for example,
T_r = T . Prove that v is a cut vertex of G if and only if G does not have
an edge with exactly one endpoint in T_v .

Consider the below (DFS) spanning tree for example:

Clearly vertex 1 has an edge with exactly one endpoint in T₁, but vertex 1 is a cut vertex.

In sec. 0.1, an algorithm is informally defined, described. It lists a set of conditions for it including unambiguousness, precision, etc. of instructions.

But it does not list finiteness of the sequence of instructions as a necessary condition.

I think this is not consistent with how algorithms are defined and understood in the CS community. They are defined, among other things, to be finite sequences of instructions.

Therefore, I think the list of conditions should be amended to include finiteness as a necessary condition.

Thanks.

page 114, section 3.8: In the pseudo code recurrence relation at the bottom of the page for subset sum modified for avoiding the case when t is negative, it says SS(i, t) = SS(i + 1, t) when t > X[i] in the third case, for that case wouldn't it be valid when t < X[i] rather than t > X[i], as that would make the t that is being passed in negative when doing SS(i, t - X[i]) which would automatically yield a False.

The following seems like a definition of a Hamiltonian path, rather than a cycle, since in the latter case the starting/terminal vertex gets visited twice.

A Hamiltonian cycle in a graph G is a cycle of edges in G that visits every vertex of G exactly once

pg iv:

the goal of these problems not to solve these particular problems,
but to practice exercising a particular skill

wants to have is between problems and not to.

I'll add more typos to this issue as I find them. Thank you for your book.

Unrelatedly: is there a chance you would share the source files for the book?

The book was supposed ot be out over the summer. Where is it? These constant delays are completely unprofessional!

In the Gauss quote in section 2.1, the German word Gewissheit is misspelled as Gewifsheit, presumably due to a mis-transliteration of a long s (ſ) into an f.

In modern German, the world is spelled with a double short s: Gewissheit.

This book looks great! Thanks for writing it and making it free. There are some very interesting problems and topics and I hope to work though it some day.

From looking at the table of contents, my attention was drawn to section 3.1 titled Mātrāvṛtta. Firstly, glad to see this. :-) And as I've read a tiny bit about the topic, a couple of corrections: in

one class of meters, variously called mātrāvṛtta or mātrāmeru or matrāchandạ

— here, ("Meru" is the name of a mountain; and “mātrāmeru” is the name of a “mountain” of numbers or metres, somewhat like “Pascal's triangle”, so) mātrāmeru should be removed, as it's not a name of the class of metres. Also, the last word should be mātrāchandas (with an s at the end, and without the dot below the a).

(There's unfortunately not a great reference for these that I'm aware of—what did you use?—though this is one that at least cites the primary sources properly.)

Also, later down the page it says “—“ with two opening quotes instead of an opening/closing quote pair.

Recording minor typos in commit b2ea560.

In the updated LISBigger pseudocode that uses indices instead of arrays, the else if block is using the same code as the previous version:

...
else if A[1] <= prev
...

when it should be using the new version:

...
else if A[i] >= A[j]
...

as per the piece-wise function definition.

The following typos exist in fbf5aea and therefore also in the B&W bc54407.

Page 226 of the main book (§6.1): The first sentence of the first paragraph under the pseudocode for Preprocess, PreVisit, and PostVisit reads "This algorithm assigns v.pre (and advance the clock)": "advance" should be "advances". A similar typo exists later in the sentence after v.post.

Page 257 of the main book (§7.2): The last bullet point has a duplicated word "An edge is safe if it is the minimum-weight edge with with exactly one".

(These two typos are right next to typos found in my previous typos issue too! Ugh!)

In Greedy Algorithms, 4.5 Stable Matching, section "Some Bad Ideas", page 170

At the top of the page:

Unfortunately, resolving one instability can new ones

Should probably be "can create new ones" or such.

„Given a boolean circuit, is there is ...“
—> remove „is“ behind the comma.

In Figure 1.5 line 3 and 4 the left part is not actually sorted correctly 'S R' should be 'R S'.

In ch1, Anatoly Karatsuba's last name is misspelled several times as "Karastuba."

On http://jeffe.cs.illinois.edu/teaching/algorithms/ clicking 'two pages per page (for printing)' results in a 403 forbidden error

In Chapter 6, "Depth-First Search", in the section "Koraraju and Sharir’s Algorithm", Kosaraju's name is misspelt in the title and body text as "Koraraju".

(The footnote on the first page of the section, however, as well as the algorithm pseudocode itself, has the correct spelling for the name.)

A professor I had in college was compiling lecture notes into a textbook, and offered $5 for any typo or error discovered in the notes. My friend exploited this by searching for "double words," like "the the," etc. My friend made quite a bit of money that semester.

Along these lines, I've found "the the" in Sections 7.1 (page 256) and 7.5 (page 265), and "of of" in Exercise 7.4b (page 266) and Section 9.3 (page 310). There may be other words which are repeated in this manner, I didn't check them all.

I think it should be a letter 'B' instead of 'D'

An EPUB (or MOBI, or AZW3) format version of the book would be very much appreciated.

At http://jeffe.cs.illinois.edu/teaching/algorithms/, there is a link "Disjoint Sets" with href="notes/11-union-find.pdf", which currently results in a "404 Not Found" error message.

The following typos appear in the 0th edition, dated December 29, 2018:

• In the footnote on page 26, I believe it should read:
  • "...because the EDVAC could sort faster than IBM’s dedicated sorters..."
• On page 29, I think it should probably read:
  • "In the separate Partition subroutine, the input parameter p is the index of the pivot element..."
• On page 30, it should probably read:
  • "...and take the median of those three elements as the pivot."

Near the end of the first section of B.2, we find the following:

Thus, the
number of maximal independent sets satisfies the recurrence M(n) ≤ 2M(n − 1), with
base case M(1) = 1. We can easily guess and confirm the solution M(n) ≤ (2^n) − 1. The
only subset that we aren’t counting with this upper bound is the empty set!

I'm not 100% confident in my understanding here, but if I understand what you're trying to do with the "easily guess and confirm", then that should be parenthesized as 2^(n-1) instead.

There are 2^d vertices in a d-dimensional hypercube.

I should create a few issue templates (https://blog.github.com/2016-02-17-issue-and-pull-request-templates/) for different types of issues, for example: book / notes / hwex / web site, or feature request / typo / minor bug / major bug / dumpster fire.

Low priority, because I need to see what kinds of errors people actually report.

Hi,

in 0.6, algorithm for Alouette, the french is clumsy.

Plumerais -> plumerai, 3 times (future https://leconjugueur.lefigaro.fr/conjugaison/verbe/plumer.html)
'a -> à, 2 times (other direction)
'a bas 'a -> à
inner loop: i-1 -> i (I think you have to re-sing the introduced part, cf https://en.wikipedia.org/wiki/Alouette_(song) )

Thanks,
Florian

"negative wedge weights" in ♥8.2 Negative Edges

Bonjour ;-)

I noticed two mistakes on the December 29 version:

• page 24, "Éduoard" should be "Édouard"
• page 70, "tâttoner" should be "tâtonner"

I understand the pseudocode as follows:

The first for allocates n representatives, and decreases R by n (I'll call this R' = R - n).
The second for runs from n+1 to R', i.e. it allocates R - 2n representatives.

The total number of representatives allocated is then only R - n.

Now what order should store the files if we want to minimize the total cost?
should be changed to
Now, in what order should we store the files if we want to minimize the total cost?

The printed book needs an index. (The real world doesn't have grep / ctrl-F / a magnifying glass icon.)

They are similar in shape and colour, and differ only slightly in size, so you need to have them side by side to notice the difference.

A different symbol for the open problems would be appreciated.

I think the code of quick select in page 35, Chap 1.8 actually find the kth smallest element, but the text was talking about kth largest element.