Introduction to Algorithms - Problem Session 1: Asymptotic Behavior of Functions and Double-ended...

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Jason Ku
View the complete course: ocw.mit.edu/6-006S20
KZbin Playlist: • MIT 6.006 Introduction...
Four examples of worked problems on the asymptotic behavior of functions and double-ended sequence operations.
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 KZbin 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.

[@famguy218]

I had undiagnosed ADHD until I was 22 and ruined my college experiences. I was not able to properly learn computer science in college and it heavily affected my ability to strengthen my career. These videos and open courseware is helping me re-learn the material I never properly learned and giving me another chance at learning computer science and how to be a better programmer. I don’t know why these amazing videos and coursework are posted for free, but I can’t thank you enough for it

[@manoloeso2633]

This is incredible! I can attend the best university lectures without spending a penny. I can't believe it!. You are contributing to the development of the whole world. Thank you.

[@The-Funk35]

Me, wanting to revisit algorithms and data structures. Lecture 1: Course introduction, alright makes sense. Lecture 2: Data structures. Alright cool. This is all making sense. I coulda gone to MIT. Lecture 3: Jason, " *math* Does that make sense?" Me: "Absolutely not, I haven't taken a math class in over 10 years."

[@andiuptown1711]

Literally me rn

[@Michael-ur3zs]

I really wish the OCW camera people would stop zooming in and out and not showing the problems as they're discussing. They always seem to put a strong focus on zooming tracking the professors movements as they pace around. Not sure what they think makes that style better when recording a lecture for students.

[@thinkGrey_]

I think it is automated system

[@Christopher_Cole]

I agree. Some people might not know, but the problem set is given in the video description. "View the complete course" is the link, and then the Problem set will be under "Course Features." I've only gotten ten minutes into the video, but I've basically just been looking at the problem set and listening to his input.

[@Christopher_Cole]

Turns out they aren't using the Problem Sets in this video. They are using the practice problems. (Listed on the left hand side of course page) Problem Sessions use Practice Problems, which are meant to help with understanding/solving the Problem Set which is probably harder.

[@ravierkonan1694]

Maybe it is automatic based on facial recognition. For this case we can't really understand.

[@Xaminn]

Agreed. I left the video for this reason alone.

[@kz_cbble9670]

00:00 problem 1 23:19 problem 2 36:48 problem 2.1 45:41 problem 3 1:07:40 Problem 4

[@yorgunkaptaan]

thanks!

[@arketos]

thank you man

[@DmitryStepanov-mo6wt]

You have so amazing atmosphere of lecture, it is really exciting... I want to go MIT since that...

[@LEI8037]

Loved the way you are teaching Jason Ku

[@MegaDonaldification]

for those new to algorithm, this is definitely not fun. If you struggle with pointers, dynamic arrays, proof, and geometric series, including not following or preparing ahead of time, it becomes very difficult to follow.

[@anuragbhakuni3494]

Those who still have doubt on Amortised time:- let take an example of the dynamic array, we usually insert operation in O(1)(constant time) but at the end of the array, we need to take an array (double the size of the present array), copy all element to it and then insert. so this particular operation takes a liner time, but as we doing the insertion many times,, this bad operation(in terms of time) has less effect on the time complexity of the complete insertion process.

[@sarmadsultan7981]

ty

[@vallurudevesh1498]

bro!!!! good explanation

[@alfredwindslow1894]

To provide a more rigorous proof. We can imagine continuously inserting to the array would have the following sequence w.r.t. the number of operations: 1, 1, 2, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 8, … Inserts usually take constant time, however when we fill the array we need to double the size taking linear time. This sequence has a sum such that the sum up to 2^n insertions is ~1+2+4+8+…+2^n Taking the sum of the geometric series we get 2^(n+1) - 1, and dividing by the 2^n sums giving the average sum would be 2 - 1/(2^n). As n gets large, i.e. as we do more and more insertions, we can see that the average time per insertion would approach 2, and therefore be constant time.

[@irispallis]

I wish the camera could stay where it was on the blackboard. I need to understand what the instructor explains about what he drew/wrote, not where he moves or what his facial expression looks like. However, I like the lecture. please consider this for the next records.

[@hyunkwak6569]

For those wondering about the relation in 7:02 a proof is provided in recitation1 exercise 5 (page 6 of 7)

[@sauravpoudel3906]

whre can I get the recitation?

[@supermanwang]

Mr.Ku's handwriting is great!

[@jackmiller9829]

this helps my further year courses, thank you

[@bmatachieve9549]

Thank you professor.

[@datioepicplaystv2145]

Not sure why i clicked on this video, now i know that i know nothing about math

[@floormop6672]

Same. I’m high asf rn trying to understand this

[@leomysky]

So cool Thank you for this knowledge

[@wingsonthebus]

10:42 aaaaaaaaaä this makes so clear this formula i’ve always found so confusing

[@geekyprogrammer4831]

This course is going to be legendary as 2011 version 🤓🤓🤓

[@ricsip]

is the 2011 version and this 2020 version talk about the same topics? Are they more than 90% overlap, so its enough to watch only one of them, or the topics were modified for the 2020 version compared to the 2011 sessions?

[@conchobar0928]

@@ricsip Did you figure out an answer?

[@Leo-io4bq]

​@@conchobar0928Did you figure out an answer?

[@w1d3r75]

Such a likeable guy

[@suindude8149]

The linear sequence generator like any function based on the size of a problem set increment. As suppossing the increase in number of element in a Linked list or Queue,thus increasing the complexity of a case of problem like a Chess problem or the well known Diners Bankers Reader Writers problem in sync.

[@brettpowers2748]

Title was vague but I was not disappointed. Great explanations here.

[@enisten]

Recitation videos are available for the 2011 iteration of the course. I haven't checked, but they may correspond roughly to the unrecorded recitation videos of this iteration. kzbin.info/aero/PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb

[@MS-qh3iz]

thank you so much!

[@kides6537]

Thanks!!!

[@cosmicsans3275]

His face in the thumbnail reminds me of nevil from icarly lol

[@CameronCobb]

Lol

[@Alex-xi3bw]

I was literally going to comment that this guy reminds me of nevil lmao

[@vam8775]

This playlist is the ultimate resource for every passionate computer science engineer.... 🔥🔥❣❣

[@sharingan998]

thank you, ocw

[@muhamadsh4683]

‏‪11:59‬‏ Thats the combinations formula not the permutations i think. Thanks for the content.

[@suindude8149]

Its so simple to find out the first and last position in say t times,then the swaping time is T.Thus,we can finish the problem in the summative.

[@cirilocanganjo7957]

Congrats!

[@bidal2248]

It's so interesting class!!!

[@suindude8149]

so by comparing the growth rate hence the time complexity calculation we can arrange the functions. We can say the limit of the n thus the best and worst case complexities. Thus,we can make comparison.

[@think_n_code]

I like this lecture. There is another approach to reverse a singly linked list (without extra memory space): just pointers, without including the size of the list. I think is easier to understand. Isn't it?

[@ShubhamKumar-ex3nk]

yes using extra pointer

[@pierreollivier1]

you can also use recursion, you return the current node when your next node is equal to NULL, and then you simply assign to your next node->next the address of the current (aka the previous) node. node *list_reverse(node *current, node *next) { if(next == NULL) return (current); list_reverse(next, next->next); next->next = current; return (current); } this is quite efficient, because you itterate the list once and assign also once.

[@suindude8149]

The k-1 and so on gives the same pattern hence that will be true for kth value as well. Thus,we may get another estimation of how the func progress with the increasing size,its theethod of induction.

[@suindude8149]

Linked list has a space complexity problem wrt tge Dynamic array. The excessive space of 2 or double 4 sometimes creates a huge space complexity in Linked list as the size increases.

[@terasoft-official]

Great lecture, except the black board was never in focus of camera, and that made me uncomfortable.

[@CandyLemon36]

This is a remarkable body of work. I read a matching book that was enlightening. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell

[@AviPars]

Amazing

[@edmbootcamp6188]

Love this guy hahaha

[@abdelaziz2788]

i will tell my kids i was here before 300 views

[@kharraz1713]

Great lecture, but i don't understand problem 3.. can anyone explain it to me

[@saigowthambabuamburi6158]

Does anyone know, how can we find the videos for Recitation? Thank you.

[@mitocw]

The recitations aka Problem Sessions are in the KZbin playlist: kzbin.info/aero/PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY. Best wishes on your studies!

[@ashishbhandari8792]

Done!!

[@BAEESCOPE2010]

Algorithms is a science, handling a camera is common sense!

[@sherifatef2906]

Can anyone explain to me how the first element of a data structure gonna be the last element after applying the algorithm on 00:44:00?

[@donovantheprogrammer2989]

Why do I feel like there were about 5 lectures missing between the last lecture and this lecture?

[@mitocw]

According to the course calendar, you should have watched lectures 1 and 2. See the course on MIT OpenCourseWare for more info and materials at: ocw.mit.edu/6-006S20. Best wishes on your studies!

[@platoso]

The course also includes recitations which were not recorded. You can either read the recitation notes (founded under Resource Index) or try watching the recitation vides for the 2011 iteration of this course - hopefully this helps.

[@Karim-nq1be]

If that's the case, I think you should probably have a look at some of the courses of 6.042J Mathematics for Computer Science.

[@risithroy4558]

Can someone pls explain line 11 a1 1:23:13? Thanks

[@Lol..No.]

Damn, wish I understood 1/4 of this.

[@mihuhih2186]

try to google keywords from his presentation. there is a lot of better explanations everywhere online

[@stephan8294]

before taking this lectures it's best to learn about discrete maths and linear algebra i think

[@OhmVibe]

conscious incompetency > unconscious incompetency

[@hellswhite383]

Got the first problem right, second problem has stumped me so far, as I forgot what those compound(I think) numbers mean. Don’t really remember the ! either for that matter, though I think my guess is pretty good.

[@petarkonj8979]

why the fuck is camerman filming him instead of what he writes on the table (when he writes)

[@kamikamen_official]

Is there a reason why we'd prefer a recursive implementation to the iterative solution? In this case I feel like the iterative solution is actually more elegant, isn't it? (Problem 1-2 b)

[@yepstill8773]

Yeah and then on the singly linked list reverse algorithm he used an iterative version instead of the recursive version which is way more intuitive and elegant for that case(in my opinion anyways). Kinda weird.

[@itsdavidalonso]

I wish the camera man wouldn't be constantly panning and zooming and let us see the blackboard at all times

[@jonalderson5571]

Wow, JUST before Covid

[@jayeshwaghmare2989]

Read CLRS along with the lectures, it was helpful for me

[@aasifali9139]

where to find CLRS?

[@user-ib5ml1vz5r]

Spoiler: this lecture does make sense.

[@nikhilsannat5429]

Is there any Recitation Video? Like 2011?

[@mitocw]

There are no recitation videos but there are recitation notes: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes/. Best wishes on your studies!

[@dejidevi3990]

@mit open courseware,plzz upload recitation videos also.

[@stepphenschaf668]

This Professor gives me serious Michael Reeves vibes

[@crylater8200]

can the public get access to the problem sets?

[@mitocw]

Yes, the problem sets are available. View the course materials on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!

[@MegaDonaldification]

First of all, Prof Jason, I appreciate your energy and time you spent pouring your experience on the newbies Docky is not living anything apart from the titles and what he wants in the project or coursework. Some students will leave the class to prepare for it - this is a bad idea. Some will read before hand since they have the scheme of work - the best idea. A few will take down keywords and few notes and probably research it on chatGPT right there and then. In summary, preparing before hand is the best answer to this professor's lecture. Breath and strength wont find their way into you if you don't walk the longsuffering walk of suffering in patience. You must be 2-3 steps ahead in the Introduction to Algorithms textbook if you want to understand, implement, and have excellent grades in this beautiful, inductive lectures in algorithm. To pass this course, you must swim in it first and walk through the questions later. I looked at the course table of content, then realised it is the same material found in Leetcode or Neetcode.

[@p3878]

Reminds me of Scipio Prime

[@shimonbrandsdorfer9427]

The last problem works the same for lists with a size of an odd number?

[@emmafountain2059]

No, but the problem specifies that there are 2n students in line, so we know its an even number. You could slightly modify the approach to make it work with some if else statements but that's kinda just unneeded complexity.

[@MrJesterboi]

No but it only doesn't work because you're flooring n / 2. You would need to decide what you consider the middle element that will be the end of the first unreversed section of the list.

[@whicencer8819]

why (n 3) = θ(n^3)? Can someone explain me this moment please? On 16:20

[@LearnMoreBeWater]

n choose 3 = n(n-1)(n-2)/6. So, n choose 3 is big theta of n cubed

[@brandonwallace8817]

How does he get n+1 n and n-2 over 6 @ 16:05, I get how that will give us n cubed just how he got that from that I don't follow

[@charanreddy2113]

I’m asymptotic notation we ignore the smaller terms so we only consider the largest term . In this case it’s n cube

[@Alex-xi3bw]

It's hard to explain in text, but organic chemistry tutor has a good video on factorials on youtube that explains it well. Basically, n! in the numerator can be re-written as n(n-1)(n-2)(n-3). The (n-3) in numerator and denominator then cancel each other out, leaving you with just n(n-1)(n-2) in the numerator.

[@Pradeeppadmanabanofficial]

where are the python files for this problem i searched opencourseware i could not find it

[@mitocw]

The problem set python files are in the zip files: ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/assignments/. Best wishes on your studies!

[@harshitarawat8941]

45:40

[@prudhvir3ddy]

this guy acted in movies ?

[@howtrue3140]

Great content but you need to reformat the videos to reduce data and space complexity because Data is too expensive this side..there is no way i can afford 941mb to download a 1:26:37 minutes video .. atleast if it was

[@kael7953]

May be you don't have to download and just use wifi?

[@kevinquiroscanales6240]

@@kael7953 I think he only has access to mobile data where he lives, but I would still just recommend donwloding a slightly worse resolution of the video and it works just fine for many of the problems.

[@user-bv3gf2ix6c]

hi guys any one here can tell me why he use theta symbol replace n log(2 pi n/e)

[@Millicx]

It's used to explain the time complexity of an algorithm

[@The_Digamma]

because its the tight bound of n log(n). tight bound happens when the O(f) = Ω(f)

[@manishkasera8584]

30:11 Savage

[@forheuristiclifeksh7836]

0:28

[@Reppintimefitness]

I teach fitness

[@forheuristiclifeksh7836]

11:18

[@IZIKI-399]

One moment appreciating the Muslims for inventing algorithms.

[@FlyingPetal]

Khwarizmi was persian and so am I(I know our history well). It has nothing to do with the F***ing Islam.

[@mhd-em6yt]

er ist ein Kind ?!!

[@raymondwang8334]

Er sieht einfach aus wie

[@melvin4441]

Er ist klüger als die Erwachsenen

[@behrozkarim8588]

Python is the worst programming language to learn data structures

[@doublelol]

True. But this course focuses more on the theoretical concepts behind data structures and algorithms. With the knowledge you gain by completing psets you should easily be able to implement any data structure in any programming language.

[@somebodyoncetoldme1704]

Fire the camera man