CMPT 307 Text Book Chapters Covered, Spring 2021
Text Book: Introduction to Algorithms by T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
(The MIT Press, 2009). Six lecture slides have been posted at the course website (more may
come later). Below are the book chapters covered in the posted slides.
• Lec1, Foundations
Roles of algorithms (Chapter 1)
Design and analysis of algorithms (Chapter 2)
Big-Oh notation and growth of functions (Chapter 3)
Divide-and-conquer algorithms and recurrence analysis (Chapter 4)
Randomized algorithms and average case analysis (Chapter 5)
• Lec 2, Sorting and Order Statistic
Heapsort (Chapter 6)
Quicksort (Chapter 7)
Lower bound on comparison based sorting (Chapter 8, Sec 8.1)
Sorting in linear time (Chapter 8, Sec 8.2-8.4)
Median and order statistics (Chapter 9)
• Lec 3, Data Structures
Elementary data structures (Chapter 10)
Hash tables (Chapter 11)
Binary search trees (Chapter 12)
• Lec4, Advanced Design and Analysis Techniques
Dynamic programming (Chapter 15)
Greedy algorithms (Chapter 16)
Amortized analysis (Chapter 17)
• Lec 5, Advanced Data Structures
B-trees (Chapter 18)
Fibonacci heaps (Chapter 19)
Data structures for disjoint sets (Chapter 21)
1
• Lec 6, Graph Algorithms
Preliminaries (Chapter 22)
Elementary graph algorithms (Chapter 22)
Minimum spanning trees (Chapter 23)
Single-source shortest paths (Chapter 24)
All-pairs shortest paths (Chapter 25)
2




































学霸联盟