Loop Invariant Proofs (proofs, part 1)

This is the first part of a lecture on proving the correctness of algorithms (and mathematical proofs as such). In this video we get to know loop invariant proofs by the example of linear search.

I like to talk slowly, so use playback speed of 1.25 for "normal" speed, or even faster.

0:00 Introduction
1:51 Correctness: Better-Linear-Search
5:07 Loop Invariants
6:25 Loop Invariant: Better-Linear-Search

17:11 Alternative Loop Invariant
21:07 Loop Invariants Proofs
26:29 Linear-Search

[sembutininverse]

today i was reading the introduction to algorithms book, or also known as clrs, in the start of this book, i encountered the loop invariant, that wasn't clear to me, your video helped me to understand this topic, thank you, i really enjoyed watching this video, thank you for sharing this great video with us, thank you 🙏🏻

[ziminfan]

Found a gem here! I'm studying binary search recently and have some trouble understanding different kinds of implementations of it. For example, some uses "left = 0, right = nums.len, while (left < right)", some uses "left = 0, right = nums.len - 1， while(left <= right)". Using loop invariant can help me differentiate what the coder was thinking when using different implementations.

[sufiyanadam]

On 19th, I have to give my algorithm exam and I don't know how I came across your channel, but by far this has been my greatest fortune treasure, thank you so much for the quality content that you have provided, I am grateful and I have shared your videos to my other classmates as well.

[ace]

Thank you for this. I was reading "Introduction to Algorithms" book and came accross loop invariants, was confused until I saw this explanation.

[MarcosViniciusBergamo]

Thanks a lot! This video helped me tremendously! Content is pretty good and how it's presented make sense for me, so I'm happy and will spread this channel to my classmates for sure :)

[Gladieth]

Shoutout to the Discrete Mathematics and Its Applications textbook by Rosen. Really helps provide a solid foundation for this lecture. Also, great video.

[zokpls]

Super helpful, awesome explanation. Thank you!

[Deksudo]

I'm bookmarking the playlist for this semester, as the content seems to match perfectly with what we learn. Thank you!!!

[ktg]

You helped me pass my first quiz! Thanks so much

[MrBlazzerBoy]

Goodrich's textbook has a ridiculously vauge paragraph on "loop invariants". Thank you for this video, it really helped me. What textbook for DSA do you suggest?

[jomsantony]

Thank you for the Great lesson, can you come up with a video on ford-fulkerson max flow algorithm and its proof

[kicksomeup]

The second question of the quiz, the correct answer should be B, because A[0:0] is always going to be an empty list, so answer will always be not-found since the loop won't run.

[jbipmni]

how to proof correctness of this algorithm:
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)

[nirbhaykumar]

good job.. Honest advice to have more subscribers: work on your delivery, the content is good

[virajmurab]

I searched loop invariant on chat gpt


it referred me to this vid!