1. Course Overview, Interval Scheduling
Vložit
- čas přidán 3. 03. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Srinivas Devadas
In this lecture, Professor Devadas gives an overview of the course and introduces an algorithm for optimal interval scheduling.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Thanks MIT for providing an updated version of your algorithms class. You are truly awesome. You continue to inspire me to learn more.
what do you mean by updated version
@@neuron8186 hey u , why u mocking him
The MIT recommended order for watching this is 6.042J (Mathematics for Computer Science) , then 6.006 (Introduction to Algorithms) and finally 6.046J (Analysis and Design of Algorithms).
Sharat Sachin where did you find recommended order
Thx mate
Thank you so much!!!
Thank you!!!!!!!!!!!!!!! you just save my soul which fcked up by corona virus
Thanks mate. I was looking for this comment. Really helpful
The video quality is truly amazing, and it keeps getting better and better. Thanks MIT, the professors and staffs behind the scene!
Thanks whoever wrote up the subtitles, they really do help to ensure you don't miss out on anything.
thanks MIT i am a poor guy learned alot from you and when i got my future bright i will make donation as i can that time and i would be glad to do more then anyone
Interval Scheduling starts at 17:30
THANK YOU
Here in Egypt, at least till the end of 2011 & to be accurate in the places I teached in CE/CS,
We take most of these topics 6.042 ,6.006, 6.046 between Data structures course (2nd yr) & algorithm design & analysis (3rd yr),
usually we start with parts from knuth "Sorting & Searching" , then a variety of books on Algorithms (I recall Sartaj Sahni as one of them) , then a part from Sara Base "The Hardest Problems"
-We probably end data Structures on B-trees, B+ trees,
-Also, we don't use python, we write Pseudo code in lectures (like 5503 course lectures), and the labs use the main programming language these students study for implementation to emphasize more on it(u see sometimes some colleges prefer to concentrate on implementation and programming skills in the Data Structures course)
-Probabilistic algorithms is a post graduate course
-We address Cryptography in completely different course (Security from Stallings)
-I took FFT very very long time ago as an undergraduate in a half semester Digital Signal Processing course yes connected to Algorithms, I never teached it but I know it is taught in different courses
Coming from the 2011 6.006 course, the cinematography for this lecture should win an Oscar! The multiple camera angles, the 1080p definition....I think I'm about to shed a tear
But for real, great lecture! I'm looking forward to watching the rest of the series. You rock, MIT
A very good series. More contents from CLRS are covered compared to the previous 6046 and 6006 courses.
*_Very big thanks to MIT OCW for helping us with this beautiful course_*
I love everything about MIT, I am very grateful and willing to donate!
Thanks a lot for uploading this, Srini, Erik you rock on .. .
Thanks MIT for providing these amazing course!!!
Thanks a lot for MITOCW, it deeply help me to find the real knowledge. I think MITOCW really save me from the poverty and ignorance. THANK YOU MIT THANK YOU MITOCW
great reinforcement of my current undergrad algorithms class!
+1 I take the classes at my local university for credits, I watch these lectures for knowledge.
Weighted Interval Scheduling starts at 1:02:15
Thank you MIT OCW, and thank you Prof. Devadas.
thanks bhai :)
Thank you MIT for this opencourse, it is very good
Course begins at 4:35.
thanks
Thanks
THANK YOU DOOD
professor devdas is no doubt an excellent professor but the thing that makes him even better is how similar his voice and articulation is to RICK SANCHEZ!!
Thanks you very much, It helps me a lot.
Just finished 6.006, I am here to devour 6.046J
hi where can i find the corresponding reading assignment for the course?
From 480p to 1080p! Wow! Possible it's a good time to upload 4k version of 6.006
Wonderful content. I love the course, the professor and your sharing the knowledge with the world for free.
Interval Scheduling: 17:30, Greedy Algorithm: 25:50, Greedy Interval Scheduling: 27:30, Prove: 42:50
you guys are awesome thanks
I hope I can learn this within a year after I satisfy prerequisites. I will be back!
Why can greedy algorithm solve the interval scheduling problem? Is there any limitation to the type of problems greedy can solve? And how to develop an intuition to guess the best strategy, such as the earliest finish time? on the first sight, the minimum conflict strategy totally makes sense, although one counter example proves its invalid. My other guess is to a strategy which concurrently picks smallest tasks and minimizes time waste (intervals between tasks) .
9:25 Lectures starts here.
Thanks for providing information for free
Are there any plans of making an edX version of this course? (also for 6.006)
I didn't understand a thing, any class that i should watch before this? can someone help me with links?
Thank you MIT for uploading. I might just pass my coding test and get a job thanks to you. Maybe...
I love how we have literally thousands of years of teaching tradition and we still cannot afford ourself a desk that is easy to clean
And chalk
Those of you interested in algorithmic puzzles, check out my new book "Programming for the Puzzled" mitpress.mit.edu/books/programming-puzzled
www.amazon.com/dp/0262534304/
God, I love their big-ass chalks.
Good!! Human.
It'scalled railroad chalk, similar to sidewalk art chalk, usually used for construction and insurance claim investigation.
How about compiling the contents into small quick videos where absolutely necessary things are covered just like those math videos of Gilbert Strang. It will be a great help as a quick refresher.
PS: Great Thanks to MIT for this new and updated HD course
Can someone tell me what are the prerequisites for this course.
ps. I know c and cpp fairly well
The prerequisites are: 6.006 Introduction to Algorithms, 6.042J / 18.062J Mathematics for Computer Science. See the course on MIT OpenCourseWare for more information at: ocw.mit.edu/6-046JS15. Best wishes on your studies!
Bless MIT.
Not able to get the third example of incompatibility in 37:55
Interesting proof. Essentially, the induction step is possible because can be swapped into any optimal solution, and we know there exists a k+1 sized optimal solution in which the last k elements can be found using the greedy algorithm, as k is the maximum amount of intervals that fit in the rest of any k+1 sized optimal solution alongside . (By assumption, the greedy algorithm can find a solution when the maximum size is k). So, as the greedy algorithm always finds , and it always finds the next k intervals when it's possible too, then the greedy algorithm can find a k+1 sized optimal solution, hence the greedy algorithm works.
Why are so many people leaving ?
i think i'm in the wrong course lol. I was looking for the newest one but the intro one must be 6.006
Thank You!
I was looking at 6.006 and 6.046j....can anyone please tell in which course do they teach about asymptotic notaions, how to calculate them?? Even in 6.006 they assume students know how to find it.
6.042J
I didn't understand why k* should be maximum?
im loving it :)
resolutions really tells the time between 6.006 and 6.046...!
prove of choosing ealiest finish time: 42:48
I don't why but i intently started listening to the logistics as well 😂😂.
14:41 deyrrmining graph if it is hamiltonian cycle is difficult
I want a frisbee.
It costs $250K
(I had the same thought)
Hi guys, which version is better to watch this one or the 2011’s?
I was wondering this too, I love the 2011 first chapters
Anyone can tell me which section in the course textbook assigned with each video lecture?
Sorry, there doesn't appear to be a Readings section, but the Calendar lists the topics and the required textbook. ocw.mit.edu/6-046JS15.
Study from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Thk you sir
Hello Sir, I want to learn data structure and algorithm and as I don't have any knowledge about coding or about data structure & algorithm.
I have to start from beginning .So ,this course is suitable for me or I need to have any background knowledge.
Prerequisites:
6.006 Introduction to Algorithms
6.042J / 18.062J Mathematics for Computer Science
See the course on MIT OpenCourseWare for more info at: ocw.mit.edu/6-046JS15. Best wishes on your studies!
Sir, what is the best programming language to understand, implement the data structures and algorithms, analyse and design algorithms.. c/c++/java/c#/python etc???.. please sir answer me.. it will be very helpful.. eagerly waiting for your valuable answer..
I would start with Python. Good luck!
Thank you sir for your reply.. Sir what's the best video resources for learning python in depth.. Please answer me sir..
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-s095-programming-for-the-puzzled-january-iap-2018/index.htm?OCWCourseList&CarouselSm&FeaturedCourse
Thank you sooo much sir.. Lots of love and respect for your Sir from India 🙏🙏🙏..
@@srinidevadas9965 Glad I have the opportunity to say to you directly that you are a great prof.
The show starts at 17:39
HI! I'm from 006! :D
Soooooooo Awesome!!!
What is a request actually?
You are helpfull !!!!
23:46 I really hoped he pick that duster there 😳
Oops , there goes the duster 23:47 .
What level of math do I need for this? 10 min in some of it sounds like chinese already.
+ijw z The prerequisites for this course are: 6.006 Introduction to Algorithms (ocw.mit.edu/6-006F11) and 6.042J / 18.062J Mathematics for Computer Science (ocw.mit.edu/6-042JF10).
+ijw z The prerequisites for this course are: 6.006 Introduction to Algorithms and 6.042J / 18.062J Mathematics for Computer Science. See the course on MIT OpenCourseWare for more information at ocw.mit.edu/6-046JS15
lol
Thank you! Would you recommend taking 6.041 Probabilistic Systems Analysis and Applied Probability as well?
@@ilyakopyl yes
everyone buy the proof? not me.
This a grad course?
This is an undergraduate course. See the course on MIT OpenCourseWare for more details at ocw.mit.edu/6-046JS15.
is this course updated?
There is an update: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/. Best wishes on your studies!
after 4 years they really make Frisbee instead of cushion
is this thing is worth watching in 2023. Things are still same or updated?
This class is still worth watching in 2023. These topics are the same now as they were back then. Best wishes on your studies!
@@mitocw that's I'm searching about
18109:1532
I would get all the frisbees if I'm in the class
great
what is the prerequisite to this course? I don't understand most of it
6.006 He says it himself at 1:17 if you were paying attention
23:45 poor eraser :(
finally :D
Interval Scheduling: 17:30
Greedy Algorithm: 25:50
Greedy Interval Scheduling: 27:30
Prove: 42:50
I don't get 1:19:41. If recursive calls are O(1) then shouldn't the complexity be n? Why is it n^2, can somebody explain?
The O(n) here is that we need to compare n sub problem to get max value, which means we need call n times to solve sub problems, as you said, the recursive call are constant, so a subproblem complexity is N* O(1) = O(N). And there has N subproblems, so N * O(N) = O(N^2)
I don't understand why there are n subproblems. If we're taking the max over n things, that's O(n), but Srini said that just solves a single subproblem. Can someone give an concrete example of two different subproblems here, and why we need to calculate them? It seems to me that Srini is saying we need to calculate something else after we find that max in order to really solve the problem, but he didn't write it out anywhere and it's not in CLRS :(
@@WeirdAlSuperFan All of the subproblems correspond to an interval in the set, and are the problem of finding the max weight of intervals that fit after that interval. For the interval with the latest finishing time, it's not actually going to have a deep subproblem, as there are no later intervals, so solving that subproblem is going to be O(1). For the interval that has the 2nd latest finishing time, the subproblem consists of a choice between including the last interval or not. It's also O(1) to do this check. If we consider the third latest interval though, we can begin to see a pattern. The third latest subproblem now consists of a checking three options, either having no later intervals included, or having the solution for the second latest interval included or having the solution for the last interval included. Any check we need to do is an O(1) check thanks to memoisation, and we have to do 3 checks at most, although it's likely in this case that some of my phrased options are the same. As we continue this line of reasoning, we can see that each subproblem is O(n) because it can consist of up to n checks that are O(1) each (thanks to memoisation and the fact we are backtracking from the subproblem corresponding to the latest interval upto that subproblem). As there are n intervals, there are n subproblems hence O(n^2)
Greedy proof starts from 43:00
That Asian on 3:55
whatttt , its out of my league ...
Why do lecturers not use presentation slides and digital white boards?
While I do appreciate the OCW initiative, it seems really odd to me the MIT fails to innovate or even adopt solutions which would improve efficacy.
Maybe I'm not as smart as you, but I know that this mode of presentation keeps me at about full mental capacity. Something faster would just leave me far behind. If I wanted information to be densely packed, I wouldn't be watching a lecture anyways. I'd read the corresponding chapter in the CLRS book. Again, that's just me.
@@joeyfalcone3990 Hmmm, I don’t see how this modality adds value or efficacy.
Sleep Party 6.046
Does this guy for real using paper notes to write P and NP definitions on a board?
Well they have to cover a lot of topics in such a way that the students (who are most likely new to all of this) will undergrad, so it requires a lot of planning before hand.
fhd? wow
Professor is indian. So i am feeling comfortable.
proud to be an indian..