In this thread we discuss our progress reading “Introduction to Algorithms, Fourth Edition”. We gather every Saturday and Sunday at 12:00 (noon) UTC.
Reading goals for next Saturday: Chapter 3
I've extended the time we have to finish chapter 3 because I was pretty busy with work this week. Did you get through all of this week's content? Let us know if you think we are going too fast or too slowly.
Today's discussion questions: Name a loop invariant property which is not mentioned in the book, and prove that it is loop invariant. 2.1-4 Write pseudocode for linear search, which scans through the array from beginning to end, looking for x . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfils the three necessary properties.
You will gain the most by doing the exercises and problems yourself! Spoilers are not enabled on this board, so please not post solutions for exercises or problems for sections: 3.1 and beyond
Notable changes from the third edition for this week’s content: None
Cool thread, I've been meaning to dig into this book myself. Any tips for how to catch up so I can stay with these threads? Also I have third edition but I'm assuming the differences are trivial, can anyone confirm/deny?
Noah Watson
sup algochads I bought the 3rd edition around a year ago but got filtered hard by induction
in college they taught us many times, I watched lecture about Mathematics for Computer Science about it yet still I don't get it.
I mean, I understand how it is supposed to work yet it all seems like a bunch of bs. After the first base case is it really just replacing your formula where every x is x+1 and the solving it, and somehow this proves that it works all along?
Show it works for 1. Given it works for n, prove that it works for n + 1. With these two parts combined, that means working for 1 means it works for 2. Working for 2 means it works for 3. Working for 3 means it works for 4. And on to infinity.
William Gomez
>Given it works for n why? why assume it works for n if that is what we're trying to prove
Colton Mitchell
Because you start with this: Prove it works for 1. Given it works for 1, prove it works for 2. Given it works for 2 prove it works for 3. Given it works for 3 prove it works for 4. Then you take a step back and notice that all your proofs are the same. Essentially, you just write a function prove(n, n+1) instead of implementing prove(2,3) and prove(3,4), etc.
Henry Nelson
>After the first base case is it really just replacing your formula where every x is x+1 and the solving it, and somehow this proves that it works all along? You prove it works for the base case, which is usually 0 or 1; then you take for granted that it works for x and you prove that if it works for x it should work for x+1 too.
That is enough to prove everything because: >if it works for 0 (base case) then it works for 0+1=1 due to the inductive step; >if it works for 1 (previous inductive step) then it works for 1+1=2 due to inductive step; >if it works for 2 (previous inductive step) then it works for 2+1=3 due to inductive step; >so on and so forth.
It similar to how you can construct every natural number by with a function succ(n)=n+1 and a starting point 0. >0 is a natural number (starting point) >1 is a natural number because it is equal to succ(0) >2 is a natural number because it is equal to succ(succ(0)) >3 is a natural number because it is equal to succ(succ(succ(0)))
Proving the inductive step only is not enough because you don't have a starting point.
Ryder Harris
after all these years, I think I finally get it, thanks! I didn't understand how critical the base case is so I was pretty much ignoring it and focusing only on the induction step. proof(n, n+1) by itself is not enough and left me confused but now I understand that proof(1) and proof(n, n+1) proves 1, 2, 3, ..., n
Jacob Hernandez
the preface of the fourth edition tells you what the major changes are.
in addition I am also posting about any significant changes in the material we are reading. for example, next week we are finishing chapter 3: > Notable changes from the third edition for this week’s content: > None
Luis Mitchell
>then you take for granted that it works for x and you prove that if it works for x it should work for x+1 too. this part always confused me as to why are we allowed to assume something that we're trying to prove But I think that just because we assume doesn't mean it's true, if we fail to prove then our assumption is wrong
Fuck off I already graduated, my advice is pick up a maths book instead.
Camden Nguyen
> if we fail to prove then our assumption is wrong I don't think that's necessarily accurate in this case, maybe you're thinking about proof by contradiction: If we try our hardest and cannot find a proof that 'if A is true then B is true', this doesn't tell us much about either statement. But if we have a proof (1) that 'if A is true then B is true' and another proof (2) that 'B is not true', then we can combine those to obtain a proof (3) that 'A is not true'.
