1. Algorithms and Computation
Вставка
- Опубліковано 1 тра 2024
- MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Jason Ku
View the complete course: ocw.mit.edu/6-006S20
UA-cam Playlist: • MIT 6.006 Introduction...
The goal of this introductions to algorithms class is to teach you to solve computation problems and communication that your solutions are correct and efficient. Models of computation, data structures, and algorithms are introduced.
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 UA-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/comments.
My semester on university: *Starts.
Me: *Watches completely unrelated lectures from MIT.
Sounds like youre thinking of changing majors 😆
@@randyt700 lol
+1bro , this hits me deep 😂😂
Thanks to Technology. Im in Africa Uganda but I feel like as if Im at MIT. Thank you very much for the lecture.
Are you acquainted with Pasta Sempai?
@@elhermeneutico "But before you leave, do you recognize these things?"
Jk, that's a beautiful comment and is amazing that this knowledge can reach the whole world.
THIS!! im from indonesia we dont exactly have the best education in the world so this channel has been a blessing for me
@UCTPCE7ckUioWlMK1nBThsfg lol that joke you're an a hole but funny af.
love to see this
I took Linear algebra, Algorithms, probability, and signal and systems at MIT. Thanks.
You must be a genius then :-)
I'm not gonna say how lucky you are cuz i can realize how much worked was required to achieve such a thing!
Chop andu
How did you like signal and systems course?
Via Online?
There is a big difference between learning what's going on under the hoods of algorithms, instead of just jumping directly to learn a programming language, it's a really explained architecture course, thanks MIT
I highly admire American intellectuals. Putting out free high quality contents for the rest of the world to learn. Thank you!
There is no way anyone can get bored in lectures like these, such a great professor
but u of t courses easy to get bored
@@jackmiller9829 See dat dare cumpooter? Sheez go'n to uhlauh uss to proagram. At least that's how my family from down there sounds.
lmao he's so unprepared he couldn't express the concept or answer the questions clearly enough. And what is this 1980 style presentation 1/10 precious time wasted on writing and deleting the blackboard.
@@CP-jk3tc Much more engaging than what Princeton provides for free, which was made by the writers of the Algorithms book, so... MIT is doing it better, IMO.
@@CP-jk3tc Beg to differ mate - a bit of a rant, pardon! This method actually results in better processing and retention of the content being taught, by the human brain. Maybe a waste of 1/10 precious time, but those paying top dollar to actually learn there are getting their time and money's worth! For us online ones - it's actually free! Watch at 1.5 the speed and save all you want! 🙂But do not underestimate the power of 1980 method, and dismiss it in favor of modern, but lesser lasting ones! The prof also drew the learners logically into the inductive reasoning and WORD-RAM model, instead of just throwing it out there. Engaging IMO. Must laud the prof. Am already liking these lectures over the 2011 class. However Erik Demaine remains that one constant that defines passion, and is always a treat to watch. What a humble guy, to have earned PhD at just 20 years old, but being so accessible! MIT FTW!
Thanks a lot MIT. What you have done by sharing these resources for free to the whole world is beyond my skill of appreciation. May your institute and its glory grow and prosper!
The professor simplifies everything, Thank you so much for sharing this informative content
The professor is full of passion! Very clear structure, thank you!
Thank you MIT for these uploads. Love the way Ku teaches
I can't believe I'm watching these type of videos for entertainment.
Me too, I don't want to read code so I am watching the course for relaxation!
This prof.'s energy when he teaches is on another level.
This is fantastic I love their energy and enthusiasm which make the lecture fun and interesting
After 10 years of open course finally video quality went from 360p to super high res in 1080p
The quality of the instruction decreased with time, unlike the video quality.
We need 4k
Finally!! I've been asking for this ever since I took course 6. Thank you.
Always wanted to go to MIT, unfortunately I couldn't. Thank you so much MIT for giving us the opportunity to learn from the best from these videos.
I think I am walking in your footsteps too. My chances are slim but I'd still give it a shot.
@@therealb888 definately try. if you can do some olympiads and win a good medal then you have a good chance of joining MIT.
@@therealb888 unfortunately i know one guy who got rejected by MIT accepted to Harvard so it's not the end of the world
Lies again? Serie A Leader
Bro just grab a book and read why do you think being in a different building will change anything
This only video has much more valuable content than any entire Colombian computer science program. Thanks, MIT.
I think the teacher has set a goal on daily steps and tries to accomplish it while teaching. Which is a nice life hack.
Thanks for bringing an updated version of this class back.
thearshblog.blogspot.com/2022/09/beating-youtube-algorithm.html
how to beat UA-cam Algorithm 👆
0:00 intro, goals of the course
2:59 what is an algorithm
11:10 birthday problem
15:15 correctness of an algorithm
25:35 efficiency of an algorithm
36:50 model of computation
42:35 why use data-structures
great
Thanks
Thank u mate
I find this guy hard to follow?
@@gp10020 agree
Introduction and Goals of the Course:
- The goal of this Introduction to Algorithms course is to teach students how to solve computational problems and communicate that their solutions are correct and efficient.
- Beyond just solving problems, the course emphasizes proving correctness, arguing efficiency, and communicating these ideas clearly. Students will do more writing than coding.
- An algorithm is a fixed-size procedure that takes an arbitrary-sized input and produces a correct output.
What is a Problem?:
- A computational problem consists of a set of possible inputs and outputs. The problem specifies a binary relation mapping each input to a set of correct outputs.
- Problems are usually defined using a predicate to check if an output is correct for a given input, not by explicitly listing all input-output pairs.
- The course focuses on general problems that can take arbitrarily large inputs, requiring the algorithm to loop or recurse to process the entire input.
What is an Algorithm?:
- An algorithm is a fixed-size procedure that takes an input of arbitrary size and generates one of the correct outputs specified by the problem.
- If the algorithm generates an output for an input, it must be a correct output according to the problem specification.
- Algorithms are like recipes - a sequence of steps that will return an output for any valid input.
Birthday Problem Algorithm:
- As an example, consider the problem of determining if any pair in a group of people share the same birthday, generalizing to any "birth time" to make matches less likely.
- A proposed algorithm is: Maintain a record of birth times. Interview each person in order. Check if their birth time is already in the record. If so, return the match. If not, add it to the record and continue. If no matches after checking everyone, return no match.
Proving Algorithm Correctness:
- With large inputs, we can't just test an algorithm on all possibilities to argue its correctness. Instead, we use induction.
- The key is finding an inductive hypothesis that can be proven true for a base case and all larger instances.
- For the birthday problem, the inductive hypothesis is: If the first K people contained a match, the algorithm would return a match before interviewing person K+1.
- Base case: Trivially true for K=0.
- Inductive step: Assume true for K. If first K+1 contain a match, either: 1) the match was in the first K and algorithm already returned it, or 2) the match includes person K+1, which the algorithm will find and return when checking against the first K people's records.
- By induction, if a match exists, the algorithm returns it before running out of people to interview. If it interviews everyone without returning a match, then no match exists.
Arguing Algorithm Efficiency:
- An important aspect of an algorithm beyond correctness is its efficiency - how fast does it run and how does that compare to other possible algorithms?
- Measuring actual running time is problematic as it depends on the particular input, the speed of the machine, and other implementation details.
- Instead, we count the number of fundamental operations executed by the algorithm to get an input-size-dependent measure irrespective of machine or implementation.
- The number of operations an algorithm requires as a function of input size n is used to classify it using asymptotic notation:
- Constant time: O(1), runs in bounded time irrespective of n
- Logarithmic time: O(log n)
- Linear: O(n)
- Log-linear: O(n log n)
- Polynomial: O(n^c) for constant c > 1 (e.g. quadratic is c=2)
- Exponential Time: O(2^n), considered "intractable"
- In this class, "efficient" generally means polynomial time, with linear or near-linear time being even better. Exponential is considered inefficient.
Models of Computation:
- To measure efficiency abstractly in terms of fundamental operation counts, we need a model specifying what operations a computer can do in constant time.
- The model used in this class is the Word RAM:
- Assumes a CPU connected to a large random access memory (RAM) consisting of a sequence of bits
- The CPU can read/write a word-sized block of memory in constant time (modern word size is 64 bits)
- The CPU can do integer arithmetic, comparisons, and logical bit operations on a constant number of words in constant time
- The word RAM allows any individual word in memory to be accessed in constant time. However, accessing all n words of an arbitrary-size input requires O(n) operations.
Finally a refresher to a legendary course
God bless
Is there anywhere this course completely uploaded somewhere already? Like from past years, but not too old?
@@quasa0 There is both 2011 and 2008, you can find them linked at this courses page (description)
which one do you think is the best, in terms of quality of instruction? 2008, 2011 or 2020?
@@mickeymacke1780 I would say 2020, but if you want to improve on Algorithms, then problem solving is vital, and also don't forget to checkout problem sets
@@ehza Do we get solutions to the problem sets?
Thank you MIT for these fabulous lectures!
It is very knowledgeable thanks.
I need the way to make a dashboard for a mining activity (trucks, scoop, jumbo, solo, Excavator, Loader....)
Sooo good.
self learning algorism
until you spot that the teacher doesn't know induction xD
I love the sound those massive chalks make on those blackboards. Very pleasant.
I found happiness cause you see people like you who code and the talk about ideas.
MIT is sick. Its way better then my university course and I m not even a native speaker. Kudos to Jason Ku
Thank you MIT for these amazing lectures.
This is an amazing lecture! Thanks for let me revise my algorithm and data structure knowledge after I become an engineer.
high quality knowledge at the palm of our hands , what a time to be alive. thank you MIT.
thank you for these videos, ilook forward to the rest of the videos in this course
MIT, the one school where I can somewhat understand the expensive tuition of private universities. You get the professor like these to teach the students. Luckily for a broke student like me, I can partake in these amazing lectures.
Thank you MIT for sharing this to the public
Thank you MIT for publishing such video lectures
Thank you MIT! Here we go let's learn! I'm a self-taught Developer hoping to improve my algorithm skills.
The explanation on words (in the models of computation section, towards the end of the lecture) was excellent and has enabled me to understand the concept better than any previous explanations I've encountered - thanks! Jason did admit he couldn't spell; I'd suggest it's "arbitrarily-sized" (inputs), not what he wrote on the board 😉
I define a problem as a question pertaining to an unknown variable or function, in the programing sense, but more abstract.
I define a computation as a calculation.
Therefore, I define a computational problem as a question pertaining to a calculation, or, in other words, a question about what algorithm is necessary to find a desired output.
Timely upload, thank you, MIT
this's an amazing lecture. love it professor.
I look forward to hearing more
these lecture series are so amazing! I am so thankful they're available to the public
thearshblog.blogspot.com/2022/09/beating-youtube-algorithm.html
how to beat UA-cam Algorithm 👆
Literally best instructor ever!!
thankyou MIT OCW, for these lectures.
Awesome, we have been waiting for this, thank you. Nairobi Kenya.
2 years back I had the privilege to do an interview with Dr Ku for a high school project. He was wonderful, very warm and down-to-earth. I was honestly shitting bricks cos I was so nervous but his friendliness helped me ease into the whole thing. All around great guy.
Love the enthusiasm, thanks mit
I like to say that an algorithm is a set of instructions that will take you from the beginning to the end in a particular order so long as there are no errors.
It’s a good definition if the algorithm is deterministic.
@@andrewzhang5345 who cares about the defination
@@JUST_C0DE In practice you wont find that many deterministic algorithms.
The teacher is the reason we love the subject.
As a teacher I ve learned to be energetic
thanks to the mit for giving us oppurnity to learn interesting topics thank you
Thank you MIT!
What a time to be alive thanks MIT 🎉
I am Form Bangladesh I liked the lecture very much, Especially Sir's Explanation was very nice
Thanks MIT, watching from Sri Lanka.
I always wanted to study in mit but i don't have money
Now mit is uploading classes that's awesome
Absolutely spot on.
I am fortunate enough to live in an era which I can live in Sri Lanka 🇱🇰 and watch these valuable lessons from MIT
If MIT uploads all the lectures on youtube nobody will be deprived of eduction in this world.
What a blackboard. I love it.
@Barry Allen lol
People don't use blackboards anymore and thus the students knowledge doesn't last forever, the tike of writing taken by teacher and given time to take down the content make student grasp things better rather than using PowerPoint presentation with endless slides and meaningless content🤣
@@aishwaryadharmadhikari7165 Can't tell if you're being sarcastic 😂. Anyway there are probably more objective points that support a white board & power point presentation with an e pen.
Blackboards do have their own charm and feeling in addition to giving more time to the student to digest the information. Not to mention the classic classroom environment.
The best parallel for this is EVs vs ICE vehicles. Gas does have some advantages like range & refill time but they can be achieved in the future by EVs with advancements. Similarly, we should be able to transfer the black board advantages to newer learning technologies through advancements.
I know I over analyse stuff, I'm self aware 😂.
@@therealb888 I totally agree with you, but, I won't change my opinion though 🤣 .
It's been 2 years since the online education program has started in India where students are learning on mobiles and I dont think this has been any benefitable to anyone. Not students nor teachers not the institutions!
Show me results😆😂
@@aishwaryadharmadhikari7165 I totally agree with you as well 😂. Where has been the results right?!. But the answer lies in your comment!. Watching on mobiles with distraction on the same device not to mention the small screen & eye strain. I think the results lack because of improper usage. If you look at IITs/MIT/ any top university, there are slides & these videos in addition to problem sets & notes/study materials that are available online. These online resources are absent in most small colleges in India. Online education is also the preferred way for all working professionals. The nice thing about this is that you get a backup of the resources & can pace yourself. Online resources like this should be a supplement to classroom learning in more Indian colleges.
Out of curiosity what are you studying? It's cool to see more Indians here. Do you have plans for any form of higher education in USA?
Nice to see that Michael Reeves is uploading again. Also I knew he was gonna go some places, but MIT... Congrats
Thanks for MIT, I am Iran and it is tough to come there for studying .it is pleasure to be able to learn via internet.
Because the speaker is always walking around, I think we have to thanks the cameraman, he's really doing well.
You can do that with algorithms. :)
@@AlpGuneysel Oh, I forgot, this is MIT
I believe an algorithm is not a function as functions have predefined output based on a set of sequential operations. It may be made up of multiple functions but Algorithm is more closely related to the technique to derive a function or procedure to find a solution to the problem.
Thanks for the explicit explanation. From Nigeria.
The materials on the website makes me feel like I am actually taking this class.
Perfect start!!!
Ily Jason Ku and MIT
these teachers are amazing ..
Thank you very much for making this fabulous course not only for Harvard students but also for other students.
Do you mean MIT is doing this primarily for Harvard students to catch up with them?! LOL
@@enisten No brother, but I think so sometimes.
The Harvard CS courses seem more concerned with the grandeur of their lecture halls than the depth of the content it self
Thank you very much for the lecture.
the fact that we are able to attend lectures online at one of the most prestigious schools in the country is amazing!
Absolutely, people today are so lucky.
You guys have helped me so much ! I can’t believe this is free! God bless😊 subscribed
Very good teacher, thank you Jason.
thank you for this lecture!
Thanks to these lectures uploaded from 2020 I can watch these from 1994. Thank you so much.
I love this lecture. The teacher is excellent. Claps
Thank you so much MIT
Thank you so much for sharing
The definition of the problem is also the definition for a mathematical function. Highly recommend taking a course of sets, relations and functions, proofs n induction in maths, along with an introductory programming course in C/ C++/Python to learn about arrays, strings, etc
The definition of the problem is a mathematical relation, but it is not necessarily a function since the problem may have many correct outputs for a given input
Beautiful lecture
Information for free! Brilliant:) god bless you educators for such amazing knowledge you’re will to hand out to the world 😊 subscribed
Thanks Sir And MIT Watching From Varanasi INDIA 🇮🇳🇮🇳🙏🙏🙏
Thank u MIT ❣️
ooo! yes my dream is to meet the mit chancellor some day really radical revolutionary institution.
i love MIT
thank you so much for this lecture
Thanks to technology, i can attand mit class from another side of the world😊❤
this guy is in every cameraman's nightmare
Respect to mit thanks 👍🔥🙏
nice work im happy to see it
I don't know why UA-cam recommended this to me, but I stayed for the whole lecture.
What a great professor who blames himself when he receives a wrong answer
Don't need any fee or exam to study at Massachusetts just go n watch it on UA-cam!
⏱Timestamps for this video!
0:00 - Introduction to the Algorithms Course
1:00 - Goals of the Course
3:24 - Understanding Computational Problems
9:38 - Definition of Algorithms
15:41 - Understanding algorithm correctness
26:18 - Measuring algorithm efficiency
33:00 - Understanding Running Time
36:31 - Model of Computation
43:18 - Data Structures
🧙♂✨ Generated with Houdini Chrome extension.
nice course, helped me lot. thanks
Really very fruitfull tutorials on DSA.
Wating for the next video.. tq MIT
Thank you MIT
It's 1 am and I just clicked and now I m Loving it 🤣🤣
right when i need it
Problem Session 1 Video
ua-cam.com/video/IPSaG9RRc-k/v-deo.html
Quiz 1 Review Video
ua-cam.com/video/e98MPnMHLxE/v-deo.html
I always wanna go to MIT. thank you
me watching this to entertain myself (: such a great professor!