CR: COMP 2402 Learning Objectives

Assumed Background

• COMP 1805
• COMP 1405
• COMP 1406.

Learning Objectives

[Based on Pat Morin's offering of COMP 2402 in Fall 2010] 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, ...