MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees

author: Charles E. Leiserson, Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, MIT
recorded by: Massachusetts Institute of Technology, MIT
published: Feb. 10, 2009, recorded: October 2005, views: 6648
released under terms of: CC BY-NC-SA

Turn off the lights

You might be experiencing some problems with Your Video player.

Slides

Slides
0:00	Introduction to Algorithms - Lecture 11
1:47	Dynamic order statistics
4:09	Example of an OS-tree
8:47	Selection
13:14	Example
17:31	Data structure maintenance
22:49	Example of insertion
24:06	Handling rebalancing
29:23	Data-structure augmentation
36:46	Interval trees
41:01	Following the methodology
46:10	Example interval tree
50:14	Modifying operations
57:06	New operations
59:58	Example 1 (1)
64:09	Example 1 (2)
64:37	Example 1 (3)
65:08	Example 2 (1)
65:25	Example 2 (2)
65:38	Example 2 (3)
65:45	Example 2 (4)
66:25	Analysis
69:09	Correctness
73:04	Correctness proof (1)
78:13	Correctness proof (2)

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

"Good morning. Today we're going to talk about augmenting data structures. And this is a -- Normally, rather than designing data structures from scratch, you tend to take existing data structures and build your functionality into them. And that is a process we call data-structure augmentation. And this also today marks sort of the start of the design phase of the class. We spent a lot of time doing analysis up to this point. And now we're still going to learn some new analytical techniques..."

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

1 pavani, November 2, 2009 at 11:02 a.m.:

what is B-tree? and applications

2 Ozgur, June 13, 2011 at 1:18 p.m.:

ProgrammingPages.net - http://www.programmingpages.net
Best Programming Resources and Source Code Examples for Java, Php, Visual Basic, C++ ,Asp, Python, Javascript, Ada, Cobol ,C, C#, Delphi, Fortran, Logo, Ruby, Xml.
Programming E-Book, Video Tutorials, History, Algorithms and Faqs.

Write your own review or comment:

Comment
Name
Email address
URL

make sure you have javascript enabled or clear this field:

Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees

Slides

Related content

Report a problem or upload files

Description

See Also:

Link this page

Reviews and comments:

Write your own review or comment:

ENERGY CRISIS

BLOG ESSAY

LANGUAGE TECHNOLOGIES

INFO