Calender Description

2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

Assumed Background

COMP 1805
COMP 1406.

Learning Objectives

This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be

The Java Collections Framework
Complexity analysis - Big Oh notation.
Basic data types: sets, lists, stacks, queues, deques
Array-based implementations of basic data types
Linked-list based implementations of basic data types
Ordered sets - balanced binary search trees, skiplists
Basic Lower Bounds: Searching and Sorting
Dictionaries - hash tables
Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

Topics

Java: The Java Collections Framework: Interfaces and Implementations
Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
Linked lists
Hash tables
Skip lists
Complexity Analysis: Big O, Theta
Binary search trees: Red-Black Trees
Treaps and Scapegoat Trees
Heaps, Randomized meldable heaps
Mergesort and sorting lower bounds
Applications: Plane sweep, Convex Hull, ...