1. Course Overview, Interval Scheduling

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

[@alexisglennespina8471]

Thanks MIT for providing an updated version of your algorithms class. You are truly awesome. You continue to inspire me to learn more.

[@neuron8186]

what do you mean by updated version

[@ru2979]

@@neuron8186 hey u , why u mocking him

[@siyuanliu4581]

The video quality is truly amazing, and it keeps getting better and better. Thanks MIT, the professors and staffs behind the scene!

[@SharatS]

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

[@Suborneer]

Sharat Sachin where did you find recommended order

[@kwokpinglau2400]

Thx mate

[@minh_tran]

Thank you so much!!!

[@hujake5406]

Thank you!!!!!!!!!!!!!!! you just save my soul which fcked up by corona virus

[@yeowzh]

Thanks mate. I was looking for this comment. Really helpful

[@ozziekhoo]

Thanks whoever wrote up the subtitles, they really do help to ensure you don't miss out on anything.

[@asadullahfarooqi254]

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

[@SameerSk]

*_Very big thanks to MIT OCW for helping us with this beautiful course_*

[@abhineet5834]

Interval Scheduling starts at 17:30

[@BABEENGINEER]

THANK YOU

[@sai4007]

Thanks a lot for uploading this, Srini, Erik you rock on .. .

[@stevewu9372]

I love everything about MIT, I am very grateful and willing to donate!

[@ShingHim]

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

[@coolcodingtips4624]

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

[@waltermitty6446]

Thanks MIT for providing these amazing course!!!

[@vexilligerave9356]

A very good series. More contents from CLRS are covered compared to the previous 6046 and 6006 courses.

[@nickmartinez4064]

great reinforcement of my current undergrad algorithms class!

[@ilyakopyl]

+1 I take the classes at my local university for credits, I watch these lectures for knowledge.

[@shymaaarafat1342]

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

[@darianharrison4836]

Thank you MIT for this opencourse, it is very good

[@srinidevadas9965]

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/

[@SiddharthaJoshi]

Weighted Interval Scheduling starts at 1:02:15 Thank you MIT OCW, and thank you Prof. Devadas.

[@adityasinghaswal4923]

thanks bhai :)

[@DeedeeM3gaDooDoo]

you guys are awesome thanks

[@ameslouis4264]

Thanks you very much, It helps me a lot.

[@memoriasIT]

Thanks for providing information for free

[@livingwithlinlin3122]

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

[@Marc-lh7te]

Just finished 6.006, I am here to devour 6.046J

[@hannahbansal4572]

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!!

[@ndmath]

Bless MIT.

[@yue7987]

Thank You!

[@nickwhite8238]

Course begins at 4:35.

[@sudheerays9559]

thanks

[@rj-nj3uk]

Thanks

[@BABEENGINEER]

THANK YOU DOOD

[@SergeyLeschinsky]

From 480p to 1080p! Wow! Possible it's a good time to upload 4k version of 6.006

[@codethings271]

im loving it :)

[@hanfuzhao805]

hi where can i find the corresponding reading assignment for the course?

[@random-characters4162]

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

[@cbskwkdnslwhanznamdm2849]

And chalk

[@jakeroosenbloom]

9:25 Lectures starts here.

[@WhateverYouLove]

God, I love their big-ass chalks.

[@rj-nj3uk]

Good!! Human.

[@hektor6766]

It'scalled railroad chalk, similar to sidewalk art chalk, usually used for construction and insurance claim investigation.

[@SmokingNoir]

Thank you MIT for uploading. I might just pass my coding test and get a job thanks to you. Maybe...

[@hansu7474]

I hope I can learn this within a year after I satisfy prerequisites. I will be back!

[@liangyuliu3648]

Soooooooo Awesome!!!

[@Gokulbhusal-oj3fy]

Thk you sir

[@seblewongelashenafi3417]

You are helpfull !!!!

[@jamest2736]

Are there any plans of making an edX version of this course? (also for 6.006)

[@GoogleUser-ee8ro]

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

[@devgumdrop3700]

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.

[@BipinOli90]

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

[@sonurony5171]

Can someone tell me what are the prerequisites for this course. ps. I know c and cpp fairly well

[@mitocw]

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!

[@ns4k_tv]

I didn't understand a thing, any class that i should watch before this? can someone help me with links?

[@MrEternalFool]

I want a frisbee.

[@TheGerakas]

It costs $250K (I had the same thought)

[@xpwasteeldevin]

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.

[@himanshumundhra1256]

6.042J

[@Alice_Dawn23]

prove of choosing ealiest finish time: 42:48

[@17teacmrocks]

i think i'm in the wrong course lol. I was looking for the newest one but the intro one must be 6.006

[@harryhoang7734]

Anyone can tell me which section in the course textbook assigned with each video lecture?

[@mitocw]

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.

[@ravitheja012345]

Study from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

[@jerrys5387]

Hi guys, which version is better to watch this one or the 2011’s?

[@silveriofex]

I was wondering this too, I love the 2011 first chapters

[@coding99]

resolutions really tells the time between 6.006 and 6.046...!

[@sushantrocks]

I don't why but i intently started listening to the logistics as well 😂😂.

[@forheuristiclifeksh7836]

14:41 deyrrmining graph if it is hamiltonian cycle is difficult

[@saranshthakur9999]

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.

[@mitocw]

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!

[@akshaymathur2225]

Why are so many people leaving ?

[@adiigeak8568]

Not able to get the third example of incompatibility in 37:55

[@sushantkumar4917]

23:46 I really hoped he pick that duster there 😳

[@isbestlizard]

HI! I'm from 006! :D

[@ashijoshi7982]

I didn't understand why k* should be maximum?

[@chinmaydas4053]

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

[@srinidevadas9965]

I would start with Python. Good luck!

[@chinmaydas4053]

Thank you sir for your reply.. Sir what's the best video resources for learning python in depth.. Please answer me sir..

[@srinidevadas9965]

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

[@chinmaydas4053]

Thank you sooo much sir.. Lots of love and respect for your Sir from India 🙏🙏🙏..

[@hektor6766]

@@srinidevadas9965 Glad I have the opportunity to say to you directly that you are a great prof.

[@holdenmcgroin8917]

The show starts at 17:39

[@FelipeCampelo0]

What is a request actually?

[@theaveragecoder6182]

Oops , there goes the duster 23:47 .

[@bavidlynx3409]

is this course updated?

[@mitocw]

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!

[@user-zp3nd6ht8v]

everyone buy the proof? not me.

[@SJ23982398]

What level of math do I need for this? 10 min in some of it sounds like chinese already.

[@mitocw]

+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).

[@mitocw]

+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

[@Rooot-username]

lol

[@ilyakopyl]

Thank you! Would you recommend taking 6.041 Probabilistic Systems Analysis and Applied Probability as well?

[@HarshitSharma-kk6yz]

@@ilyakopyl yes

[@pablonapan4698]

This a grad course?

[@mitocw]

This is an undergraduate course. See the course on MIT OpenCourseWare for more details at ocw.mit.edu/6-046JS15.

[@Mumbaicarmeet]

is this thing is worth watching in 2023. Things are still same or updated?

[@mitocw]

This class is still worth watching in 2023. These topics are the same now as they were back then. Best wishes on your studies!

[@Mayank93000]

@@mitocw that's I'm searching about

[@tfluan0606]

after 4 years they really make Frisbee instead of cushion

[@ahokai]

finally :D

[@anythingstudio5208]

Interval Scheduling: 17:30 Greedy Algorithm: 25:50 Greedy Interval Scheduling: 27:30 Prove: 42:50

[@hamids4550]

what is the prerequisite to this course? I don't understand most of it

[@rahulpujari9607]

6.006 He says it himself at 1:17 if you were paying attention

[@user-mv4oh8yp1y]

18109:1532

[@o.y.930]

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?

[@mytennisjourney4949]

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)

[@WeirdAlSuperFan]

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 :(

[@devgumdrop3700]

@@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)

[@junweima]

I would get all the frisbees if I'm in the class

[@stabgan]

great

[@trentonfeda7350]

23:45 poor eraser :(

[@merr5593]

That Asian on 3:55

[@merlingrim2843]

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.

[@jordanozang3317]

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.

[@merlingrim2843]

@@joeyfalcone3990 Hmmm, I don’t see how this modality adds value or efficacy.

[@jiaweixue6396]

Greedy proof starts from 43:00

[@sahilshah9047]

whatttt , its out of my league ...

[@JoffreyB]

Does this guy for real using paper notes to write P and NP definitions on a board?

[@navjotsingh2251]

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.

[@Poti221]

Sleep Party 6.046

[@IiiIiIIIiiiiiIiIII-nh9zx]

fhd? wow

[@RiteshKumar-vd7rc]

Professor is indian. So i am feeling comfortable.

[@rvrishav7]

proud to be an indian..