gzc / clrs Goto Github PK

I've just looked at the solution for one exercise about the interval trees in chapter 14, and it's wrong in my opinion. You should not share something that's not proved to be correct, it's not helpful at all!!

3 elements are incorrect according to the question provided.
A should be modified as [13, 19, 3, 5, 12, 8, 7, 4, 21, 2, 6, 11].

solution not fond 404

Browsng content directly in github repo is not convenient. How about using GitBook to publish your content? https://www.gitbook.com/

The numbering of the solutions is wrong. For example, section's 4.3 exercises have nothing to do with the third edition of the book.

For example on the 3rd edition the exercise 4.3-1 is:

"Show that the solution of T(n) = T(n-1) + n is O(n * n)".

In Ex9.1-1. I feel confused by this statement.
. Can you help me. Thx.

I can't get the main idea of your idea, but i google some solutions, and this one
Answers of Ex11.3-2 is appriate for this question. And i can not get the point of this paragraph
Another way would be using n-degree equation with each character value acting as a co-efficient for the nth term. Example: S[0]*xn + S[1]*x(n-1)+ …. + S[n-1], for better result substitute x = 33 or 37 or 39. This is the famous Horner’s method for finding a hash value.
If you can figure it out. Plz tell me. Thanks a lot.

This question is about B-Trees. The question asks for the legal trees with min degree t=2, but the solution is for t=3.
So the correct answer is 4 trees:

     2
  1     3 4 5

         4
  1 2 3     5

        3
  1 2      4 5

      2     4
   1     3     5

Although the last tree is correct according to the rules of the B-Tree, the algorithm provided by the book never generates it.

https://github.com/gzc/CLRS/blob/master/C21-Data-Structures-for-Disjoint-Sets/21.1.md#exercises-211-3

How many times is FIND-SET called?
FIND-SET : |E|

I think it should be 2*|E| ? Is it right ?

在您的代码的
void printOptimalBST(int i,int j,int r)
{
int rootChild = root[i][j];//子树根节点
if (rootChild == root[1][n])
{
//输出整棵树的根
cout << "k" << rootChild << "是根" << endl;
printOptimalBST(i,rootChild - 1,rootChild);
printOptimalBST(rootChild + 1,j,rootChild);
return;
}
这一段，在我测试的时候出现了数组越界的情况呢，就是在输出最后一片树叶的时候，感觉是不是应该在最前面加上呢？ 新手求指教！
if(i==N+1&&j==N)
{
cout<<"d"<<j<<"is k"<<r<<" right child"<<endl;
return ;
}

In the repo all solutions are not in english. Do you have solutions in english?

could you please help me to solve this exersice:
Prove that an n-input sorting network must contain at least one comparator between
the ith and (i + 1)st lines for all i = 1, 2, . . . , n − 1.

CLRS/C02-Getting-Started/repo/s1/2.png

i ← i - 1

instead

i ← 1 + 1

a )
for 0 < epsilon < 1,

lg^k n > n^epsilon

and for epsilon >= 1,

lg^k n) < n^epsilon

Therefore, the correct answer is
YES YES YES YES YES

I searched this problem in following URL, maybe you can check this. And i can't figure the running time more than O(nlgn) in the worst time. If you get it. Plz tell me, Thx a lot.

Your answer on 14.2-3
Another answer

Hi, I recently started reading this book. Its good to see this repository with solutions.

For 1.2.2 and 1.2.3, this repository contains only the final answer for it. It would be good to have the explanation of how it was arrived at. Here is what, I have reached at. Please review my method of solving this and suggest a better or good way of solving it. I will raise a PR for the explanation after getting enough feedback.

Exercise 1.2.2

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in
steps, while merge sort runs in
steps. For which values of n does insertion sort beat merge sort?

Insertion sort beating merge sort means,
for an input size n, time taken by insertion sort ( to give the sorted output ) should be less than the time taken by merge sort.

So, I arrived at an equation like this

<

Figuring out all the values of n, that satisfies the above equation would give us the answer.

The equation can further be simplified, as it contains common factor, like this.

8n.n < 8. 8n. log n

// cancelling 8n on both sides

n < 8 log n

Now, I applied n=1,2,3..... on the above equation to figure out the answer as 2 < n < 43

To figure the ending point I have to manually apply the n value from 1 to 43 which is a time consuming process. So, i tried applying n values as powers of 2 ( as it would reduce the time - considering my base as 2 in log n ), this approach, helped me to arrive at a point that maximum value of n satisfies 32 < final value of n < 64. This method made me to be faster in getting the final solution. Is there method that is even faster than arriving at the answer ?

Is this how we arrive at the answer for the exercise ? Are equations correct ? Can my equation be further reduced ?

Exercise 1.2.3

I was able to arrive at an equation, similar to exercise 1.2.2. So if my above questions are being answered, then I will have a clear understanding of how this exercise is solved.

I am reading chapter 3 and 4 and it seems that the exercises look different. I am using edition 3.
Thank you!

I think the solution of the best condition is :
T(n)=2T(n/2)+1

题目和答案不匹配，答案为第三版的答案，但是题目好像不是。

从4.1的solution看，是否对应的是第二版的？第三版增加了两章，问题与您的不一致。

out-degree should be

O(e)

that is total number of nodes in e or simply the the of e (edges list)

首先,运行DFS或者是BFS可以在O(V+E)的时间内统计出每个点的入度和出度,以后在删除边的时候要维护这些信息. 每次输出入度为0的那个点并删除其出边,并维护信息,因此有E条边和V个点,所以要执行O(V)次输出和O(E)次的删除.所以总的运行时间是O(V+E)

每次寻找入度为0的点需要O(V)时间，导致算法的实现不是很高效。

http://stackoverflow.com/questions/11489668/clrs-random-search-how-to-calculate-expected-number-of-picks

answer ,第四行，令m=[lgn]!,应该是多打了个!，令m=[lgn],

what is the solution of this exercise ??
"Give an efficient algorithm for computing the transition function δ for the stringmatching
automaton corresponding to a given pattern P. Your algorithm should
run in time O(m |�|). (Hint: Prove that δ(q, a) = δ(π[q], a) if q = m or
P[q + 1] �= a.) "
An early reply would be appreciated.

not both 1, the first one is (1 / 4) * 1^2 * 2 + (1 / 4) * 2^2 = 1.5

answer:先看快速排序的那部分，当高度为lg(n/k)便停止了快速排序。

应该是高度为lgk的时候，停止了快排。然后快排运行了lgn-lgk层，故时间复杂度应该是O(lgn/k)

应该不能维护吧？

当插入一个节点，递归到根节点，当根节点直接变为黑色，所有节点的黑高需要加一。 复杂度为O(n)。

I think answer should be

~ | s | t | x | y | z
d | 2 | 4 | 6 | 9 | 0
π | z | x | z | s | Ø

~ | s | t | x | y | z
d | 0 | 0 | 2 | 7 | -2
π | Ø | x | z | s | t

Correct me if I'am wrong.

I have run the code. If the input array is [2, 3, 6, 4, 6, 5, 6], the output will be [2, 3, 4, 6, 6, 5, 6]. This is obviously not right.
Your code works rightly when all elements in the array have the same value. But when only some are the same, problems may arise.

Maybe you need to check your answer. I can't figure out why we need to reverse the string. And i can't get you. Check at 8-3

https://github.com/gzc/CLRS/blob/master/C23-Minimum-Spanning-Trees/23.1.md#exercises-231-11-

该题目的思路跟作者是一样的：将权重减少的边添加回到最小生成树T中，一定会形成一个环，再将环中权重最大的边去掉。

因为题目中已经给出了G和T，所以我们只需要在环中寻找权重最大的边，最差情况下就是DFS遍历一遍T。所以时间复杂度应该是 O(V)，而不是 O(V + E)

不知道我的思路对不对，感谢查阅。

It seems like the problems in chapter 19 remain the second edition. Need to update to the third edition.
Found another version of solution in http://www.math.rutgers.edu/~ajl213/CLRS/
might help

The loop is supposed to start from A.length isn't it?

Shouldn't it be like this?

C = Array[A.length+1]
carry <- 0,
for i <- A.length to 1
    C[i+1] <- (A[i] + B[i] + carry) % 2;
    carry = (A[i] + B[i] + carry)/2;
C[i+1] <- carry;
return C

Can someone good in both languages convert the solutions to english?

第一部分里的4.1md里面的答案跟题目对不上。
你看一下。估计是贴的别的部分的答案

ps：看了这个repo的很多题解，非常有用，感谢您的分享。

题目写成13.3－6的题目了

The answer you post in 14.1-5, but i can not figure how it works. I think the follwing code is more clean than yours. my solution

The answer to exercise 32.1.3 says that "then we can get the T(time) = (n-m+1)*[a(1)*b(1)+a(2)*b(2)+,,,+a(m)*b(m)]
So we get the answer.", but after I sum up the series, I find that the result is

(1-d^(-m))/(1-d^(-1))-m/d^(-m)

(1-d^(-m))/(1-d^(-1))

The implementation just calls the standard library function strstr, it does not actually implement any algorithms on its own.

I'm not quite getting what "S" in the parameter stands for. If it stands for start time, shouldn't there also be an finish time input f and check for if two activities are compatible?

I feel it's necessary to change the title and the book image to indicate that solutions are for 2nd edition.
I come cross the 4th chapter, and it is completely different.

It just makes readers confused, and a little bit waste of time.

Thanks.

能不能再给点详细的解释啊，还是对代码没有太深入的理解呢

最好情况应该调用了Θ(lgn)次吧

A brute force verification will work. Here is the proof.
Proof of the exercise 25.1-4.pdf

wrong left son in the node with index 1, it should be node with index 7, not node with index 3.

好像Exercises 22.2-5中那个图最左边那两条边是可以用BFS得到的。

Hi,
I think it should be "n!/2, n!/n, n!/(2^n) are smaller than 2^n only when n is small"
instead of "increasing speed of n!/2, n!/n, n!/(2^n) are slower than 2^n"