Revision as of 15:45, 10 March 2011

Calendar Description

Assumed Background

Learning objectives completed before this course. 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.

Detailed List

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

@@ Line 22: / Line 22: @@
 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.
+=Detailed List=
 * Java: The Java Collections Framework: Interfaces and Implementations
 * Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks