Department of 
Computer Science

Search our Site

Line

ON THIS PAGE:

Course Objectives

Prerequisites

Approach

Typical Text

Course Outline

  COMP 410 [121]: Data Structures
(3 hours)

Syllabus approved 16 March 1984

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)

Horizontal Line
Department of Computer Science
Campus Box 3175, Sitterson Hall
College of Arts & Sciences
The University of North Carolina at Chapel Hill
Chapel Hill, NC 27599-3175 USA
Phone: (919) 962-1700
Fax: (919) 962-1799

Content Manager: Associate Chairman for Academic Affairs
Server Manager: webmaster@cs.unc.edu
Last Content Review: 7 November 1995