5. Amortization: Amortized Analysis

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Erik Demaine

In this lecture, Professor Demaine introduces analysis techniques for data structures, and the implementation of algorithms based on this analysis.

License: Creative Commons BY-NC-SA

[alexandrebrownAI]

Timestamps:
- 0:20 : Introduction, Usefulness of Amortized Analysis
- 1:41 : Table Doubling Problem with Intuition on Amortized Cost
- 5:42 : Aggregate Method
- 7:18 : General Definition of Amortized Bounds
- 14:02 : Accounting Method
- 22:22 : Table Doubling Problem using Accounting Method
- 27:57 : Charging Method
- 31:00 : Table Doubling Problem using Charging Method
- 42:11 : Potential Method
- 48:52 : Binary Counter Problem using Potential Method
- 56:00 : Insert in 2-3 Trees using Potential Method
- 1:04:21 Insert & Delete in 2-5 Trees using Problem Method

[emmafoley]

The best explanation of potential amortization I've found!

[imprsnt]

Load Factor = number of Elements / Size of table = n / m.

[DenisG]

11:51 But that's not entirely true, since you can "try" removing an item, which is not in the tree, which will still cost O(logN) in order to look for the item, which is missing.
Correct me if I'm wrong

[ChadieRahimian]

This is the only data structure lecture of MIT, I didn't understand a word of :((

[forthrightgambitia]

Interesting, I studied B-trees at uni and they presented the 2, 5 tree without justification of those numbers. But here it is.

[tkjyxrb]

I got the idea of amortization in general, but these coins are totally weird. Why the heck do we charge back in time only once per insertion?

[hritikzurange]

thanks for the charging method, makes life much easier :)

[arno.claude]

11:08 why did he throw that frisbee? :D is it a reward for answering a question correctly? :D

[avoriginal]

so for the accounting method you are adding 2 coins for each insertion, 1 insertion costs 1 coin and you store one to be able to pay for the deletion?

[radred]

shoutouts to any students at uvic cramming for an exam right now

[Sacheess]

51:44 does he give frisbees for answers? So fucking cool.

[jawoo]

huhuhhh, Mr Van Driessen's cool...

[sydneystriker]

The last lecture was so hard that this lecture seemed piece of cake. :)

[JuanSanchez-yiwn]

At 39:00 Can I use this for Crypto asset valuation? Specifically BTC since BTC white papers solves double spending problem

[hossein_haeri]

Misleading words... Hard to get the core concept... I kinda think those people sitting there already knew the concept which is no surprise at MIT!

[thinkweb]

I love Eric's explanations but this one felt way too theoretical. I wish he started with examples and used these techniques before diving into nitty gritty.

[shivanshpachauri]

i feel Eric to be too less energetic in this video.

[es]

i dont understand shit i fucking hate computer science

[sudipandatta]

this is the most boring lecture of mit