CR: COMP 2402 Learning Objectives: Difference between revisions
| Line 7: | Line 7: | ||
*COMP 1405 | *COMP 1405 | ||
*COMP 1406. | *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. | |||
=Prerequisite= | |||
COMP 1805 and COMP 1406 | |||
=Learning Objectives= | =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 | 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 | * The Java Collections Framework | ||
Revision as of 17:25, 22 March 2011
Calendar Description
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.
Prerequisite
COMP 1805 and 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, ...