CSSE 230: Session Notes - Day 13

Topics

1. Ammortized analysis of algorithms
2. Abstract Data Types
3. Binary Heaps
4. Priority Queues

Outline

1. [5 min] Contact before work
2. [10 min] A closer look at Java's ArrayList data structure, in particular at adding elements.
3. [15 min] Introduction to amortized analysis of algorithms. Analyis of adding to an array. Why we should double the array when we resize it.
4. [10 min] Abstract Data Types.
5. [5 min] Break
6. [20 min] Introduction to Binary Heaps.

Resources

• Notes on amortized analysis.
• A video narrating the slides on ammortized analysis
• Sample code where we implement a queue through an ArrayList and a Stack through a Queue, highlighting what ADTs are all about.
• A video narrating the slides for MinHeaps
• A min heap visualization

Homework

• Day 15, BC: Submit your answers to the amortization homework Please submit a pdf copy of your work and please place your name near the top of your document. Submissions that do not satisfy these two constraints will not be graded. Thank you.