文档介绍：Design and Analysis of Algorithms: Course Notes
Prepared b y
Samir Kh uller
Dept. puter Science
Univ ersit y of Maryland
College P ark, MD 20742
******@
(301) 405 6765
April 19, 1996
Preface
These are m y lecture notes from CMSC 651: Design and Analysis of Algorithms , a one semester
course that I taugh t at Univ ersit y of Maryland in the Spring of 1995. The course co v ers core material in
algorithm design, and also helps studen ts prepare for researc h in the eld of algorithms. The reader will
nd an un usual emphasis on graph theoretic algorithms, and for that I am to blame. The c hoice of topics
w as mine, and is biased b ym y p ersonal taste. The material for the rst few w eeks w as tak en primarily
from the textb o ok on Algorithms b y Cormen, Leiserson and Riv est. A few pap ers w ere also co v ered, that
I p ersonally feel giv e some v ery imp ortan t and useful tec hniques that should b e in the to olb o xofev ery
algorithms researc her.
The course w as a 15 w eek course, with 2 lectures p er w eek. These notes consist of 27 lectures. There
w as one midterm in-class examination and one nal examination. There w as no lecture on the da y of the
midterm. No scrib e w as done for the guest lecture b y Dr. R. Ra vi.
Con ten ts
1 Ov erview of Course 3
Amortized Analysis :: :::: ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 3
2 Spla yT rees 5
Use of Spla y Op erations ::: ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 5
Time for a Spla y Op eration : ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 6
3 Amortized Time for Spla yT rees 8
Additional notes ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 11
4 Main taining Disjoin t Set's 12
Disjoin t set op erations: :::: ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 12
Data structure: : ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 12
Union b y rank : ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: ::: :::: : 13
4