6. Randomization: Matrix Multiply, Quicksort

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Srinivas Devadas

In this lecture, Professor Devadas introduces randomized algorithms, looking at solving sorting problems with this new tool.

License: Creative Commons BY-NC-SA

[o.y.]

1:19:43 when my professor sees me entering the classrom

[seancolandrea]

coming to this from 6.006 feels like martin scorsese directed this

[huecountstudio]

MIT has some quality professors, damn. This was very helpful, thank you

[adityasanthosh]

"So If You're going to do the same thing again and again, and expect different results, That's called Insanity"

[cybernagle]

randomize quick sort & analysis: 1:07:57

[shah.kairav]

Wasn't the professor correct in making the jth value 1 instead of the ith value as pointed out by one of the students?

[ninjacod]

Hi Guys,

How different is this course comparing to the Introduction to Algorithms class taught by him?

[evanpiermont]

What is the collection of r vectors? Doesn't the 1-1 mapping argument require that your set of vectors (the support of the randomization) is close under addition by v. But without knowing v ahead of time, this might require an infinite set of vectors, in which case a bijection is not enough to guarantee equal measure between sets.

[imaddinamsif]

i don't know why i am from spain :( I looked exams from MIT, which were published on official web page and i like it.... Professor? I like how they are proposing some problems and how they teach, This life is not fair, but I will do everything possible to finish and do a master at MIT

[andrasviczian]

Couldn't you just make r a vector of n ones? Then if D is actually all zeros it would give the right answer, and if D has a one at any place it will also give the right answer.

[ChaojianZhang]

This 1080p lecture recording is awesome.

[veraBeStnews]

Does someone know which book he mentions? CLRS

[maashaz]

feels bad that my professor just copy pastes from MIT
i dont know why i pay for school...

[shahsadponnad]

i didnt understand why every one laughed when the student said '"t" .did I miss anything

[jimmypi]

anyone understand their joke about : probably correct and probably fast algorithm?

111
00:06:56, 144 --> 00:06:57, 560
which means that
they're incorrect

112
00:06:57, 560 --> 00:06:59, 560
and slow some of the time.

113
00:06:59, 560 --> 00:07:00, 100
Right?

114
00:07:00, 100 --> 00:07:03, 900
So what do you think those
algorithms are called?

115
00:07:03, 900 --> 00:07:04, 400
Sorry.

116
00:07:04, 400 --> 00:07:05, 222
What?

117
00:07:05, 222 --> 00:07:06, 580
AUDIENCE: T?

118
00:07:06, 580 --> 00:07:07, 610
SRINIVAS DEVADAS: The T?

119
00:07:07, 610 --> 00:07:08, 130
Oh.

120
00:07:08, 130 --> 00:07:08, 330
Oh!

121
00:07:08, 330 --> 00:07:09, 500
That deserves a Frisbee.

122
00:07:09, 500 --> 00:07:10, 700
Oh my goodness!

123
00:07:10, 700 --> 00:07:11, 980
[LAUGHS] All right.

[TheEmeraldSwordAxe]

These instructors teach the same class again and again, why cant they write without looking at their notes. It seems that if you take away their notes they will be helpless.