3. Sets and Sorting

Рет қаралды 155,139

Күн бұрын

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Justin Solomon
View the complete course: ocw.mit.edu/6-006S20
KZfaq 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 KZfaq 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/comments.

Пікірлер: 88

@adamhaney9447 2 жыл бұрын

This dude is simultaneously the most excited and patient professor in the world. It's awesome.

@ParthPatel-vj2zv 2 жыл бұрын

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

@gunjanshinde396 2 жыл бұрын

deserved a like.

@paulhetherington3854 Жыл бұрын

PACHEL -- Sioux / Rushan - SWDEN... Hence; never India. Sw i.e. Sioux.

@bieldozap 2 жыл бұрын

He didn’t stop smilling the whole lecture 😳

@sam_s3344 2 жыл бұрын

He seems so happy :) We need more such professors!

@vectoralphaSec 2 жыл бұрын

That's good. That means he loves what he does.

@erickgomez7775 Жыл бұрын

Yeah... That's why I was so calmed when. I watched this video

@likeabed Жыл бұрын

哈哈哈哈you’re right

@kyoungjunhan1098 2 жыл бұрын

All hail MIT for their selfless determination to contribute to our society.. for free!

@textinface1 Жыл бұрын

So far my favorite lecturer. Really engaging and easy to follow

@sweeteshsingh4054 2 жыл бұрын

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.

@ram_bam 2 жыл бұрын

Justin is a fantastic lecturer.

@yevhendubinin 7 ай бұрын

Entire 6.006 course recordings makes me wanna go back to university and study cs again

@arizavala5297 Жыл бұрын

The 3 instructors are just great. Good class as well.

@JeffreyConcerto 2 жыл бұрын

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.

@xintu8123 2 жыл бұрын

yeah, previous one is much better, and much more comforting

@quanting 2 жыл бұрын

This lecturer's math is better - more rigorous.

@goldibollocks 2 жыл бұрын

I love his enthusiasm but also love the guy from day 2!

@bavidlynx3409 Жыл бұрын

That guy is a genius.

@daydreamed 2 жыл бұрын

Thanks for the update. Really helpful resource

@ZMan-lx6pg 23 күн бұрын

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.

@dn275 2 жыл бұрын

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

@lucifyer4486 2 жыл бұрын

Thank you! Great content!

@fitnesscliffs1602 2 жыл бұрын

why are we doing comparison/merges in reverse order for selection and merge sort? what's the point?

@howardzhu2298 2 жыл бұрын

Very nice ocw!

@Namu400 8 ай бұрын

Very easy to understand

@kenfuliang Жыл бұрын

thank you ~

@surajagarwal3561 2 жыл бұрын

Very helpful thanks mit love from india 🔥🔥

@ted3309 2 жыл бұрын

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.

@jackmiller9829 2 жыл бұрын

thank you mit

@webdevelopmentwithjavascri8020 2 жыл бұрын

Thanks MIT

@Juan-dc6yf Жыл бұрын

Goat lecturer

@lucaswolf9445 2 жыл бұрын

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).

@anhquantranle961 2 жыл бұрын

Agree with you.

@izreeljames7953 2 жыл бұрын

@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.

@shaileshkumpawat6913 Жыл бұрын

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?

@mitocw Жыл бұрын

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!

@ScientistShield01 28 күн бұрын

thanks mit

@nirbhaysingh4360 2 жыл бұрын

I feel bad when the students are not responding, lol 😅

@JeffreyConcerto 2 жыл бұрын

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.

@nanunsaram Жыл бұрын

Great!

@mahmoudadel8313 Жыл бұрын

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

@dipeshshrestha7287 2 жыл бұрын

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.

@FIFA_World_Cup_Live_quatar Жыл бұрын

could you plz reply me with links of (recitation video ) of this course

@pictureus 5 ай бұрын

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?

@srijanshashwat2434 2 жыл бұрын

This is really deep, like deep learning deep - Justin Solomon

@rstark 2 жыл бұрын

Awesome

@reyreyes8659 6 ай бұрын

I didn't know James Murray taught at MIT!

@b088mohdzaid5 11 ай бұрын

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

@CairoQuinn Жыл бұрын

he really wasn't kidding about the serial killer handwriting

@ting9252 Жыл бұрын

question: what does Eric post on Facebook?

@KlanBr1 10 ай бұрын

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

@paulhetherington3854 Жыл бұрын

Hence; itt doesn't collect - because; you load out!

@edmbootcamp6188 2 жыл бұрын

This guy said hella

@kentsang9376 2 жыл бұрын

I like his vibe

@hokkaido1114 Жыл бұрын

37:34から

@abdomostafa9844 2 жыл бұрын

Are Lec pdf is avilable ?

@mitocw 2 жыл бұрын

Yes, lecture notes and other course materials are available on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!

@balletvaria 2 жыл бұрын

All the teachers are good

@rohan30497 Жыл бұрын

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.

@niklasanesen5096 Жыл бұрын

agree

@kevinquiroscanales6240 Жыл бұрын

Nice lecture. I wonder why he doesn't use the number 8 in any of his examples. haha

@ashishbhandari8792 2 жыл бұрын

Done!!

@ganeshanageshappa9341 2 жыл бұрын

Start watching at 2x speed.

@thinkGrey_ 2 жыл бұрын

Obviously

@jianxinhuang2465 2 жыл бұрын

Oh, I thought I have open 2x speed in the beginning!

@krizh289 2 жыл бұрын

Anyone else get confused by the mathematical part?

@seyitilkturk Жыл бұрын

Check discrete math, which is essential for learning algorithms.

@malikaremu2344 5 ай бұрын

not like he reaaly needs it@@seyitilkturk

@skidipap8750 3 ай бұрын

who else is preparing for job interview

@louiss3409 2 жыл бұрын

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.

@karthikKarthik-by6ws 2 жыл бұрын

my comment is the 47th comment

@kevinzebb 10 ай бұрын

Imagine paying to go to MIT and the professors can’t be bothered to write properly/legibly

@akoravani5502 2 жыл бұрын

First😂

@amansagar4948 2 жыл бұрын

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

@sam_s3344 2 жыл бұрын

First come first serve basis? I wanna research more on this now. Your comment helped me realize all this. Thank you!

@davyroger3773 2 жыл бұрын

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?

@Guinhulol Жыл бұрын

Well, you are way over your head there, buddy! We are all smart, I will give you that, however, watch an KZfaq video in the comfort of you home is a whole different experience than actually being present in class along with 200 students.

@alute5532 2 жыл бұрын

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

@undefinedundefined7942 2 жыл бұрын

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

@SwatejTech Жыл бұрын

You clearly don't understand what the Omega notation is in Algorithms.

@malikaremu2344 5 ай бұрын

this class is so non interactive

@alzubismog3891 2 жыл бұрын

I'm not sure if that student really know what he doing, great subject with worst explanation, Thank you for wasting my time.

@paulhetherington3854 Жыл бұрын

/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) /