Difference between revisions of "CR: COMP 2402 Learning Objectives"
Jump to navigation
Jump to search
(→Topics) |
|||
| 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. | 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 | * Java: The Java Collections Framework: Interfaces and Implementations | ||
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks | * Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks | ||
Revision as of 11: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, ...