Location: Academic Organisations » OpenCourseWare Consortium » MIT OpenCourseWare » MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

event thumbnail image

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
published: Feb. 10, 2009, recorded: October 2005, views: 697

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)

Related content

Visitors who watched this lecture also watched...

Lecture 10: Red-black Trees, Rotations, Insertions, Deletions
3191 views - Erik Demaine, 2005

Lecture 12: Skip Lists
530 views - Erik Demaine, 2005

Lecture 9: Relation of BSTs to Quicksort, Analysis of Random BST
592 views - Erik Demaine, 2005

Lecture 15: Dynamic Programming, Longest Common Subsequence
2036 views - Charles E. Leiserson, 2005

Lecture 16: Greedy Algorithms, Minimum Spanning Trees
1682 views - Charles E. Leiserson, 2005

Lecture 13: Amortized Algorithms, Table Doubling, Potential Method
593 views - Charles E. Leiserson, 2005

Lecture 6: Order Statistics, Median
927 views - Charles E. Leiserson, 2005

Lecture 7: Hashing, Hash Functions
1021 views - Charles E. Leiserson, 2005

Lecture 14: Competitive Analysis: Self-organizing
302 views - Charles E. Leiserson, 2005

Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
3966 views - Erik Demaine, 2005

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..."

See Also:

Download slides icon Download slides: mit6046jf05_leiserson_lec11_01.pdf (305.3 KB)

Launch Windows Media Player Launch in a standalone WM Player

WMedia Player Switch to Windows Media Player

Download Flash video Download mit6046jf05_leiserson_lec11_01.flv (Flash video 236.2 MB)

Download mp4 video Download mit6046jf05_leiserson_lec11_01.m4v (mp4 video 175.2 MB)

Download Real media video Download mit6046jf05_leiserson_lec11_01.rm (Real media video 134.0 MB)

Download Windows Media video Download mit6046jf05_leiserson_lec11_01.wmv (Windows Media video 727.1 MB)

Download audio transcript Download mit6046jf05_leiserson_lec11_01.mp3 (Audio transcript 19.3 MB)

Help icon Streaming Video Help

WebLink icon Windows Media Player Firefox Plugin - Download

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:

Comment

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

what is B-tree? and applications

Write your own review or comment:

Comment
Name
Email address
URL

make sure you have javascript enabled or clear this field: