C S 2413 Data Structures

Catalog description

Object-oriented representation of widely used data structures and associated algorithms. The design of medium-size software systems. Written communication required in some projects. Discussion of ethical issues including computer crime, abuse, and hacker ethics.

Prerequisites

C S 1333 and C S 1813.

Audience

Sophomore computer science majors and majors pursuing the computer engineering option or computer science option.

Frequency

Three times a year during fall, spring, and summer semesters.

Format

Lecture, three hours per week.

Laboratory

A number of programming assignments will be given.

Recommended texts

  • Computers, Ethics, and Social Values, Deborah Johnson, 2nd edition, Prentice-Hall, 1994.

    Supplementary texts

    None.

    Typical schedule of topics

    1. Introduction
      1. algorithm design
      2. performance measurements
    2. Fundamental data structures
      1. operations
      2. object-oriented representations
    3. Search trees
      1. 2-3 trees
      2. red-black trees
      3. splay trees
      4. optimal binary search trees
      5. multidimensional search trees
      6. suffix and Patricia trees
    4. Priority search structures
      1. priority search trees
      2. min-max heaps
      3. deaps
      4. binomial and Fibonacci heaps
    5. Hashing
      1. open addressing
      2. static and dynamic hashing
      3. perfect hash functions
    6. Sorting
      1. comparison-based sorting
      2. sorting - lower bound
      3. adaptive sorting
      4. external sorting
    7. Graphs
      1. representations and basic operations
      2. minimum-cost spanning trees
      3. union-find data structure
      4. shortest path and transitive closure
    8. Further topics
      1. skip lists
      2. quad trees
      3. grid files
    Data Structures / Course descriptions / OU School of Computer Science / 22 August 2000