Merge Sort - Proof of correctness using loop invariance

Подписаться 11 тыс.

Просмотров 16 тыс.

50% 1

In this video, we discuss the correctness of Merge Sort using the concept of loop invariance
If you want to obtain a certification and a Algorithms Foundations badge from the State University of New York Binghamton based on the videos in this channel, please visit the link. For obtaining the certification, you will need to pass a multiple choice final exam based on these videos. The course also contains self-assessment quizzes to help you prepare for the finals and for obtaining the certificate.
Introduction to Algorithms: www.binghamton...
Advanced Algorithms: www.binghamton...
This channel is part of CSEdu4All, an educational initiative that aims to make computer science education accessible to all! We believe that everyone has the right to good education, and geographical and political boundaries should not be a barrier to obtaining knowledge and information. We hope that you will join and support us in this endeavor!
---------
Help us spread computer science knowledge to everyone around the world!
Please support the channel and CSEdu4All by hitting "LIKE" and the "SUBSCRIBE" button. Your support encourages us to create more accessible computer science educational content.
Patreon: / csedu4all
GoFundMe: www.gofundme.c...
---------
Find more interesting courses and videos in our website
Website: csedu4all.org/
---------
Find and Connect with us on Social Media:
Facebook: / csedu4all
Twitter: / seetharamanand
LinkedIn: / anand-seetharam-5444775a

Опубликовано:

28 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 11

@j.p.8595 4 года назад

Thank you for the video. Just a question, why is it k = r+1 and not k = r in the termination step?

@anandseetharam 4 года назад

The termination occurs when k is incremented, becomes r+1 and thus cannot enter the loop (i.e., it checks the condition in the for loop).

@GEhehloopf 3 года назад

In 6:05 when defining loop invariant, why is it A[p...k-1] and not A[p...k]? In the maintenance step, why is it A[p...k] contains k-p+1 smallest elements? Why do we need the extra "+1" in k-p+1, why isn't it just k-p? Thank you again for the informative video!

@anandseetharam 3 года назад

When you are looking at particular value of 'k' (i.e., the loop is in the kth iteration), you are considering the elements in the array till 'k-1'. At termination, 'k' will be become 'k + 1'( this is the condition that causes the 'for' loop to terminate) and therefore, we end up considering the elements from A [p.....k]. Hope this helps.