R1. Matrix Multiplication and the Master Theorem

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Ling Ren
In this recitation, problems related to matrix multiplication and weighted interval scheduling are discussed.
Chapters
00:00 Title slate
00:20 Recitation intro
02:16 Weighted Interval Scheduling
22:40 Strassen algorithm
33:13 Master Theorem
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@kimhammar]

Master Theorem 33:10

[@klejdisevdari3916]

This comment saved me so much time. Thanks

[@gerardorigas6812]

This was great, thanks, I have been researching "geologic time scale calendar activity" for a while now, and I think this has helped. You ever tried - Bannrial Bizarre Bulldozer - (should be on google have a look ) ? It is a smashing exclusive product for discovering your spiritual animal and the clues it has to your future success without the normal expense. Ive heard some incredible things about it and my partner got excellent success with it.

[@maverickpierce3090]

instablaster...

[@halfEnlightenedOne]

02:16 Weighted Interval Scheduling
22:40 Strassen algorithm
33:16 Master Theorem

[@Karim-nq1be]

I really enjoyed the way the instructor was explaining, thank you.

[@pkatmusic5800]

I think after viewing Professor Gilbert Strang's video lecture on matrix multiplication, you won't ever forget it. I mean it. 🙂🙂🙂

[@abijithbahuleyan785]

Does he explains Strassen's Algo

[@mytennisjourney4949]

Thanks! I always have no feeling about master theorem, now I understand to prove process, it makes more sense for me. Another way to think about this, the recursion tree can prove the master theorem, so it can solve all concrete problem.

[@sumitgupta1457]

Great video on master theorem

[@hektor6766]

Recitation is where things happen.

[@user-tn1yb1ne4e]

Graduted from QingHua(top university in CN) as a bachelor, this guy is brilliant.

[@AMANKUMAR-oh1zt]

Means he is a commie??

[@jackzeinder1705]

@@AMANKUMAR-oh1zt do you guys still have toilet?

[@AMANKUMAR-oh1zt]

@@jackzeinder1705 Aapke hote hue toilet ki kya zarurat hai? :-)

[@jackzeinder1705]

@@AMANKUMAR-oh1zt kya tum log ab bhee gaay ke gobar se dhote ho ? :)

[@lxu5148]

@@AMANKUMAR-oh1zt Then he may be able to put you inside?

[@williamkosasih6907]

this guy's very good in teaching

[@woodsker]

Strassen’s algorithm 22:30

[@degerahmet]

dude you are the man !

[@mingyang8183]

amazing teacher

[@chilily901]

Thanks! Great professor, learned a lot today ^^~

[@AndreyVarlamov]

Great vigeo. Thanks.

[@qin6409]

mit有华人不容易，且尊重且珍惜

[@peasant12345]

14:26 specifying wis(r1) needs log n comparisons in worst case. But the total complexity is still dominated by sorting part.

[@tanushmahajan3359]

22:34 Matrix Multiplication (Strassen)

[@amitsrivastava5690]

37:00 a is branching factor and base case.

[@dr.rahulgupta7573]

Nice presentation of the topics in a beautiful manner by an experienced teacher .Thanks .DrRahul Rohtak Haryana India

[@dunket777]

video is not clear at 29:57 the values of M6 in first bracket are not clear

[@pinusong]

看到了华人在 MIT讲课，厉害了，加油，大家都是优秀的人

[@bazingadmc720]

关于weighted interval scheduling有个疑问，通过i1的end time去找R1（start time在i1 end time之后的interval）不就需要O(n)的时间吗，并且递归过程中每一步都有这个计算过程。

[@peasant12345]

binary search will consume log n. Still safe to get n log n.

[@xinli6243]

the weighted interval scheduling. Why was the first alg n squared and second one just n? it takes constant time to computer R1？

[@rewolfer]

I also wondered about the cost of finding R1...

[@safoorayousefi3814]

I think Ling forgot to mention that cost. Having sorted the job array by start time, finding the next job whose start time is greater than the finish time of job_i can be done using binary search (O(logN)).

[@WeirdAlSuperFan]

Is finding the intervals in R the only reason the first algorithm is n^2? I feel like in both cases we're assuming R is constant time, but there's a different reason the unsorted algorithm is n^2, but I can't find an explanation anywhere on the internet or in textbooks

[@amornchotsingh3977]

Hello Everybody, I don't understand how this course works. There are lecture videos taught by the lecturers and also videos taught by students with prefix R1,R2,R3, etc. If I'm not wrong, are R1,R2 revision videos of official video 1 and 2? Or are they supplementary to the videos taught by the lecturer?

[@mitocw]

These supplementary videos are recitations. Recitations are a way for students to ask follow-up questions to anything that was confusing in lectures. For the full course materials, see the course on MIT OpenCourseWare at:ocw.mit.edu/6-046JS15. Best wishes on your studies!

[@yiran432]

So..... anyone can explain the philosophy of Strassen's method?🙂

[@bhaskarkurapati1907]

What I understood that Strassen was trying to reduce "a" in Master Theorem formula from 8 to 7 so that first condition n ^ (log a with base b) would result in n^2.8074 instead of n^3. I remember reading the idea in "Introduction to Algorithms" book that multiplication/division are expensive computational operations than addition/subtraction. "a^2 - b^2" (which involves two multiplications and one subtraction) can be computed with "(a + b) * (a - b)" (which involves single multiplication). Strassen used similar strategy to reduce matrix multiplications from 8 to 7.

[@zhanglei1032]

华人小哥？

[@Victor-yn6jm]

应该是中国人，清华毕业的

[@gerdhickl4991]

Test

[@mohamednofal5256]

asians are good

[@yuanchun9124]

[?Grady?] --> greedy =、= 3:21

[@RishabhKumar-sc8uz]

Bc video me dj mix Kra h

[@arindammandal7742]

faltu