walkccc / clrs Goto Github PK
View Code? Open in Web Editor NEWš Solutions to Introduction to Algorithms Third Edition
Home Page: https://walkccc.me/CLRS
License: MIT License
š Solutions to Introduction to Algorithms Third Edition
Home Page: https://walkccc.me/CLRS
License: MIT License
problem 3-1 answer: the lower right corner of the form should be no, right?
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.
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
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
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.
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.
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.
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.
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.
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?
The solution to problem 15.1-2 gives the table of pi/i
In that pi/i of column 4 should 9 (36/4).
`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 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 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};
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 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
problem 10-2,b,union algorithm is not given
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
The black chain violate the property 5. No correct.
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.
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
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?
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).
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.
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 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.
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.
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.
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
First time writing an issue on github.
I think I've found two issues in 24.1-1.
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!
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 š
In the INSERT function, you may need to change the parent->successor when it's child larger than it (child.key > parent.key).
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.
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'm pretty sure the answer is O(n^lg(3)). It's not O(n^2).
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.
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)
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
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 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.
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:
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)
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)!).
Hi!
Question 15.2-4 https://walkccc.github.io/CLRS/Chap15/15.2/
The number of vertices has a typo
Thanks!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
š Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ššš
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ā¤ļø Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.