CR: COMP 2402 Learning Objectives: Difference between revisions
| (14 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
= | =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= | =Assumed Background= | ||
COMP 1805 | *COMP 1805 | ||
*COMP 1406. | |||
*MATH 1007 | |||
*MATH 1104 | |||
=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 | |||
* 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= | =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, ... | |||
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, ...