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
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.
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
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.
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.
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.
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."
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.
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?
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.
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. th-cam.com/play/PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb.html
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
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.
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!
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.
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)
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.
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 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.
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!
Prerequisites: 6.0001 Introduction to Computer Science and Programming in Python: Basic experience programming in Python 3. 6.042J Mathematics for Computer Science: Basic knowledge of discrete mathematics: set theory, relations and logic, combinatorics, proofs, recursion, number theory, graph theory, and probability. For more info and course materials, visit the course on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!
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!
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.
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.
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.
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.
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
i have the same problem. I am suffering and trying to begin everything again. I hope we will succeed!
okay? but nobody gives a crap that you watched youtube videos. get the degree
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.
00:00 problem 1
23:19 problem 2
36:48 problem 2.1
45:41 problem 3
1:07:40 Problem 4
thanks!
thank you man
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
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.
I think it is automated system
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.
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.
Maybe it is automatic based on facial recognition. For this case we can't really understand.
Agreed. I left the video for this reason alone.
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."
Literally me rn
@@andiuptown1711 us bro
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.
ty
bro!!!! good explanation
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.
For those wondering about the relation in 7:02 a proof is provided in recitation1 exercise 5 (page 6 of 7)
whre can I get the recitation?
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.
The cameraman was most likely someone from the street. He doesn't know his job.
You have so amazing atmosphere of lecture, it is really exciting... I want to go MIT since that...
Mr.Ku's handwriting is great!
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.
i think that's interesting to see both professors in the same class, but one waching the lessons of the other one
Loved the way you are teaching Jason Ku
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.
This playlist is the ultimate resource for every passionate computer science engineer.... 🔥🔥❣❣
This course is going to be legendary as 2011 version 🤓🤓🤓
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?
@@ricsip Did you figure out an answer?
@@conchobar0928Did you figure out an answer?
10:42 aaaaaaaaaä this makes so clear this formula i’ve always found so confusing
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.
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.
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.
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.
10:22 binomial coefficient
Great lecture, except the black board was never in focus of camera, and that made me uncomfortable.
11:59
Thats the combinations formula not the permutations i think.
Thanks for the content.
y=D.delete_first()
D.insert_first(D.delete_last())
D.insert_last(y)
For(i from 1 to k)
D.insert_last(D.delete_first())
Not sure why i clicked on this video, now i know that i know nothing about math
Same. I’m high asf rn trying to understand this
1:10:37 if you are using non constant space, insantiating some kind of data structure
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.
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?
yes using extra pointer
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.
Algorithms is a science, handling a camera is common sense!
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. th-cam.com/play/PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb.html
thank you so much!
Thanks!!!
Think you MIT
His face in the thumbnail reminds me of nevil from icarly lol
Lol
I was literally going to comment that this guy reminds me of nevil lmao
i will tell my kids i was here before 300 views
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
Spoiler: this lecture does make sense.
Such a likeable guy
Title was vague but I was not disappointed. Great explanations here.
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.
So cool
Thank you for this knowledge
Thank you professor.
this helps my further year courses, thank you
Why do I feel like there were about 5 lectures missing between the last lecture and this lecture?
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!
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.
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.
I wish the camera man wouldn't be constantly panning and zooming and let us see the blackboard at all times
Damn, wish I understood 1/4 of this.
try to google keywords from his presentation. there is a lot of better explanations everywhere online
before taking this lectures it's best to learn about discrete maths and linear algebra i think
conscious incompetency > unconscious incompetency
It's so interesting class!!!
Read CLRS along with the lectures, it was helpful for me
where to find CLRS?
Great lecture, but i don't understand problem 3.. can anyone explain it to me
thank you, ocw
thank so much for these vedios
damn this guy is good
Does anyone know, how can we find the videos for Recitation? Thank you.
The recitations aka Problem Sessions are in the TH-cam playlist: th-cam.com/play/PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY.html. Best wishes on your studies!
This Professor gives me serious Michael Reeves vibes
Congrats!
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)
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.
One moment appreciating the Muslims for inventing algorithms.
Khwarizmi was persian and so am I(I know our history well). It has nothing to do with the F***ing Islam.
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
May be you don't have to download and just use wifi?
@@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.
Reminds me of Scipio Prime
Is there any Recitation Video? Like 2011?
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!
@mit open courseware,plzz upload recitation videos also.
can the public get access to the problem sets?
Yes, the problem sets are available. View the course materials on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!
Wow, JUST before Covid
Can someone pls explain line 11 a1 1:23:13? Thanks
why the fuck is camerman filming him instead of what he writes on the table (when he writes)
I teach fitness
8:56 why is f5 slower than f1 ?
Hey guys while watching this video i got really stuck with that math stuff,is there any prerequisite for this ?
Prerequisites:
6.0001 Introduction to Computer Science and Programming in Python: Basic experience programming in Python 3.
6.042J Mathematics for Computer Science: Basic knowledge of discrete mathematics: set theory, relations and logic, combinatorics, proofs, recursion, number theory, graph theory, and probability.
For more info and course materials, visit the course on MIT OpenCourseWare at: ocw.mit.edu/6-006S20. Best wishes on your studies!
Amazing
Love this guy hahaha
Done!!
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?
this guy acted in movies ?
great :D
30:11 Savage
where are the python files for this problem i searched opencourseware i could not find it
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!
The last problem works the same for lists with a size of an odd number?
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.
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.
why (n 3) = θ(n^3)? Can someone explain me this moment please?
On 16:20
n choose 3 = n(n-1)(n-2)/6.
So, n choose 3 is big theta of n cubed
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
I’m asymptotic notation we ignore the smaller terms so we only consider the largest term . In this case it’s n cube
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.
hi guys any one here can tell me why he use theta symbol replace n log(2 pi
n/e)
It's used to explain the time complexity of an algorithm
because its the tight bound of n log(n).
tight bound happens when the O(f) = Ω(f)
45:40
11:18
Python is the worst programming language to learn data structures
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.
0:28
er ist ein Kind ?!!
Er sieht einfach aus wie
Er ist klüger als die Erwachsenen
No entiendo un carajo
Fire the camera man