Lectures (Video)
- 1. Introduction
- 2. Asymptotic Notation
- 3. Divide and Conquer
- 4. Quicksort
- 5. Linear-time Sorting
- 6. Order Statistics
- 7. Hashing I
- 8. Hashing II
- 9. Random BST
- 10. Balanced Search Trees
- 11. Augmenting Data Structures
- 12. Skip Lists
- 13. Amortized Analysis
- 14. Competitive Analysis
- 15. Dynamic Programming
- 16. Greedy Algorithms
- 17. Shortest Paths I
- 18. Shortest Paths II
- 19. Shortest Paths III
- 20. Review
- 21. Quiz
- 22. Advanced Topics I
- 23. Advanced Topics II
- 24. Advanced Topics III
- 25. Advanced Topics IV
Introduction to Algorithms - Lecture 9
|
Get the Flash Player to view video.
Lecture 9 - Random BST
Randomly built binary search trees: Expected node depth, Analyzing height (Convexity lemma, Jensen’s inequality, Exponential height) Post mortem
Prof. Erik Demaine, Prof. Charles Leiserson
6.046J Introduction to Algorithms (Massachusetts Institute of Technology: MIT OpenCourseWare) http://ocw.mit.edu Date accessed: 2008-11-23 License: Creative Commons BY-NC-SA |
Lecture Material
Get the Flash Player to view slideshow.
(Slides are displayed for 10 sec before advancing to the next slide. You can also navigate the slides manually by using the back and forward buttons. Clicking the slide itself will advance to the next slide.)
To download the above lecture material use this link. (Right-click and select Save Target As or Save Link As.)
