Module: Abstract data types

Stacks, queues, lists, trees, dynamic sets, pointers and objects, rooted trees, asymptotic analysis.

Learning Outcomes

Understand definition, implementation, and behavior of abstract data types.

Gain further practice in algorithm analysis through examination of stacks, queues, lists, and trees.

Readings

Stacks, queues, and lists

Basic abstract data types.

Screencast Suthers 28 min

Trees and dynamic sets

More on abstract data types.

Screencast Suthers 16 min

CLRS 10 - Elementary Data Structures

Stacks, queues, linked lists, pointers and objects, rooted trees.

Textbook 21 pages

Chapter 4 Notes

Introduction to abstract data types

Notes

Experiential Learning

Asymptotic analysis: Homework

Practice asymptotic analysis.

Homework

Battle of the Dynamic Sets

Provide four implementations of the Dynamic Set ADT and compare their performance.

Programming