ON THIS PAGE:

Course Objectives

Prerequisites

Approach

Typical Text

Course Outline

Course Objectives
To provide a toolbox of useful data structures, implementations, and associated algorithms

Prerequisite
COMP 401

Approach
Practical data structures of broad applicability are emphasized along with the bases for choosing and designing data types appropriate for a given task.

• Introduce and develop the concept of abstract data types.
• Describe a collection of abstract data types and, for each type, describe a collection of implementations. Verify implementations in a semi-formal way.
• Analyze the time and space requirements of various implementations.
• Examine a variety of internal sorting algorithms.

Typical Text
Aho, Hopcroft, and Ullman, Data Structures and Algorithms
Augenstein and Tenenbaum, Data Structures Using Pascal
Horowitz and Sahni, Fundamentals of Data Structures

Course Outline

Concepts (also interspersed throughout course) (2)

• Data Abstraction
• Program correctness (verification)
• Algorithmic complexity (order notation)

Stacks and Queues (1)

Lists (2)


• Array implementation
• Linked lists, priority and event queues
• Matrices: sparse, triangular, and band
• Generalized lists
• Garbage collection

Trees (2)


• Binary trees, including traversal
• Balanced trees
• Set implementations using trees

Graphs (1)

Searching (2)


• Tree search
• Hashing

Sorting (2)


• Binary treesort
• Heapsort, quicksort, and mergesort

External Data Structures (1)