12. Searching and Sorting
2024 ж. 22 Мам.
173 184 Рет қаралды
MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
View the complete course: ocw.mit.edu/6-0001F16
Instructor: Prof. Eric Grimson
In this lecture, Prof. Grimson explains basic search and sort algorithms, including linear search, bisection search, bubble sort, selection sort, and merge sort.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
This guy was the chancellor at MIT and yet teaches such basic concepts with sincerity and humility. Meanwhile most professors just brush over these topics assuming the students can learn it on their own. Massive respect !
Exactly! The less knowledgeable the more arrogant
42:12 merge isn’t logn iterations its at least n iterations and at most 2n iterations. You can see at 39:49 that number of prints(iterations) isn’t logn. 37:32 we aren’t cutting down the problem in half, it’s a tree 40:33. It’s logn levels of iterations(not iterations themselves) where iterations at each level together have O(n) complexity(cost of each step(iteration) is O(n) but turns out that cost of steps at same level of a tree is also O(n) 41:24. He just mixes levels with steps 42:04 Normally what we do is we multiply number of steps(O(n->2n)) to their complexity(O(n)) but in this case we use the fact that at each LEVEL of a tree sum of conplexity of steps is O(n). So number of LEVELS in a tree (O(logn)) multipled with each level’s complexity(O(n)) = O(nlogn)
@@JH-ux1re Perfectly explains his sentiments around the political divide.
@@JH-ux1re😢😊😊
I've watched all the 12 lectures during corona time, I think professor Eric deserved a better audience, his jokes are really good and keep your attention through the course. Thanks MIT !!
same here
same game (c) Prof. Grimson
Can u share the playlist link
@@kannammapoona8064 I'm late but it's /playlist?list=PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA
I do agree
*My takeaways:* 1. Search algorithm 2:49 2. Sorting a list is also linear complexity 8:09, but when we search for something, we often search many times, therefore the cost of sorting could be balanced 9:37 3. Bogo sort (unbounded complexity) 11:00 4. Bubble sort (quadratic complexity) 12:48 5. Selection sort (quadratic complexity) 18:20 6. Merge sort (log-linear complexity) 26:20, and why it is efficient 32:55, it is the best we can have (considering worst cases not average cases)
Lei Xun thanks
Thanks for the handy time stamps.
For someone watching this. Make sure you do the problem sets. These classes mean nothing without them. It has been a great experience watching all the videos
It has been an amazing learning experience to watch those 12 MIT lectures, I am really thankful to the institution for making all this avaiable to everyone, It's been really helpful. Incredible teachers and great lectures, already looking forward for the next course I will certainly "attend" hehe cheers from a brazillian comp science undergrad
Thank you MIT, I really enjoyed this class.
I'm so grateful for MIT and everyone who helps support OCW. This course was an incredible experience and i can't believe I just did it from Argentina, during an economic crisis. Thank you!!!
One of my biggest dream was studying at MIT, I was pretty optimistic about that till I was like 16yo when I realise it is impossible, bcs I live in central Europe and I also needed to pass some difficult times so I didn't tryhard learning as much as I wanted to. These courses are making my dream partly realised. I'm so grateful for that, thank you
garbge
I’m in awe such incredible lectures are available free of charge on the internet. This far exceeded the quality of any CS course I’ve taken to date.
You did in one lecture, what my shitty lecturer tried to do in a week. Very good, simple and accurate.
by far the most amazing course I've taken, really thankful to you guys for taking the time and providing this
Thank you very much for this free resource. I've memorized all the algorithms presented after running into what I would consider a severe mental block in trying to conceptualize them in my mind before memorizing them. I only share in case anyone else is struggling with trying to deeply understand the content, my suggestion is to first memorize the algorithms, type them out a few hundred times, line by line, through memory, then the concepts will solidify in your mind and you can start to adapt them to other facets of programming. I think we'd all like to pretend we're super-genius's that "get it" on the first go-round, but, at least in my case, it just doesn't work that way.
Thank You MIT-OCW from bottom of my heart.... Thank You for your honest service. I really enjoyed this journey with both professors. THANK YOU :)
Thanks MIT for producing such great content and making it freely available. This is the third MIT course that I have finished.
THANKS MIT, ALL THE PROFESSORS AND MIT OCW TEAM FOR SHARING SUCH AMAZING KNOWLEDGE
This was amazing. Thank you professor for making me understand these concepts so easily. I’ve been trying to understand these concepts for so many years and now I feel like I truly get it. A gifted teacher and thanks MIT for providing this!
Those lectures are a a great chunk of knowledge I needed. I really liked the way everything is explaned. Thanks MIT
These guys are great!! I'm now accepting donations to buy Ana and Prof. Grimson a second pair of clothes.
They didn't record these in 1 day?
It looks like they recorded these videos in one day.
@@mvisperas so the students are actors?
@@kneerelief577 It means all the videos were shot in one day. Thus, their clothes appear to be the same. In game shows like Jeopardy, the host and the contestants bring different clothes so it appears the next show is actually the next day. The MIT videos are aimed at teaching, not vanity.
In the merge() function (35:14), if you change the first line of the for while loop to "if left[i]
Thank you Dr. Ana Bell and Prof. Grimson for the amazing lectures and all involved with OpenCourseWare for this course!
It has been great to follow these lectures. Thanks MIT and ocw
Thank you Prof Eric and MIT team for these wonderful lectures !
Thank you MIT, even though I'm not attending your institute and not paying you any fees, I'm still able to learn from (atleast the so called/ supposedly) the best profs! ❤✌🇮🇳🇮🇳🇮🇳
This the best ever cs course I have ever seen on youtube Thank you so much MIT you helped a lot
Thank you! hopefully the education in Brazil will get better because of your wonderful free courses. God Bless the whole world and you all.
That joke at the end was gold lmao, Prof. Grimson has a wonderful sense of humor
For folks struggling with how recursion code runs, the animation at 40:05 shows step by step what happens for the recursive merge sort code. Study it together with the code, and hope you get a clearer picture of recursion.
Thanks for your efforts that made such gems available
I am addicted to Dr. Grimson’s lectures
professor Eric has been writing recursive solutions the whole course, so this time I spent 3 hours writing a recursive merge sort to find out it wasn't necessary to do it recursively,
Thank you for these lectures! Very helpful for a highschool student interested in computer science.
amazing lecture! I am so thankful this is available to us!
Thank you MIT u guys are doing a great job ... This video made my learning easy in lockdown 🙏🙏
what an absolutely fantastic lecturer
Selection sort is like the opposite of bubble. In bubble after every loop we find the maximum one and put it at the end, in selection sort we just find minimum after each loop. If it was c++ we could’ve written len(L)-j for range of j in 15:07
The proffessor's presentation is poetry 😎
Amazing lectures! Thanks OCW. Also, what should be the next course that I should take after this? (considering I want to get good at the use of data structures and algorithms)
Thank you MIT and thank you Prof. Grimson!
more like geller
love this lecture, very interesting!! thank you so much for the videos, now... to give all of this some good use =P
great explanations!
a very impressive lesson.
How is this only 125k views and a guy talking about pokemon cards has over 3 million views? Can't really comprehend how this amazing lecture is posted for free on youtube and ppl are not watching it (or at least as much as it should be watched )
Thank you MIT!
thanks a lot.Very interesting and livefull lections for self education
Thank you MIT
thank you ,mit
I really liked your sense of humor
Thank you professor for teachings
Much thanks to OCW
Thank you MIT.
Thank you so much sir and ma'am!!
Best professor ever!!!
Very informative, thank you.
Made My Life! Thanks Sensei!
love this dude
"And we deliberately admit students of different heights so John can do this demo" lol, love these lectures!
A BIG THANKS TO MIT.
i love this dude man
thanks mit!!!
Great lectures and great lecturers. And I liked the jokes :) Thank you.
2:53 linear search (mentioned) is not the same as sequential search (what is meant here)
selection sort around 18:00
I wish I was in this lecture as bubble sort has been given a bad wrap, where: "for j in range(1, len(L)):" should be "for j in range(1, unsort_len(L)):" This would be a simple extension to the use of "swap" as "new_len". This saving was even observed in the lecture. Also, it would have made a very informative demonstration of quick_sort out on the steps on such a nice day. Merge sort also requires many storage allocations, which can be expensive and is another cost to consider with "compares", "swaps" and "allocates". Those steps would have been a great location for any divide and conquer sort, eg shell, merge or quick, and especially to demonstrate their difference.
Thank you very much. From Vietnam ^^
I think bubble sort print statement should be right after the if statement
what a closure!
Thank you so much.
wooow so fantastic!!!
Thank you !!! it's great
This is awesome
Thank you
Thank you very much! 💖🙂
The classes are very good. I wish there were more classes to explain the algorithms in detail
there is one more MIT OCW course called introduction to algorithms
See ocw.mit.edu/courses/find-by-topic/#cat=engineering&subcat=computerscience&spec=algorithmsanddatastructures to see what we have for algorithms. Best wishes on your studies!
Thank you MIT wonderful lectures. @ Eric awful jocks ;)
day during quarantine .sounds good
that was fantastic :)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
He's actually quite funny
I feel like Prof. Grimson's true calling was to be a comedian. The dude is really funny!
34:42
42:12 merge isn’t logn iterations its at least n iterations and at most 2n iterations. You can see at 39:49 that number of prints(iterations) isn’t logn. 37:32 we aren’t cutting down the problem in half, it’s a tree 40:33. It’s logn levels of iterations(not iterations themselves) where iterations at each level together have O(n) complexity(cost of each step(iteration) is O(n) but turns out that cost of steps at same level of a tree is also O(n) 41:24. He just mixes levels with steps 42:04 Normally what we do is we multiply number of steps(O(n->2n)) to their complexity(O(n)) but in this case we use the fact that at each LEVEL of a tree sum of conplexity of steps is O(n). So number of LEVELS in a tree (O(logn)) multipled with each level’s complexity(O(n)) = O(nlogn)
This is amassing lecture . Please can you say where the first 11 lectures .
Here's the playlist for the series: kzhead.info/channel/PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA.html. For more info, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-0001F16. Best wishes on your studies!
15:25 better turn the meaning of the swap flag upside down ... if you swap things set swap to True
For anyone watching this as a beginner and want to learn more computer science courses, here is the list of free courses through which you can learn sequentially - github.com/ossu/computer-science
Very useful. Thanks!
“And we deliberately admit students of different height so we can do this demo”Hilarious 😂. I really appreciate your jokes, Professor !
are there lectures after this.?
No more lectures after this one. See the course on MIT OpenCourseWare for more details at ocw.mit.edu/6-0001F16.
there is a follow up course which is 6.0002
why was my college not showing this kind of example
the playlist link please !!!!
kzhead.info/channel/PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA.html
0:00:00 Review 0:02:54 0:04:00 0:06:10 0:08:26 Sorting will do you good 0:12:32 BOGO sort 0:13:58 Bubble sort 0:15:58 0:18:25 selection sort 0:20:00 0:22:02 0:23:50 0:26:00 0:27:38 Merge sort 0:30:00 0:32:26 0:34:28 0:36:26 0:38:12 0:40:02 0:42:00 0:44:00 0:46:10 What do computer scientist do 0:47:06
Is it required at MIT that profs wear the same outfit for every lecture, or is that just a consequence of filming for the video series?
Please provide algorithms course for c++
go to website
i gave applause without him telling
is there any final exam for this course (6.001) ?
Looking at course on MIT OpenCourseWare ( ocw.mit.edu/6-0001F16 ), it doesn't look like it. We do know that the equivalent of 6.001 will be starting on EdX in late August (26th). It will have a final exam (which can even be graded if you sign up for a certificate): www.edx.org/course/introduction-to-computer-science-and-programming-7. There is an older version that has an exam (with solution) but it is based on an earlier version of Python and might not be as helpful: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-3/final-exam/
Raymond Hettinger would have a bird if he saw the abomination at 3:58
All classes included?
Yes. For more info and materials, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-0001F16. Best wishes on your studies!
Great though difficult ~~
For explanation + implementation + Key points List and short notes on all sorting algorithms with doubt support : kzhead.info/sun/mNmFXaijaYKGmq8/bejne.html All English Videos have been uploaded by 25th June 2020 and from now hindi series will start.
34:30 what programming language is this ??
Python (v3.5). For more information and materials, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-0001F16. Best wishes on your studies!
👏👏👏👏
I really hope he is my cs professor, such an adorable person
20:00