Lecture 16: Greedy Algorithms, Minimum Spanning Trees

author: Charles E. Leiserson, Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, MIT
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009,   recorded: November 2005,   views: 57543
released under terms of: Creative Commons Attribution Non-Commercial Share Alike (CC-BY-NC-SA)


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


"OK, today we're going to start talking about a particular class of algorithms called greedy algorithms. But we're going to do it in the context of graphs. So, I want to review a little bit about graphs, which mostly you can find in the textbook in appendix B. And so, if you haven't reviewed in appendix B recently, please sit down and review appendix B. It will pay off especially during our take-home quiz. So, just reminder, a digraph, what's a digraph? What's that short for? Directed graph, OK? Directed graph, G equals (V,E), OK, has a set, V, of vertices...

See Also:

Download slides icon Download slides: mit6046jf05_leiserson_lec16_01.pdf (404.7 KB)

Download Video - generic video source Download mit6046jf05_leiserson_lec16_01.m4v (Video - generic video source 172.6 MB)

Download Video - generic video source Download mit6046jf05_leiserson_lec16_01.rm (Video - generic video source 134.6 MB)

Download Video Download mit6046jf05_leiserson_lec16_01.flv (Video 238.1 MB)

Download Video Download mit6046jf05_leiserson_lec16_01_320x240_h264.mp4 (Video 249.9 MB)

Download Video Download mit6046jf05_leiserson_lec16_01.wmv (Video 738.4 MB)

Download audio transcript Download mit6046jf05_leiserson_lec16_01.mp3 (Audio lecture 19.4 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 syam, October 20, 2009 at 1:23 p.m.:

this is very nice . i thankful to sirs

Comment2 Ozgur, June 13, 2011 at 1:20 p.m.:

ProgrammingPages.net - http://www.programmingpages.net
Best Programming Resources and Source Code Examples for Java, Php, Visual Basic, C++ ,Asp, Python, Javascript, Ada, Cobol ,C, C#, Delphi, Fortran, Logo, Ruby, Xml.
Programming E-Book, Video Tutorials, History, Algorithms and Faqs.

Comment3 Georgi Kalchev, August 29, 2011 at 11:02 a.m.:

It was really nice of You to share all of these great video lectures. Thanks for sharing your great work with us. Wonderful idea and very helpful.


Comment4 Narges, December 10, 2011 at 12:38 p.m.:

Thank you for these great and useful video lectures.


Comment5 Jane, November 13, 2012 at 2:02 p.m.:

This is awesome! Thank you sooooo much for sharing, and for the careful index of time stamped slides. Such a great design, no more, no less, just the right fit to help learning.

Comment6 joji, July 15, 2013 at 3:37 p.m.:

wtf does this related to greedy tutorial

Comment7 suman kumar, October 18, 2020 at 4:21 a.m.:

The lecture was quite helpful . Thanks a lot MIT

Write your own review or comment:

make sure you have javascript enabled or clear this field: