CR: COMP 2402 Learning Objectives

From Soma-notes

Calendar Description

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

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