3. Sets and Sorting
ฝัง
- เผยแพร่เมื่อ 10 ก.พ. 2025
- MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Justin Solomon
View the complete course: ocw.mit.edu/6-...
TH-cam Playlist: • MIT 6.006 Introduction...
Stored sets sorted by key allows for faster searching. This lecture covers how to construct a sorted array efficiently and the types of sorts.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Support OCW at ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s TH-cam and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/co....
![จากรุ่นใหญ่สุดรวยในเกม FIVEM สู่การติดคุกแก๊งแตกในชีวิตจริง [สรุปแก๊งOREO]](http://i.ytimg.com/vi/Vjj8EX4qpiU/mqdefault.jpg)
This dude is simultaneously the most excited and patient professor in the world. It's awesome.
0:00 intro
3:13 set interface
8:55 unsorted array
14:05 sorted array
18:48 sorting vocab
21:28 purmutation sort
26:04 selection sort
40:52 insertion sort (skipped)
41:25 merge sort
deserved a like.
PACHEL -- Sioux / Rushan - SWDEN... Hence; never India. Sw i.e. Sioux.
All hail MIT for their selfless determination to contribute to our society.. for free!
He didn’t stop smilling the whole lecture 😳
He seems so happy :) We need more such professors!
That's good. That means he loves what he does.
Yeah... That's why I was so calmed when. I watched this video
哈哈哈哈you’re right
He depressed.
The 3 instructors are just great. Good class as well.
Justin is a fantastic lecturer.
Love that MIT is providing this to us for free. Thank you! The lecturer is passionate and knows his stuff, but the previous lecturer from Day 2 was far superior. The students would probably benefit more if he taught the entire course.
yeah, previous one is much better, and much more comforting
This lecturer's math is better - more rigorous.
I love his enthusiasm but also love the guy from day 2!
That guy is a genius.
Erik Demaine is simply the best teacher! And Srini Devadas from the previous version of this course, while slightly below Erik at teaching, is still much better than both of the other lecturers.
So far my favorite lecturer. Really engaging and easy to follow
Entire 6.006 course recordings makes me wanna go back to university and study cs again
At minute 41.07, by mistake professor mentions Insertion sort runs in O(n) time, it should have been O(n^2). I know it was human mistake, can happen with anyone.
Great lecture Justin, you have a great vibe about you. The quiet students in the class makes it all funnier to me. Feels bad Justin haha
Thanks for the update. Really helpful resource
This is really deep, like deep learning deep - Justin Solomon
I was slightly confused at ~ 13:30: Inserting a new element (at the end) should take Theta(1) amortized time (and not O(n) amortized time, as the instructor suggested). However, since we have to search through the entire dyn. array on every insert to check if an element with that key already exists, the insert operation runs in O(n).
Agree with you.
@Lucas keep in mind the professor's response is relative to the argument he gave earlier in the lesson of traversing, one by one, through an array of size n to find(k), and that would take order n time.
Very helpful thanks mit love from india 🔥🔥
Watching it online it feels like why isn't anyone answering what the Professor asks, but even if I would have been sitting in the class, I would not have answered thinking someone else would. But that made it hard for the Professor.
what is meant by the remark at 9:20 about the previous two lectures using 'metaphorical arrays'? is this refering to the 'memory allocation model' described by Demaine in L02?
The way that nobody answers his questions makes me sad, honestly. He's doing his best to give you some knowledge and you can't even say if 72 larger than 8.
why is he asking 3rd grade questions though, who's going to raise their hand for that in uni
Yes, that’s true that this teacher is not able to share his ideas throughout his lectures and can’t able to connect with them
you are not counting your students here in youtube around the world. Greetings from Argentina. Sorry for my english , i'm not very good with the sintax
Very easy to understand
he really wasn't kidding about the serial killer handwriting
Goat lecturer
thank you ~
5:16 set is a container
30:00
I feel bad when the students are not responding, lol 😅
It's because he wasn't doing a good job engaging the students and having them follow his thought progression, so many had tuned out and/or weren't understanding him. It didn't help that he basically dismissed any questions they had so that he could cram as much material as possible into the time he was allotted.
I like his vibe
MIT should limit the number of instructors taking a course. Like 3 proffs for a DSA course, it does affect the synchronization between the students n the proffs. Btw, loved Erik and Jason, Justin is just trying to cover too many stuffs in too less time.
agree
thanks mit
I didn't know James Murray taught at MIT!
That's a good joke :)
thank you mit
Thank you! Great content!
Very nice ocw!
Hence; itt doesn't collect - because; you load out!
Why do we always seem to go backwards(?); why not just push to the array and when the length reaches the size we stop?
Is it's because it's easier to make inductions on where we anyway need(?) to be explicit about the index and don't want to make assumptions about the underlying datastructure?
Great!
Thanks MIT
All the teachers are good
can i watch these lectures and try to write code in C++ instead of Python? I mean I can but is it a good idea to learn both C++ and Algorithms, and is it feasible?
You can but we would advise you look for a course that is in C++ and save yourself some extra effort. If you still want to do this course, it is possible. The logic and the algorithms will work for almost any programming language. Things to look out for:
- C++ is statically typed vs Python which is dynamically typed.
- Python Functions do not have restrictions on the type of the type of its return value. C++ does have restrictions. C++ can only return a type of value which is already defined.
- Python variable scope is more flexible than C++. Look out for issues of scope in things like loops.
Best wishes on your studies!
37:34から
I'm confused about the merge sort code. Does it not seem to have added the i term of L/the j term of R into the set A? It only made the A[b-1] = L[j-1] or R[j-1], but there's no statement to assign L[i] or R[j] to the A[b]. This is my confusion, maybe it's fault.
why are we doing comparison/merges in reverse order for selection and merge sort? what's the point?
sorry but can someone tell me in 25:00 why does the loop starts from 1 not 0 ?
He has chosen to write pseudocode with 1-Based Indexing, in which you access the first element of the array like this: array[1]. If you are used to 0-Based Indexing, the loop would be for i from 0 to length(array) - 2. Note the use of -2 rather than -1, we don't need to visit the last element, as there wouldn't be anything to compare it with.
Awesome
first thanks for amazing course but there something wrong here when prof explained selection sort i reconized it doesn't a selection sort ti's a abubble sort please correct me if am wrong
Nice lecture. I wonder why he doesn't use the number 8 in any of his examples. haha
Start watching at 2x speed.
Obviously
Oh, I thought I have open 2x speed in the beginning!
This guy said hella
question: what does Eric post on Facebook?
could anyone help me with the recitation 2 followed by exercise where Set from Sequence has to be built? I am not getting the part self.S.get_at(i).key inside the insert method. What kinds of items are we feeding to build the sequence seq() and later set from seq? Are we making custom item object with key attribute as intrinsic property? Please help me with this.
could you plz reply me with links of (recitation video ) of this course
Imagine paying to go to MIT and the professors can’t be bothered to write properly/legibly
Done!!
Anyone else get confused by the mathematical part?
Check discrete math, which is essential for learning algorithms.
not like he reaaly needs it@@seyitilkturk
Are Lec pdf is avilable ?
Yes, lecture notes and other course materials are available on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!
dude wastes so much time with rhetorical 3rd grade questions and decent jokes, but doesn't have time for student questions. he seems like a really sweet guy, but the time economy is terrible.
Keep in mind, courses like this have recitation sessions where students can ask questions for clarification.
24:53 Omega question
To answer it you gave to stop listening to wanna bes and go bVk to source math
Omega is a probability space
a set of all possible outcomes
Set of all possible moves which he chose from his algorithm
From comments I'd say this is only mediocre
Stop whatever you're doing only when you're ready study probability theory for phds
God wish Caltech picks me up for a professor Substitute for once
Sorry MIT but my heart is in California
Nope same symbol but different meaning. They're talking about algorithm complexity / big-O notation so it's not the same as the probability one
You clearly don't understand what the Omega notation is in Algorithms.
who else is preparing for job interview
this class is so non interactive
Wow, I understood this, I even wrote code that did this three years ago, yet my applications which included samples of the code to Google and Amazon went unanswered and I never got into MIT. It is almost like they circumvented the security of my system.
watching these lectures, the moment you think you're perhaps understanding the class better than the folks sitting there at freaking MIT, actually you're right, you're actually smart if you're doing this. these schools selection process is as useless as Guinness world record, not enough participate at the right time at the right age, it's like first come first serve
First come first serve basis? I wanna research more on this now. Your comment helped me realize all this. Thank you!
But how can you know that you understand the content better than the students? Because they dont speak up? Have you considered the other factors involved in that other than ignorance?
Well, you are way over your head there, buddy! We are all smart, I will give you that, however, watch an TH-cam video in the comfort of you home is a whole different experience than actually being present in class along with 200 students.
@@davyroger3773 You don't get it bro. This guy is smarter than all these MIT students because he can bark that 9 is a larger number than 7 on command.
I'm not sure if that student really know what he doing, great subject with worst explanation, Thank you for wasting my time.
my comment is the 47th comment
First😂
/mk Xtt' green / black cammoflage 20deg fnt 100pts tempd DllCHaa'(Delta) 4''in x 4''in Att' center 3''in diamsz dbl speres //system.out.ArroW' HeaDD'.prntln("DllCHaa' SDR OrrbTTsz' L'''x system) /