Sort all intervals by beginning time - O(n*log(n))
Have a DP[N] which shows the best value calculated for intervals up to that interval including it (left to right), initially DP[i] = value[i]
For each interval i, check each interval k = 0->i-1 and if they don't overlap with i, DP[i] = max(DP[i],value[i]+DP[k]), result is max element of DP, which turns out to be O(N^2)

Hi, thanks for this repository and ability to discuss the problems from CLRS!

For 15.3-2, don't you think that problems can actually overlap as they can repeat. Here is the example.

4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1
4 3 2 1 4 3 2 1 ...
4 3 2 1  4 3 2 1 ...
4 3  2 1  4 3 2 1 ...
3 4  1 2  4 3 2 1 ...
1 2 3 4  4 3 2 1 (memoization) ... 
1 2 3 4  1 2 3 4 ...
1 1 2 2 3 3 4 4  4 3 2 1 4 3 2 1 (memoization)
1 1 2 2 3 3 4 4  1 1 2 2 3 3 4 4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 

Of course there is problem with memoization. How to store solutions to previously solved? How to compute hash? Key storage: O(n), value: O(n). Compute hash time: O(n). It needs to iterate subproblem elements before solving it recursively to determine that the same problem solved before. Hence: $T(n) = 2T(n/2) + n + n$. Space: $~nlog(n)$.

3. Sort the elements in S'.

Every element z in S' is z = x - y, for each element y in S.

Since S has been sorted in step 1, it contains all the elements in increasing order. So, won't S' contain all the elements in a decreasing order, which is to suggest that S' is already sorted (decreasing order).
If this is true, this step would be redundant, although it wouldn't affect the asymptotic complexity in case one uses an algorithm with logarithmic time complexity to sort this set.

In 17.4-2 we should consider a case when a_i-1 == 1/2 (for example, we have a table of size 8 with only 4 elements). In this case, when we are dropping an element from the table, the load factor becomes bellow 1/2 (otherwise we is not able to reach 1/4 which is required for contraction, returning to the example, if we have deleted an element from the table there is only 3 elements and 3/8 < 1/2).

ĉ_i = c_i + Ф_i - Ф_i-1 = 1 + (1/2 * size_i-1 - num_i-1 + 1) - (2 * num_i-1 - size_i-1) = 2 + 3/2*size_i-1 - 3*num_i-1 = 2 + 3/2 * size_i-1 - 3/2 * size_i-1 = 2.

In question 4.4-3, originally it was written that we guess T(n) ≤ cn^2 - 6n
However, if we T(n) = 4T(n/2 + 2) + n, we get that
T(n) ≤ 4(c(n/2 + 2)^2 - 6(n/2 + 2) + n = cn^2 + 8cn + 16 - 12n - 48 + n
It was falsely written that the above = cn^2 - 4cn -32c + n

I submitted a PR that addresses this and provides a more general solution by guessing T(n) ≤ cn^2 - dn, for d ≥ 0.

Hi,

Excuse me, for doing my homework assignments, I used the solutions that you provided without providing the references. These assignments will not be published anywhere. I was not aware of plagiarism policies regarding homework assignments. Now, the university charged me for plagiarism. Could you please give me permission for my usage of your solutions for homework assignments? This is my email address: [email protected]

Regards,
Narges Zarnaghinaghsh

In the INSERT function, you may need to change the parent->successor when it's child larger than it (child.key > parent.key).

In the solution the bottom-right most element should be replace with the top node, not copied there.
A correct example can be found at:
http://www.cs.toronto.edu/~trebla/CSCB63-2018-Summer/06-heap-p1.pdf

Hi, I have read your site and find it very helpful. I just want to print it out on paper to make it easier to read. I wonder could you please provide a pdf version and I can use. A possible way is to put your site on gitbook which can generate pdf file automatically.

Given answer have not considered the milli or nano prefix in the unit though!

I think it asks approximately minimize the B-tree search time. We can interpret the a+bt time equation as follows. a is a constant time independent of read or write of a page, it may be moving the head from one track to another. bt is the expected time spent in reading or writing t items of the page. When a = bt, we have at least spent a time equal to the amount we waste as a. Therefore t = b/a = (5ms)/(10us) = 500 ( page size)

I think this is what they expect from the question.

Firstly, this is a very helpful project – thank you!

One minor issue is that there seems to be an issue with the rendering of "not equals":

I am on the latest Chrome – Version 74.0.3729.169 (Official Build) (64-bit).
I tried on Safari as well, it looks a bit off but not as bad as chrome

Robert

d(a,b)+2d(s,c)=d(s,a)+d(s,b)<d(s.x)+d(s.b)
d(x,b)=d(s.x)+d(s.b)√
d(x,b)=d(s,c)+d(s,b)×
The author may have mistyped this detail by accident, but I really appreciate the information provided by the author, which has brought great help to my study.

I was looking for the answer of the exercice 5.2-2 and I'm asking myself if is is correct. Because there are cases that are not take into account I think, but I'm not sure.

For example if we hire first the candidate with the rank k (for example: k = 3) and directly after, we hire the candidate with the rank n (ex: 6) the procedure hire exactly twice too. But the solution doesn't take these events into account.

Hi thanks for the contribution !

I found an issue in 22.4-2:

The recursive solution works but does not end in linear time. The subproblem is overlapping. Take the path from s to t as example, we mush do a topo sort first, take the intermediate node {v1....vk-1}, and run a buttom-up DP from t. call s v_{0}, t v_{k}, we have:

SIMPLE-PATHS(G, u, v)
    Topo-Sort(G)
    list the vertex between u, v as {v[1], v[2], ...., v[k-1]}
    let v[0] = u, v[k] = v
    for j = 0 to k-1
        DP[j] = INT_MAX
    DP[k] = 1
    
    return SIMPLE-PATHS-AID(G, DP, 0)
    
 SIMPLE-PATHS-AID(G, DP, i)
    if i > k
        Return 0
    else if DP[i] != INT_MAX
        Return DP[i]
    else 
       DP[i] = 0
       for v[m] in G.adjlist(v[i]) and 0 < m <= k
            DP[i] += SIMPLE-PATHS-AID(G, DP, m)
       Return DP[i]   

And return DP[0] as answer. In this way we avoid recursively solve overlapping problem and return answer in $\Theta(V+E)$.

If there are odd number of chips, one extra chip will be left out, if the extra chip is a good chip, the invariant might be broken in the grouped chip pairs.

There is a solution that fixes the problem: https://efanzh.org/2018/10/05/introduction-to-algorithms-exercises.html#chip-testing.

2^(2^n) and (n+1)! shouldn't be in the same equivalence class.
When n -> ∞, lg(2^(2^n) ) - lg((n+1)! ) = 2^n - lg((n+1)! ).
Since lg((n+1)!) = lg(n+1) + lg(n!) = Θ(lgn) + Θ(nlgn) = Θ(nlgn), there exists a constant c making lg((n+1)!) <= cnlgn.
So when n ->∞, 2^n - lg((n+1)! ) >= 2^n - cnlgn >= 2^n - cn^2 -> ∞
Therefore, when n ->∞, 2^(2^n) / (n+1)! -> ∞, 2^(2^n) = ω((n+1)!).

For 31.1-8, it is written "Iterate a from 2 to sqrt(n), and do binary searching." But if n contains B bits, sqrt(n) contains about B/2 bits, and it contains 2^(B/2) values, which is not polynomial but exponential in term of B.

Hello,
Shouldn't the answer for D, part 1, worse case should be Theta(N^2) instead of Theta(N)? Because all insertion will go to the right or left and you have to walk down to the bottom n times over n insertion which lead to n^2 run time?

Thanks!

The black chain violate the property 5. No correct.

4.4-3 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 4T(n/2+ 2) + n. Use the substitution method to verify your answer

when n = 4, get T(4) = 4T(4/2 + 2) + 4 = 4T(4) + 4 which is endless loop.

I'm pretty sure the answer is O(n^lg(3)). It's not O(n^2).

Source: http://sites.math.rutgers.edu/~ajl213/CLRS/Ch4.pdf

Hello Jay,

there are several errors in this way:

"ParseError: KaTeX parse error: Expected '}', got '&' at position 51: …= \{f(n): &̲ \text{ there e…
"

I'm not latex guru, Could you share me more info about it??

Best regards
Oliver

A lot thanks for your beautify solutions to this book.

I have a question for 16.4-2, if you do not mind I opened an issue here:

Your answer only proved the if part of the question, not the only if part. Do you have any ideas about how to do that?

Hi!

Question 15.2-4 https://walkccc.github.io/CLRS/Chap15/15.2/
The number of vertices has a typo $j=1$, which should be $j=i$. And the number of edges is incomplete.

Thanks!

First off, thanks for this great resource!

I see that the answer for 4-3a is derived using the master theorem. However, to me, this recurrence seems to fall outside the scope of the master theorem: specifically, the textbook notes that "there is a gap between cases 1 and 2 [of the master theorem] when f(n) is smaller than n^(log_b(a)), but not polynomially smaller" (Page 95). Wouldn't this problem fall into that gap?

For an example of another recurrence that falls into a similar gap between cases 2 and 3, checkout the example given at the bottom of that same page (Page 95): T(n) = 2T(n/2) + nlgn.

Can something be done about this feature requests? I don't think it should be too hard to implement it. You can implement a switch similar to how it has been done on the CS APP 3e solutions website.

https://walkccc.github.io/CLRS/Chap04/Problems/4-1/

f(n) = n^4 but you solved for n^3 instead

Should be Big Theta(n^4)

The solution to problem 15.1-2 gives the table of pi/i
In that pi/i of column 4 should 9 (36/4).

Solution 26.5-2 is not exactly correct, because lemma 26.28 doesn't apply in this case, and since Solution 26.5-4 just copied Solution 26.5-2, it's also incorrect. I think the complexity of either of these algorithms does rely on the data structure it uses. We only need to give an O(V^3) bound on the number of DISCHARGE calls, so it remains to prove the O(V) bound on the number of DISCHARGE calls in each phase ,i.e. between two consecutive RELABEL calls. The proof for 26.5-4 is that by always discharging the highest vertex, the height of discharged vertices is monotonically decreasing in each phase, so a discharged vertex is never recharged in the same phase. As for 26.5-2, I have no idea how to prove it.

PRINT-LCS(c, X, Y)
For 12 line: else if c[i - 1, j] ≥ c[i, j - 1]
missing a statement for else if branch.

It should be:
else if c[i - 1, j] ≥ c[i, j - 1] i = i - 1

In the last third line of the solution this is written:

This is true, since g(m)>g(n) and f(n) is monotonically increasing.

It should be:
This is true, since g(m) <= g(n) and f(n) is monotonically increasing.

In question (3.1-8) the O-notation bound should be 0≤f(n,m)≤cg(n,m), instead of 0≤cg(n,m)≤f(n,m) and the Ω- notation bound should be 0≤cg(n,m)≤f(n,m) in the answer.

It shows that n2^n is omega of e^n.
However, e^n is omega of n2^n as the justification (1) provided said that (e/2)^n is little omega of n
(e/2)^n is still an exponential function and should be o of n, and graphing the two clearly shows that n < c(e/2)^n
(Or computing the limit of ((e/2)^n) / (n) as n goes to infinity and using l'hopital's results in it tending to infinity)
UPDATE:
Sorry, misread something

It seems like at i=0, the sets are wrongly indexed.

According to me, following are the correct set values. Can you please check ?
K1 = {4, 8};
K2 = {3};
K3 = {9, 2, 6};
K4 = {};
K5 = {};
K6 = {1, 7};
K7 = {5};

Hi,

We need to determine an upper bound using recurrence tree and your answer has O(2^n) as the upper bound.

O(2^n) seriously? I mean that is a valid upper bound for most functions but it's not tight enough. I think O(n^2) would do for the given recurrence relation.

Also, for many solutions in 4.4-* you haven't given the recurrence tree, which draws some confusion in the solution (4.4-8 ). It's good to be confident about one's answer, provide as many details as possible into the thought process that lead to the answer

Thanks for the hard work 👍

The answer to 6.1-6 says:

No. The property is violated by the next-to-last leaf (illustrated below in red.)

However, nothing is illustrated.

I think this gives the wrong answer if the edges of the cycle is not in a specific order.
For example,

3 3
1 2 -1
3 1 -1
2 3 -1

After running lines 1 to 4. The distances will be -3, -4, -5 respectively. Then for the modified lines. the first edge doesn't change the distance. The second sets d[1] = -OO. The third doesn't.

It could be done by running these two line |V| times which takes O(VE). Or if the condition v.d > u.d + w(u, v) is true for some vertex v, the distance of v and all vertices reachable from it should be set to -OO which works in O(E + V).

Would it be

Dear Jay,

I was looking at the solution to problem CLRS on https://walkccc.github.io/CLRS/Chap22/22.3, and it says: "See the algorithm DFS-STACK(G)". However, I couldn't find the DFS-STACK algorithm anywhere on the page. Where is it located?

Sincerely,
Evgeny Makarov

The problem states difference between the binary-search-tree property and the min-heap property. The answer is based on the property of max-heap where parents are greater equal than children.
But it should be answered by the property of min-heap, where parents are less equal to children.

First time writing an issue on github.
I think I've found two issues in 24.1-1.

• In the upper figure, the predecessor of y should be s, not z
• The lower figure shouldn't even exist, as the modified graph contains a negative weight cycle (the cycle x > t > z > x cost -2)

Only the running time is mentioned.
The solution (most probably correct) can be found in my git repo CP Library in the string.cpp file

Hello, on your work corresponding to chapter 15 problems, 15-1. Longest-Path-2, using a bottom up approach. I am wondering if there is a typo in the conditional of the nested for each loop...

1 if dist[u] + w(u, v) > dist[v]
2 next[v] = dist[u] + w(u, v)
3 next[u] = v

It seems to be that line 2 should be dist[v] = dist[u] + w(u, v) ...Would you agree?

problem 10-2,b,union algorithm is not given

I think the solution of 3.2-3 is not totally correct on the prove of n!=o(n^n) and n!=ω(2^n)
The given solution is only proving that n!=O(n^n) and n!=Ω(2^n).
The solution should use the magnitude of (n!/n^n) as n->∞ and (n!/2^n) as n-> ∞ to prove it.

`function divide( array, flag )
let bigger, equal, smaller be a empty array
for i=1,array.length do
if array[i] > flag then
insert(bigger, array[i])
elseif array[i] < flag
insert(smaller, array[i])
else
insert(equal, array[i])
end
end

return bigger, equal, smaller

end

function find_sum_aux( smaller, bigger, flag, target )
if smaller.length == 1 and bigger.length == 1 then
return true
elseif smaller.length == 0 or bigger.length == 0 then
return false
else
bigger1, equal1, smaller1 = divide(smaller, target/2 - flag - flag/2)
bigger2, equal2, smaller2 = divide(bigger, target/2 + flag + flag/2)
if equal1.length > 0 and equal2.length > 0 then
return true
else
return find_sum_aux(bigger1, smaller2, 3flag/4, target) or find_sum_aux(smaller1, bigger2, 1flag/4, target)
end
end
end

function find_sum( array, target )
bigger, equal, smaller = divide(array, target/2)
if equal.length >= 2 then
return true
else
return find_sum_aux(smaller, bigger, target/2, target)
end
end
`
loop invariant:
init:
if there is two number whose sum is x, the smaller one must small the target/2 and the bigger one should bigger the target/2.
maintance:
there are two array, smaller one should in smaller array, and bigger one in bigger array,continue divde to more smaller and more bigger one.
end:
if one of two array is zero means no sum. two of array are length 1 means has

In ch31 problem 3, the second complexity is not correct. I'm pretty sure that it should be O(B 2^B), since we do n = 2^B additions of size B = lg n.
If you compute sum_(i=1)^n lg n, it's O(n lg n ) by the integral approximation.
Another way to see it, the recurrence is T(n) = T(n-1) + lg n , which is the same than problem 4.3.h.

However for the first one, I'm not really sure how you could compute it, the recurrence can be upper bounded by the recurrence T(n) = 2 T(n-1) + lg n and I don't know how to compute it.
If you try to compute the sum, it's
sum_(i=0)^(n-1) 2^(n-i) lg i
I don't know how to compute or bound that sum either.

problem 3-1 answer: the lower right corner of the form should be no, right?