Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

[k24bfan]

taking the this exact course at my university. This helps a lot for getting ahead and reviewing.

[ndduy1995]

Just a dream, from Vietnam.

[SpitTanker]

Sad that I am studying in Italy, this university in america costs 30.000 dollars per year, but if I see the difference is not that MIT is harder thatn other universisties.The difference is that they explain well the same things that are explained with other universisties.

In my university all professors are messy, it totally sucks.The problem is not the difficulty of the problems itself, but understanding what the hell professors are doing.From this lesson I have understood everything,it's clear

[spellnisharwaseque]

OKAY! :|

[maidwithluv]

just kidding. I meant the explanation of why people like stuff better than performance...

[maidwithluv]

omg its worse than precalculus...

[ollobrains1]

i dont have prerequisites but i can get it hahaha

[meditating010]

Yummmmy!

[iemandmetgeenhoofd]

This is so much more interesting then frech

[NanceyAnissaxe668]

so is ja lustig

[bigrickjr57]

Extremely clear, articulate and concise; I prefer this learning style and teaching methodology. Enhances one's understanding and further minimizes complications in learning the subject matter. Dr. Ricky L. Johansen, Jr., Ph.D.

[thecomanche1]

Doesanyone actually use this in their job

[keez1994]

@thecomanche1 He mentioned how frequently this is used in programming. It's an optimization thing.

[FightTheSystem1492]

this lecture is very easy to interpret..nothing special

[SuperKittyPancake]

I just wish to get into MIT.

Boys can dream can they?

[TheDawigginton]

@SuperKittyPancake Work hard; it can happen. I was accepted to MIT even though my family is forced to live on government assistance and my father is disabled. Due to a perennial hospitalization, I am not currently attending, but I was accepted and had a full scholarship. Don't give up the dream man.

[webDes33]

@TheDawigginton if you can make it into MIT with a scholarship you can probably do good regardless!

[MrChimei]

My god these students are dull!

[alb12345672]

Lecture Summary - Insertion sort is n^2 time(quadratic), while Recursive Merge sort is nlog(n) (log time - MUCH faster).

[massinamas]

What are the prerequested courses?

[gomunkul]

@massinamas discrete math and a basic intro into programing course.

[CasperBHansen]

he actually wrote a single-line comment on the whiteboard, brilliant :P

[digital111x]

what was so funny at 28:20 ??

[BrainRotMenacer]

@digital111x I'm wondering the same thing. Must've been something that happened off camera

[TheTharinduTube]

Ahhh I got it ... it's the stereotype "beats" which fooled me.....

[TheTharinduTube]

@hrseif but here the comparison is between O(n^2) and O(n^3 ) .... :(

please make that clear for me..........

[Omegaroth]

damn... didnt take the probability class...

[TheTharinduTube]

at 53.45, he says thatas n gets bigger, O(n^2) algo always beats a O(n^3).Is this the correct thing or the other way round ???

[hrseif]

it's correct .

O(n^2) makes smaller running time than O(n^2), so it's better

[johnthegr8]

@TheTharinduTube Yes O(n^2) is more efficient than O(n^3). Quadratic time is closer to constant time than cubic time. With big O being the upper bound time and Ω (Omega) being the lower bound. Quadratic time isn't bad but logarithmic is better.

[MichaelisOnYourtube]

should a person wishing to learn computer programming learn about algorithms BEFORE or AFTER actual computer programming?

[VerbalMechanics]

@MichaelisOnYourtube You won't be able to grasp the concept of algorithms until you are fluent in programming.

[iBradleyAllen]

Sorry but the guy is not a good teacher. in 35 minutes or so talking about sorting numbers he starts at the 2nd number? but doesnt use his algorithm! he just looks at them and sorts them reading his paper, not teaching about the algorithm, DUH

how is that using the key? he mentions nothing about how the sort takes place, a 1st grader could sort the numbers. he seems to be very smart but is not good at teaching

[iBradleyAllen]

looks hopeful, but 4 minutes into the lecture and the "uhhh"s and "umm"s are SO ANNOYING, why doesnt someone tell him how annoying the uhhhs and ummms are?

[TheBilly]

You know guys, it's perfectly acceptable to edit.

I half expect to see a 20 minute fire drill in the middle of a lesson.

[85Damix]

Can I get it HD ?

[TheBilly]

@85Damix No. 240p MPEG-4 is the best available for download on their site.

[shebotnov]

i wish all, or at least my uni would tape our lectures

[elcanful]

wow this course is actually available for free here? nice..

[aperezNWO]

Thank you!



[ooMatttyooo]

what math background was he refrerriing to is it specifically discrete mathematics? or is there more involved?

[deonteCsewell1445]

58:02 LOL looking at it from 30,000ft compared to 3mm, lol we gonna be up on planes?!? J/k

[fashanu1000]

interesting stuff

[Gr33nAv3ng3r]

Mergesort @1:03

[fuentes83]

34:13

[Shursharochka]

Please, help me!! What does 'SMA course' mean? I know maths but I am Russian and so I am hesitating with translation. thank you so much in advance!

[MrFloce]

@Shursharochka Singapore-MIT Alliance (SMA)

[Shursharochka]

@MrFloce Thank you!! :) You are soo nice!! :)

[Shursharochka]

@Shursharochka You are welcome :) Good luck!!!

[CSryoh]

17:00 for the actual leason

[sas1ni69]

@CSryoh Thanks man.

[Karmakameleeon]

@CSryoh thank you!

[epicnidhogg]

@CSryoh thanks

[tattoconga]

Yes, I like to watch this kind of videos. So far the ones i've seen are mathematics lectures (I'll be graduating today (receiving my math B Sc) but I also enjoy watching computer science lectures.

[fashanu1000]

@tattoconga i've always been interested in finding out why people study math i like math just as a hobby m 15 and do intergel calculus for fun but i dont see what future reference mathematics will give me so i was hoping you can tell me why you chose a degree in math instead of physics or biology or even computer science.

[eatme690808]

@fashanu1000 Arthur Benjamin gives a useful answer to your question by going over the ABCs of math: A for applications, e.g. math is crucial and foundational for the fields you listed (less so biology but in certain sub-fields dramatically so), B for beauty, e.g. deriving Euler's identity or Euclid's proof of root-2's irrationality, and C for certainty.

[iiiaxel]

Hey does anyone know how did he get theta (j) to define the worst case asymotic analysis formulation of insertion sort, I'm lost on that part...

[tattoconga]

@iiiaxel Before the inner loop, you can see the statement 'i-j-1' and then in the inner while loop you see that it doesn't halt until i<=0. It means the the while loop (in the worst case) will be runing j times since it depends on i and i goes from j-1 to 0. Inside the while loop there's only a constant number of operations, which means the running time of the whole while loop will depend linearly on j i.e will grow proportionally to j. continue in next coment

[tattoconga]

@iiiaxel since we're working with asymptotic notation, you can drop the constants and just notice that it grows proportionally to j i.e you have theta(j). I hope this was of any help. I understand it but i find it hard to explain stuff, especially because english is not my mother language (btw Im not from india as most viewers XD, my country is crazy light green)

[iiiaxel]

@tattoconga Yes it does :) Thanks for that, Your english is great :) I used to lived in a country that covers with green too, btw are you doing/following similar course as this one?

[kurco19]

capooooooooooooo!! veni a la fing! :P

[Qualia]

hm, ok?

[chinbnm]

that is leiserson, he is one of the authors of the bible of algorithms... amazing book

[sim2k]

wow, have a look on the map, the most of the 186k viewers are from india :O

[bahramg82]

@sim2k LOL.The India map is dark green like crazy.

[Ghaiyst]

@sim2k Well, watch from 00:27 again. He talks about that it's an SMA course (Singapore MIT Alliance course). So, I'm not surprised at the idea that a big fraction of the views are from India.

[jasonofthel33t]

@Ghaiyst what does Singapore gotta do with India?

[kkkk888896]

just do it

[Brucy6666]

humm, 240p

it was a challenge, but i got through it :)

[pthanhkim]

thanks for the vid useful

[shooterman13]

the older guy is better, the hippy guy is to fast and analytical

[magnet101]

Liked it. I'm from the UK...where is MIT? The lecturer was great but I found myself counting how many times he said "ok". Ok.

[systemnate]

@magnet101 Cambridge, Massachusetts, United States (MIT stands for Massachusetts Institute of Technology)

[magnet101]

@systemnate Thanks for that! :)

[magnet101]

Liked it. I'm from the UK...where is MIT? The lecturer was great but I found myself counting how many times he saod "ok". Ok.

[leokelly3]

12 people aren't sorting their bits correctly.

[bballr09]

"fortunately you all have a strong probability background...so if you don't, maybe it's time to say 'gee maybe i should take that probability class that's a PREREQUISITE for this class'" lol harshhh

[protegy100]

This is amazing

[HWGuyEG]

Why is performance important... hardware isn't out-pacing programmer incompetence, whoo flash games going slower than Crysis.

[keithyw]

far better instructor than my algo lecturer back at my university. his explanation makes sense and was easy to follow.

[sisudo21]

His explanation on insertion sort was bad. He forgot to mention that it must compare itself to the previous number. It doesn't just "move" there magically.

[darkyto]

Ahora estaba estudiando algoritmos, por mi cuenta, wow !!! solo eso puedo decir

[ratatulsuprem1]

not explicit

[so2murad]

Hi is this undergraduate or graduate course ? thanx !

[ike353]

@hypoxide you just had to mention that and ruin it for everyone lols =P

[hypoxide]

I never considered how distracting ending every sentence with "k" could be.

[manconoo]

ok ok ok

[csjpeter]

Interesting to see how a lesson is going on the MIT. Basically I would say I like it except it takes a bit more math than really need for an introduction to algorithms. Evens so, unfortunately it is not even mentioned at 1:00:35 that Theta is an additive function. Which is very important property, without that SUM(j=2;n)Theta(j)=Theta(n^2) could not stand.

[BlueWaffleMan9000]

eric = hippy

[Octobre1986]

I'm not pretty much into maths and informatics but this was quite understandable and interesting. thank you.

[ThePakistaniMuslim]

The teacher calculated the height of tree as log(n) but if there is only one element in array to be sorted that is n=1 then log(n) =log(1)=0 which means that the height of tree is zero which is not true as n=1 so it should be log(n)+1 for calculating height of tree.

[hassamu]

@ThePakistaniMuslim

If there's only one element in the array to be sorted, then it returns n because the element is already sorted. Besides that, the height of a node (in this situation the root) it's the longest downward path to a leaf from that node, therefore if you have a tree with only one node, which is the root and at the same time it is a leaf, then the height of the tree is 0, which is log(1).

[ThePakistaniMuslim]

@hassamu Yes i've mistaken. Hieght of tree will be zero. But total levels of tree should be log(n)+1 because at n=1 there exist atlest one level.

[mpatso8klotsia]

I like this theacher a lot so much fun to his lesson!I am not in MIT so one the students there please confirm. The metaphor of Performance ~ Money so to have other features was brilliant!

He is one of the authors of the book that suggested.A classic one

[sim0332]

awsumm i want for admission in MIT. . .

[syntaxerorr]

HAH..@ ~36:00

"Lets take a look at running time"

*looks at watch*

[sreekanthbhagavatula]

wish I found these before I finished my masters or during my bachelors.

[bone009]

Damn!, should've went to MIT when I had the chance!, Freaking Harvard, worst choice ever!!, Fuckking professors self-study excuses...

[nbjsw]

@bone009

have mercy on U

[TheRahulon]

its very help full and worth while...

[kelbiiiz]

In Sweden it´s free to studie .. no I was wrong .. you get like 2800 monthly.. to just studie... sooo.. hahaha love and hate this country. That teatcher is nerves like a mother fu*ker.

[fiffo]

This was awesome. I study Computer Science in Italy and this was very helpful, I really appreciate you putting this on the web, this embodies the idea of free culture that I hope everyone will one day agree about.

[AMDNiels]

Can someone tell me if this is correct:

Another solution for the worst case analysis of insertion sort: Recursive equation for T(n) = T(n-1) + 1. This gives the closed form of n * (n+1)/2 + 1, so this means 1/2*n^2 + 1/2*n +1, so in Theta notation: Theta(n^2).

[cchampio]

@AMDNiels Insertion sort is not recursive, so it has no recurence relation.

[AMDNiels]

@cchampio I'm talking about the relation of how many times it has to

call up a value, thats 0 times for 0 items, its 0 times for 1 item, its 1 time

for 2 items, its 1 + 2 times for 3 items, its 1+2+3 times for 4 items, etc..

Seems like recurrence to me.

[Entertainmentwf]

@cchampio ... it's clear you maybe don't know what the term recursive means but, iterative algorithms can be written as recursive algorithms... All you do is change the iterator into recursive branching that has a growth related to the count of iterations. The growth is polynomial (for this case) but, the problem can be written in more than one way.

[cchampio]

@AMDNiels your recurence is wrong too. it's theta(n). I tried to post the solution but youtube keeps giving me error and won't let me post it. something it dont' like about the text.

[kingbrocklesnar]

i'd like to know the rationale why in asymptotic notation we can drop the lower terms (that's harsh!) and ignore leading constants (rude!)

otherwise i claim this lecture is bogus....i mean... this guy calling the student who gets the best grade in his lecture cheating!

[samgee2007]

a third world country Singapore (a tiny island) is teaching America about maths?

[marturz]

@samgee2007

Singapore = third world country, I guess not, ever heard of the HDI of Singapore?

[DonEddy89]

It is very nice that MIT runs the OpenCourseWare Programm

Other Universities should look forward to copy that type of enabling free education for everyone ! I'm definitely supporting this..

[ProjectJava]

I love class on the web. You never get called on.

[a4avaiz]

its easy for one to get lost on how the elements are being sorted for mergesort. its important to understand how mergesort divides the workspace and sorts each half and finally merges it. once this is done, one will always know why mergesort is O(nlgn)

[a4avaiz]

this is a great intro. but as a student, I think the insertion and mergesort implementation details have been scrificed. even tho its just a few lines of code, the mergesort implementation is a beast. for an array of 10 elements, the number of stacks and variable versions generated by the recursive calls is quite large.

[a4avaiz]

this is a great intro. but as a student, I think the implementation details for the ins and mergesort algos were sacrificed. even though its just a few lines of code, the mergesort implementation is beast. for sorting 10 elements the number of stacks and variable versions generated by the recursive calls is quiet large.

[GuruOfComedy]

Great lecture, algos start at 28th minute

[AJSwisgirl]

ok hahhaha i passed the course by saying ok -ok -ok -ok ... irritating heheh

[predatora]

Your teachers still writing to blackboard speeches that would speaking. And your lessons are so simple even at mit.

[mobbindag]

This class is rad!

[interted]

do you know of a good book that a can consult while i attend this lectures?

[1tahirrauf]

"Introduction to algorithms"

Thomas H. Cormen

Charles E. Leirson

[interted]

@1tahirrauf thx

[Waranle]

@interted yes there is a book called "introduction to algorithms" ebook, google it

[hades1088]

Cool!!

[MrDrixos]

WOW, zot intresant en al...

[unknownliviu]

this is quite 9th grade stuff at the best high school in Bucharest , Romania

[jarjar2b]

@AJSwisgirl

hiss orospu bak bu sarki sana geliyor. kafani kirarim kopek. benim favorilerimde var bak cok sevecen.

[philabyebye]

anyone know any real Intro to Algo's videos? I have to learn a little about a few programming languages and write some basic algos and simple programs. I have only done web programming with a little Php so I understand the basic idea but this was too complex for me.

[zobayer1]

go for C/C++ then, this is best and easiest to implement algorithms, infact now a days, algorithms are more written in C/C++ fashion. php is almost similar to C/C++...

[sutton513]

m'kayyy

[WolfmansBrother321]

This guys says OK way to much. But the class seems pretty good.

[GreenWave68]

this is re-donk-uls!

[Astrosisphere]

It's just as bad at my uni! They spend more time telling you about the structure of the course and what you're going to learn than actually teaching you the stuff!! Then when it comes to teaching you the stuff they blabber on with little or no visual aids!

[BlakeVII]

I have a feel for what you're saying.

Good comment.

[123adideutsch]

I have a question regarding the lesson-

Why did the lecturer wrote "log n" (1:15:45) ?

As much as i understand it should have been (log n)/(log 2),

because the tree is divided each time by 2 and natural log could work only if the tree was divided by 10 each time.

[FlagstoneFiend]

because if the last level will be complete and the number of leaves will be n it will be 2^h just look at the tree for level 1(h=0) n=2^0=1,

for level 2(h=1) n=2^1=2, for level 3 n=2^2=4,for level 4 n=2^3=8

[123adideutsch]

but that is exactly what i say:

you say that n equals 2^h.

according to that h should be (log n)/(log2).

[FlagstoneFiend]

wait!! i mean h=logarithm in base 2 of n that mean lg n/lg 2 or ln n / ln 2 but thats the idea of asymtotic it's not important for you what's the base if you had a tree with 3 children for each node execpt the leaves on the last level it will be log in base 3 of n but the complexity is log n like it was in the example for 2 children so infinity

= log(1,n)>log(2,n)=log(3,n)=...­>log(n,n)=1 not nice i know but this is the idea

[123adideutsch]

so to conclude, (just to be sure i understood it well)

h equals to (log n) / (log 2) , but since n equals infinity in our performance calculations - that has no effect in comparing growth because log 2 is a const. ?

[FlagstoneFiend]

yes. that's the idea

[DarkTrunksGeorgeSim]

why do they have to write too much on the blackboard...serously that's why we have books.

[Aiden057]

Thank you for making this available!

[miketwo345]

FYI: The Lecture starts at 17:10

[lani0]

thanks

[insightllc]

@miketwo345 Lester C. Thorow, Dean, Sloan School of Mgmt., MIT -- is a member of the Trilateral Commission and knows 33rd degree secret is the 1899 Alaska Earthquake - British Association record No. 333, at Shide. Isle of Wight on September 3 at three o' three.

[Vindex27]

@miketwo345 Thank you. 

[colmoneill83]

@miketwo345 Haha thx m8 i noticed your comment at about 2 mins in, you saved me 15 mins :) thumbs up :P

[Brucy6666]

@miketwo345 thanks :)

I got 6:00 in and thought... wait a sec, im not attending the course, when does the lecture start :P

[sharperguy]

What were they laughing at at 0:28:21?

[GoukiTehPwner]

He shook his head, so I'm thinking a student was goofing off behind him or something.

[tsatsa12]

i did the first algorithm when i was 17 at school at Greece ,i thought MIT things would be harder

[LearningAutomata]

So you want them to start right away by explaining NP-completeness??

This is an introductory course.

[mpleportals]

This guy doesn't seem too friendly...

[John4660]

Well i think i know where my hard earned tax dollars are going. Um and Ahhh is his perequisit for the course! This reminds me of an orientation i once attended. It was long and boring as well. They will never post an actual intelligent training video, one in which you can actually learn from.

[dwgila]

wow cant believe I'm not paying to see this O.O

[Hurze]

every "AAAAHM" before each sentence is really annoying... but I like the whole idea of spreading lessons on the web.

So jealous of the 80 min video upload!!!!