1. Course Overview, Interval Scheduling

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
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

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

[alexisglennespina]

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

[asadullahfarooqi]

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

[siyuanliu]

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

[ozziekhoo]

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

[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

[SiddharthaJoshi]

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

[shymaaarafat]

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

[livingwithlinlin]

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

[nickmartinez]

great reinforcement of my current undergrad algorithms class!

[random-characters]

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

[SameerSk]

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

[coolcodingtips]

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

[hannahbansal]

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

[devgumdrop]

Interesting proof. Essentially, the induction step is possible because <S(i_1), f(i_1)> 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 <S(i_1), f(i_1)>. (By assumption, the greedy algorithm can find a solution when the maximum size is k). So, as the greedy algorithm always finds <S(i_1), f(_1)>, 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.

[Marc-lhte]

Just finished 6.006, I am here to devour 6.046J

[vexilligerave]

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

[stevewu]

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

[eliasali]

8 years after this lecture, I am wondering how are these student doing now.

[SmokingNoir]

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