I am ignorant and stupid and probably missing the significance this technique offers for later more complicated algorithms, but I cant help but just keep thinking to myself, "....... yeah. Okay?" Still took notes though!!!
We spend the first few weeks of class dealing with the tools of program analysis, for correctness proofs and runtime analysis. I don't kid myself to think that students are regularly going to use proofs to prove their programs correct, though perhaps on a rare occasion they will help you to debug in a much better way than "let me just haphazardly change stuff until my test cases work." The same sorts of attitude could be taken with lots of studies. Calculus...okay. How often will you use it? For many, not often, but it is just so freaking brilliant anyway. So here? We learn the tools. Maybe some of you will use them, maybe some of you won't but these aren't the type of tools that most just learn on their own. We won't use them all semester, but it will help you to understand the book's arguments that its algorithms are correct. That is, if we understand how to use the tools on simple cases, and then the book has a complex use of that tool for a more complex algorithm, we can understand what is being done. Even if you don't want to follow the book step by step, you can look at the big picture to say "Right, here they are proving this section works by loop invariant. I could follow that if I really wanted to spend the time, but just understanding the technique they are using, I know it isn't magical, but I can just skim it right now to see what they are doing, big picture, without worrying about every single line." If you keep at it longer? Then maybe sometime you will want to check out more details, or even do your own for the future, 2023 "Sbabo's Algorithm".
I am confused about the loop invariant which is evaluated before the tmp increment in the first iteration (18:27). So, according to the loop invariant in the first iteration before tmp is incremented, the summation of tmpi=1 goes from j=1 to i=1-1=0?
Shouldn' it be tmp = the sum from j =1 to i-1 of A[j] ? Then the invariant also holds before the first iteration when i = 1(tmp == the sum from j =1 to 0 of A[j] == 0) and after the first iteration when i = 2 (tmp == 0 + the sum from j =1 to 1 of A[j] == A[1]) That would be the beginning of the induction. After that we can state that the invariants holds for all i = i'
do you know loop invariant for this program function increment(y) comment Return y + 1, where y in N x := 0; c:= 1; d:= 1; while (y > 0) V (c > 0) do a :=y mod 2; if a XOR c then x=x+d; c:= a AND c; d:= 2d; y := [y/2] : return(x)
How do you know if an algorithm correctly solves a problem? Program proofs show that the logic of a program does, in fact, solve the problem the program is supposed to solve. They give a rigorous framework to argue program correctness.
13:57
I can relate...
Oof.
Thank you so much David Taylor. You have always had my back since last semester and this semester too!
When the chapter 2.1-2 problem of CLRS book puzzled me; This video helped me to understand Loop Invariants a lot better.
Amazing!! Love the explanation
I am ignorant and stupid and probably missing the significance this technique offers for later more complicated algorithms, but I cant help but just keep thinking to myself, "....... yeah. Okay?" Still took notes though!!!
We spend the first few weeks of class dealing with the tools of program analysis, for correctness proofs and runtime analysis. I don't kid myself to think that students are regularly going to use proofs to prove their programs correct, though perhaps on a rare occasion they will help you to debug in a much better way than "let me just haphazardly change stuff until my test cases work."
The same sorts of attitude could be taken with lots of studies. Calculus...okay. How often will you use it? For many, not often, but it is just so freaking brilliant anyway.
So here? We learn the tools. Maybe some of you will use them, maybe some of you won't but these aren't the type of tools that most just learn on their own. We won't use them all semester, but it will help you to understand the book's arguments that its algorithms are correct. That is, if we understand how to use the tools on simple cases, and then the book has a complex use of that tool for a more complex algorithm, we can understand what is being done. Even if you don't want to follow the book step by step, you can look at the big picture to say "Right, here they are proving this section works by loop invariant. I could follow that if I really wanted to spend the time, but just understanding the technique they are using, I know it isn't magical, but I can just skim it right now to see what they are doing, big picture, without worrying about every single line." If you keep at it longer? Then maybe sometime you will want to check out more details, or even do your own for the future, 2023 "Sbabo's Algorithm".
Thank you so much this helped me understand a little bit more about invariants
I am confused about the loop invariant which is evaluated before the tmp increment in the first iteration (18:27). So, according to the loop invariant in the first iteration before tmp is incremented, the summation of tmpi=1 goes from j=1 to i=1-1=0?
Wow, this is an excellent video! Thank you!
Thank you Sir David!
I still don't get it :'(
You are awesome. Thanks.
Shouldn' it be tmp = the sum from j =1 to i-1 of A[j] ?
Then the invariant also holds before the first iteration when i = 1(tmp == the sum from j =1 to 0 of A[j] == 0) and after the first iteration when i = 2 (tmp == 0 + the sum from j =1 to 1 of A[j] == A[1])
That would be the beginning of the induction.
After that we can state that the invariants holds for all i = i'
this guy is amazing and funny.
Thank you, sir. Is it bad that I takes me nearly an hour to watch the 20 minutes long video?
If you understood everything in the video, that sounds reasonable.
Great vid!
At 7:25 where did j come from? Shouldn't it be A[i]?
tmp is the sum of many values. in that comment, j is the dummy variable: tmp is the sum of all A[j] values, where j has the values 1, 2, 3, ... , i.
Algorithms with Attitude ohhh i see. Thanks.
Lol, you are definitely not pedagogical minded. but i did learn something
thanks man
do you know loop invariant for this program
function increment(y)
comment Return y + 1, where y in N
x := 0; c:= 1; d:= 1;
while (y > 0) V (c > 0) do
a :=y mod 2;
if a XOR c then x=x+d;
c:= a AND c;
d:= 2d; y := [y/2] :
return(x)
What is the Objective proofs?
How do you know if an algorithm correctly solves a problem? Program proofs show that the logic of a program does, in fact, solve the problem the program is supposed to solve. They give a rigorous framework to argue program correctness.
ow = otherwise...
"ow tmp == x"?
Ow = otherwise
This guy looks familiar...