Latest revision as of 17:49, 11 April 2011

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.
MATH 1007
MATH 1104

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, the performance issues, both theoretical and practical will be discussed. 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, ...

@@ Line 1: / Line 1: @@
-=Calendar Description=
+=Calender Description=
+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=
@@ Line 5: / Line 8: @@
 *COMP 1805
-*COMP 1405
 *COMP 1406.
+*MATH 1007
+*MATH 1104
 =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
@@ Line 21: / Line 24: @@
 * 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.
+Along the way, the performance issues, both theoretical and practical will be discussed. 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=