CR: COMP 2402 Learning Objectives

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 1405
• COMP 1406.

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.

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, ...