Introduction to Algorithms August 19, 2008

# MIT's Introduction to Algorithms, Lectures 1 and 2: Analysis of Algorithms

<- previous article next article ->

I just finished watching the last lecture of MIT's "Introduction to Algorithms" course. Having a great passion for all aspects of computing, I decided to share everything I learned with you! This is the first post in an article series about this course.

As I wrote earlier, I am very serious about watching video lectures. If they are math-intensive, I usually take notes as if I were in the classroom. Lectures in this course were exactly like that -- logarithms, big-o's, thetas, expectations, and all the other math guys fighting with each other on the blackboards.

There are totally 23 video lectures, each around 1 hour 20 minutes long. I will be posting about 2 - 3 lectures at a time which will result in approximately 10 blog posts. Each post will contain annotated lecture, along with embedded video of the lecture and a time-stamped list of topics covered in the lecture. I will also post the notes I took myself as I watched the lectures (actually, I just bought a scanner (Canon CanonScan 4400F) just for this purpose!)

Understanding and designing effective algorithms is a very important skill for a top-notch programmer. You can still do good without knowing much about algorithms, but knowing them makes you superior. There are two kinds of people, those who can design effective algorithms and those who don't. ;)

## Lecture 1: Analysis of Algorithms

The first lecture is given by the famous professor Charles E. Leiserson. He is the L in CLRS. If that doesn't ring you a bell - it's one of the most popular books on algorithms!

He starts the lecture by explaining what this course and algorithms will be all about. He says that this course will be about "Analysis of Algorithms" and states: "Analysis of algorithms is the theoretical study of computer program performance and resource usage".

Designing great software is not just about performance. Charles presents a list of 12 things that can be more important than performance. Just for comparison with algorithms guru, what do you think can be more important than performance?

Here is the list of things more important than performance that Charles presented:

• modularity,
• correctness,
• maintainability,
• security,
• functionality,
• robustness,
• user-friendliness,
• programmer's time,
• simplicity,
• extensibility,
• reliability, and
• scalability.

He also asks "Why study algorithms and performance at all?". He and students answer:

• Sometimes performance is correlated with user-friendliness.
• Performance draws line between feasible and unfeasible.
• Algorithms give language for talking about program behavior.
• Performance can be used to "pay" for other things, such as security, features and user-friendliness.

The lecture continues with the definition of the Sorting Problem - given a sequence (a1, a2, ..., an) of numbers, permute them in such a way that a1 <= a2 <= ... <= an.

There are various algorithms to solve this problem. Two algorithms are presented to solve this problems - one of them is Insertion Sort and the other is Merge Sort.

Running time of these algorithms is analyzed by introducing Asymptotic Analysis and Recursion Trees.

Here is the whole lecture:

Topics covered in lecture 1:

• [17:15] Main topic of the course - Analysis of algorithms.
• [19:00] What's more important than performance?
• [22:03] Why study algorithms and performance?
• [27:45] The sorting problem.
• [29:30] Insertion sort algorithm
• [34:30] Example of Insertion sort.
• [36:25] Running time of algorithms.
• [39:39] Definition of worst-case, average-case and best-case types of analysis.
• [46:50] How to analyze the Insertion sort's worst-case running time?
• [49:28] BIG IDEA - Asymptotic analysis.
• [50:49] Asymptotic notation - theta notation.
• [57:14] Insertion sort analysis.
• [01:02:42] Is Insertion sort fast?
• [01:03:40] Merge sort algorithm.
• [01:05:25] Example of Merge subroutine of Merge sort.
• [01:08:15] Analysis of Merge sort's running time.
• [01:10:55] Recurrence equation for Merge sort.
• [01:13:15] Recursion tree solution of the Merge sort's recurrence equation.

Lecture 1 notes:

 Lecture 1, page 1 of 2. Lecture 1, page 2 of 2.

## Lecture 2: Asymptotic Notation

Lecture 2, on the other hand, is given by genius professor Erik Demaine. He is the youngest professor in the history of the MIT! He became professor at MIT at 20! Wow!

This lecture is all about mathematical notation (Asymptotic Notation) used in the analysis of algorithms. It's the big-o notation, big omega notation, theta notation, small-o and small-omega notation.

The second half of the lecture is devoted to solving recurrence equations. Three methods are presented:

• Substitution method,
• Recursion-tree method, and
• The Master method.

Here is the whole lecture:

Topics covered in lecture 2:

• [01:25] Big-o (upper bounds) notation.
• [03:58] Set definition of big-o notation.
• [05:25] The meaning of O(h(n)) in notation f(n) = g(n) + O(h(n)).
• [10:20] Big-omega (lower bounds) notation.
• [11:40] Analogies of O, Ω and Θ to comparison operations of real numbers.
• [12:28] Theta (tight bounds) notation.
• [13:40] Small-o and small-omega notation.
• [17:03] Solving recurrences: substitution method.
• [37:56] Recursion-tree method.
• [49:00] The Master method.
• [01:02:00] Proof sketch of the Master method.

Lecture 2 notes:

 Lecture 2, page 1 of 2. Lecture 2, page 2 of 2. Lecture 2. Sketch of Master's theorem proof.

Have fun absorbing all this information! Until next post!

Ps. It turned out that the lectures were not available anywhere but from MIT's OCW website. I found that they were released under CC license, which allowed me to upload them to Google Video, so I can embed them in the posts!

Pps. the lectures are taught from the CLRS book (also called "Introduction to Algorithms"):

<- previous article next article ->

Is it just me, or are both videos lecture #2?

Oops, James, you are right. I have made some kind of a mistake and uploaded the same video twice or something.

Fixing it now.

Thanks for the transcodes Peter. I can hardly believe that MIT decided to use Real for these... unless it's just a container for the encode.

Danno, it's true. MIT used Real for those.

So, I've taken and taught this class (as a TA, that is), and the one thing I need to emphasize to anyone that wants to really go through this class through OCW... the bulk of the learning in this class is in the problem sets. They are hard. They are very hard. They normally took a good 8+ hours each for a solid group of 2-4 MIT CS students.

I haven't looked at the OCW versions, but don't waste the material by looking at the solutions before you have a good struggle with them. As a student, and as a teacher, they were by far the most important aspect of the class.

As someone who has also taken the class, I second what Matt said. Most of the learning will happen from the problem sets. But also as Matt said, the problem sets usually are worked on in groups, so if you have a friend who's interested as well, it would probably make your life a lot easier to have someone to bounce ideas off of.

Hey, thanks for the share! Really enjoying this. It's great to see someone's notes as they show how another person intakes the information. neat notes too =P

Concur w/Matt + Brennan.

As another person who has taken the class, I never worked in a group during this class.

In fact, in my career at MIT I've only done 1 pset in a group. Groups can be good, but for most people I think they impede learning.

here you can find many of the algorithms of the book coded in Python.

Peter,

Thanks for this and for converting the videos for YouTube. Makes life much easier.

oh, you got coloured crayons :)
nice work :)

Wow, thanks, this reminds me of another, shorter, Great Course available from Stanford which I'd been meaning to post about for ages. The professor covers "the future of the internet" with a true expert's precision. He makes clear subtle economic points and lays out who really has the upper hand in the internet economy, why many communications acquisitions work or are bungled, etc. Though not pure CS, certainly relevant to the same crowd with a similar intensity to this MIT algorithms course.

In the bulleted list of items, I'm assuming item #5 "functionaly" should be something other than "functionaly" like functionality?

Thanks for posting the notes and reviews. It will motivate me to spend some time going through the videos.

babul, you are welcome :)

spx2, it's not crayons, it's soft color pencils :)

sml, you are right, it's "functionality". I am correcting that mistake now. Nice to hear that it will motivate you :)

I also agree with everyone who said that you should also solve a lot of problems, psets or at least quizzes!

This is no less than the 3rd time I've come upon your site and taken the tour of a subject matter through the provided lens. I distinctly remember following a Python thread and a thread re: one videos from one of the H/P/A/V'cons, and each subject has been extremely well presented ...

Thank you for taking the time to share your notes and doing a write-up, I watched the video first and then read your write-up as a reinforcement. Good stuff.

grantmichaels

This is a great initiative- building communities of learners in each subject. Let us hope more listeners come up with course blogs like you. You may also take notice of developments outside of MIT OCW. For example visit:

Where you will suites of about 40 hours of recorded lectures in each course in about 60 courses (and increasing) for the undergraduate engineering subjects posted by the IITs in India. Meanwhile Wikipedia is trying to establish a Wikiversity. Best wishes.

Hello,

I am just going through these lectures myself (haven't finished them yet, though). My approach is a little bit different.

Aside from traditional lecture notes, I put the information in a spaced repetition system like Mnemosyne (there are a few others but this one works great for me).

This thing tells me exactly when to review my notes. I make the flashcards on the fly as I watch the lectures.

The advantage is that I can take for example a longer break from watching the lectures (if for example you don't have time) and as long as you do your repetitions, you will be able to go back right where you left off.

I always had trouble previously because after watching 2-3 lectures, I had to interrupt for some reason or another and then start over from the beginning to make sure I remember everything.

You also have the added bonus of always keeping 90% of the knowledge in the lecture inside your head.

Could you host the videos on anything else? Google Video is often unavailable in China. For example I cannot watch the videos now. Youtube would be better.

Looks interesting, but I give up as soon as I hear a lecturer speaking verbatim while he is writing on a blackboard "Theerrre ... aarrre ...." One should not be allowed in front of students with this crap.

Peter: Nice site and thanks for being sure to mention our CC license. Our videos are also available through YouTube with embedding enabled, which might save you some trouble. They are also available through iTunes U for download.

Best,

Steve Carson
MIT OpenCourseWare

Steve,

Only the audio (for this course) seems to be available via iTunes U. To be honest, I don't find just the audio very useful for a course like this. I would very much appreciate it if the video lectures were uploaded to iTunes U!

Like one of the comments states: Doing the psets and spending like the 8 hours on it is how you get the most out of this class. I don't know if they post the take-home test too, but that's definitely challenging.

Argh! RealVideo is the most frustrating format I've ever had to deal with.

How are you converting these?

Michael,

I used Avisynth + Virtualdub + Realtime Alternative.

First I installed Realtime Alternative, then Virtualdub, and then Avisynth.

Then I created this Avisynth script for each realtime video:

```file = "ocw-6.046-31oct2005-220k.rm"

DirectShowSource(file)
```

I named each script like ocw01.avs, ocw02.avs, ... ocw23.avs.

Then I loaded each script one by one in Virtualdub and chose Audio -> Full Processing Mode, and selected Audio -> Compression to be mp3 at 16kbit/s.
The same for Video. Go to Video, select Full Processing Mode. Then select compression to be DivX at 230kbit/s.

Then File -> Save as AVI and save the video to ocw01.avi, then load the next .avs and save to ocw02.avi, etc.

This was time consuming but I was unable to automate it with ffmpeg.

btw, thanks peter :) great job. it's a good addition to autodidactism :)

very interesting!
thank you :)

I guess I'm not following the second lecture:
1/2 * c n^3 - n == -.5 if n=c=1...
which is lt 0...

how can i prove that we can create a minimum spanning tree with Prim,Kruskals algorithms in the case that the weight of a tree w(T) is the largest (maximum) of the weights of the edges e

w(T)=max{w(e)}

Dude can you please tell me where i can get all the video lectures. Google video doesn't have all of them and its such a pain in the ass that i cant find all the lectures on one website. Also the sites that claim to have the lectures keep crashing on my browsers !!

Peter, Fantastic Job!

I have just started going through the lectures. Would you recommend a good way to download these video to watch offline?

Thanks...

hello!

Is there some compact material about that math requirement he mention?
I remember something from my study time, but can't really follow all that math stuff that are in this course.

Most of the lecture videos can be found on Youtube.com/edu MIT page.

And thanks kurumin for the informative post.

Awesome, just what I was looking for! In combination with school this is an excellent tutorial!

Are the problem sets (and, ideally, answers) available anywhere online? I think following along with the lectures is great, but being able to look at the problem sets would be even better.

very nice work, every bobdy have to be
interested, continue and improve.thx

Brilliant work fellows, it is really helpful for students like us from other institutes all over the world.

This is a scholar from National Institute of Technology, Srinagar, India. These web realeases of MIT lectures have been quite helpful. Great work over thr guys!

Any one tell me what will be the upper bound of following recurrence.

T(n)= T(n-1)+n^2.

Sorry, its
T(n) = 2T(n-1)+n^2

Arslan, it's exponential O(2^n).

At root level you have work n^2, at 1st level 2(n-1)^2, at 2nd level 4(n-2)^2, ..., at i'th level 2^i(n-i)^2.

Peter: "fantastic work"; and "thank you very much"; How do I grow the new lobe on my brain to hold this :-)

As usual, I loved this post too. This is a nice to have list of algorithms related lectures. This one goes straight to my delicious account.

i have to thank u cos these notes and videos helped me so much for understanding the logic. i studied wth these videos and notes and find all my questions answers about these topcis. they re really reallyy helpful and good explained. thanks to all =)

Looks like Alexander Calder's sculptures on the cover of the book. I've had the book for undergrad algos courses, but only now am I noticing this after my arts course. Interesting .. Very Interesting. http://calder.org/work/category/hangingmobile.html

hey!

I'm studying for tomorrow's exam in Algorithms & Complexity (which I will probably fail as I never actually followed the course) and I stumbled on your blog in a frenzied attempt to get a better grip on the Master Theorem.

I am in love with your blog(and the mit course videos), downloaded all the course's problem sets for a bit of self summer schooling :P. It's resources like this that make the internet so gr8 :))))

super super thank you =D

Hi,

Thanks,
Siva

http://nptel.iitm.ac.in/video.php?courseId=1065

http://www.cs.sunysb.edu/~algorith/lectures-good/index.html#01-01

There us no audio in these videos while
playing in vlc
Plz suggest the recommended player

mplayer works fine, Shrish.

I liked your notes very much. It helped me a lot. Thanx.

cn anyone tell me in l1 y the height of tree is logn??
cant figure it out....is it too obvious??

well. if tree is complete binary tree, no of nodes in tree can be found using formula n = 2 pow h, where h is the height to tree.if u take log on both sides it comes out to log(n) = h log(2).
log(n) = h log(2) of log base 2
h = log(n).

but this is valid in case of complete binary tree.
i hope this solve your query.

Very good summary and thanks for the notes. They are really helpful. I`m looking forward to more.

Aside from traditional lecture notes, I put the information in a spaced repetition system like Mnemosyne (there are a few others but this one works great for me).

This thing tells me exactly when to review my notes. I make the flashcards on the fly as I watch the lectures.

The advantage is that I can take for example a longer break from watching the lectures (if for example you don't have time) and as long as you do your repetitions, you will be able to go back right where you left off.

Do you think that a 10th grader in high school can understand all the stuff of this whole course?

Well, why don't you give it a try? I believe an overall exposure to basic math, algebra and stuff coupled with a lot of interest to learn is more than enough I guess :)

Any ways, to @pkrumins: I started learning this book myself at home after work, with these lectures, I'm happy am not alone!

This is awesome. These video helped me a lot during my data structure classes. I actually learned more on this website than in class :-)

Thank you. I will do all the courses.

the content of the blog was great but it would be highly appreciated if it also contains some material related to c proghramming tips
thanks and regards!
kushal bansal

Well done Peter,

What are the requirements for the second lecture?
I got lost straight away.

Discrete math, calculus, math logic.

@Peter : well done buddy ,,

I am very much afraid if i can't understand the lectures,, fingers crossed

What is currently the best place to download the lecture slides and/or videos?

Would appreciate if someone can mail the best place to download the lecture slides and/or videos.

Thanks
Birol

Pls mail to birolayg at gmail dot com.

Sorry it took me three comments to get it right.

I am from syria ,I speak arabic , I watch lecture 1&2 ,I did not understand "substitution method" ,can you explain it in simple way ,with more examples. thank you.

Hi nour,

There are two steps to the method.
1. Guess the solution
2. Prove the solution by induction

For example, we try to get the upper bound of T(n) = T(n/2) + 1 (this is the recurrence relation for binary search)

My guess is o(lgn) so our guess should look like T(n) <= clgn for some c and n > N.

Then we prove the guess by induction.

We assume that T(k) <= clgk holds for k < n.
So,
T(n) = T(n/2) + 1
<= clg(n/2) + 1 (note: we invoke the assumption here)
= clgn - clg2 + 1
= clgn - (clg2 - 1) (note: we rearrange them to the form desired - residual)
<= clgn when c >= 1/(lg2)

done!

hey peter,

thanks for your notes! I'm reading it for my test this week. =)

Jason

Hey i am looking for someone who can help me solve the problems in Analysis of Algorithms Second Edition
Author- Jeffrey J.Mc.Connell

Just watched the 1st of the series this morning.
Recv'd BSc (TESC-1980) and have been professional since-
am expecting this to be a great review.
Also wanted to Thank the SysOp for this board -
I know already that communication is the key when one get's stuck.
TNX JB

I found this helpful / useful to Charles first lecture. BTW I did not agree that Bells & Whistles ,
( user friendliness & functionality) takes precedence over Performance.

Meaning, if it doesn't have good to outstanding "Performance" , then it'll never fly. Either the director won't let it out-the-door, or if it does, by fluke, get released, then no-one will buy it.

Point in fact, the Radio Shack Trash-80, sorry, meant to say TRS-80, had all the good points of friendliness and B.A.S.I.C language, but just didn't have any performance! If the programmer / analyst doesn't put Performance as Job #1, then the competition will !, no-matter how fun or exciting, salable, modular, extendable or secure yours is.

http://en.wikipedia.org/wiki/Merge_sort

This, is what it was that I found to be useful to Charles' First Lecture.

Your handwriting is horrible, but otherwise it is very useful. So, thanks a lot.

Hi. I can't access the videos at all. Getting the Errormsg: "This video is privat". How to fix that?

I am not able to access the videos. I am seeing " The video is private". How can I access them for quick review for myself.

Same here .. i cannot access the video - says the video is private.

I can't see it - says the video is private.

Dear poster,
Thanks a lot!

I think the MIT course - including lecture videos and other materials, is available at:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Actually this link is there in the original post only - just noticed !
Thanks Peter for all the notes and for sharing...

There are two more books :

Top 10 coding interview problems asked in Google with solutions: Algorithmic Approach by Lin Quan.

Algorithms Unlocked by Cormen

Hey Doug,
Do you have the pdf of these books?

Hi

I would love to learn from this videos. but I can't access them may be the link is broken or something. Please tell me how to access it.

Of the list of things more important than performance, I think only correctness always belongs there (especially given that adequate - not best possible - performance is an aspect of correctness, and similarly for security.) The importance of everything else is conditional, and the priorities negotiable.

thanks a lot.

http://learndesignanalysisandalgorithm.blogspot.com/