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

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Jason Ku

Four examples of worked problems on the asymptotic behavior of functions and double-ended sequence operations.

License: Creative Commons BY-NC-SA

[famguy]

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

[The-Funk]

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

[kz_cbble]

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

[hyunkwak]

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

[Michael-urzs]

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.

[DmitryStepanov-mowt]

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

[anuragbhakuni]

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.

[elhoussainbouhyla]

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

[vivaciousmiss]

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.

[SphereofTime]

1:10:37 if you are using non constant space, insantiating some kind of data structure

i think that's interesting to see both professors in the same class, but one waching the lessons of the other one

[suindude]

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.

[vam]

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

[suindude]

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.

[FightAndFunHub]

Loved the way you are teaching Jason Ku

[wingsonthebus]

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

[suindude]

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.

[muhamadsh]

‏‪11:59‬‏

Thats the combinations formula not the permutations i think.

Thanks for the content.

[terasoft-official]

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

[suindude]

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.