
Post by Admin on May 4, 2019 23:19:10 GMT
Please use this thread to report errata in Part 3 of Algorithms Illuminated (Greedy Algorithms and Dynamic Programming). Please include the page and line number. Thanks! TR



Post by giorgio on Sept 24, 2019 2:02:13 GMT
I am reviewing the answer to Quiz 15.4 (page 80). Wouldn't answers b, c and d be true (and not just c), based on the argument spelled out in footnote 28? If log(n) can be used interchangeably with log(m) given this kind of connected graphs, wouldn't the running time of O(mn) be the same as O(m^2) or O(n^2) in Big O notation?



Post by Admin on Sept 27, 2019 13:39:22 GMT
I am reviewing the answer to Quiz 15.4 (page 80). Wouldn't answers b, c and d be true (and not just c), based on the argument spelled out in footnote 28? If log(n) can be used interchangeably with log(m) given this kind of connected graphs, wouldn't the running time of O(mn) be the same as O(m^2) or O(n^2) in Big O notation? giorgio: Remember that bigO notation suppresses leading constants and lowerorder terms. It does not suppress constant factors in the exponent. Suppose m = n^2. Then it is not the case that m = O(n). (See Section 2.3.2 of Part 1.) But log m = 2 log n, so log m = O(log n). TR



Post by spamegg on Oct 4, 2019 6:08:32 GMT
In Problem 13.1 (page 21), it's given that jobs have length l_j and deadline d_j.
Then parts (b) and (c) mention something called "processing time" p_j.
p_j was never defined in the question.
I suppose p_j is supposed to be the same as l_j?
It's very confusing because at first I thought p_j was the same as completion time.
"Processing time" sounds a lot like "completion time".



Post by Admin on Nov 17, 2019 0:28:41 GMT
In Problem 13.1 (page 21), it's given that jobs have length l_j and deadline d_j.
Then parts (b) and (c) mention something called "processing time" p_j.
p_j was never defined in the question.
I suppose p_j is supposed to be the same as l_j?
It's very confusing because at first I thought p_j was the same as completion time.
"Processing time" sounds a lot like "completion time". spamegg: Good catch! Indeed, the problem should say "length" instead of "processing time" to be consistent with Section 13.2 I'll fix this in the next (second) printing. Thanks! TR

