Outline/Readings CPS305: Data Structures

M. Soutchanski

Fall 2005

Check this page periodically for modification.

Text: Data Structures & Program Design in C. Second Edition. Authors: Kruse, Tondo and Leung. Prentice-Hall, 1997. ISBN 0-13-288366-X

Potential Topics: (subject to change).

Note: Ci means Chapter i in the text.

Programming Principles and Intro to Soft. Eng. (C1 &C2 except GOL details) (approx 1 week)

Introduction

Style

Coding, Testing, Refinement (stubs, drivers, program tracing, testing)

Maintenance

Algorithm Development (information hiding, modularity)

Coding (Simple List)

Program Analysis and Comparison

Stacks and Recursion (C3, except C3.3) (approx 2 weeks)

Stacks ADT

Contiguous

Linked

Introduction to Recursion (stack frames for subprograms, tree of calls)

Divide and Conquer

Principles of Recursion (tail recursion, iteration vs. recursion)

Queues, Pointers and Linked Lists (C4, except C4.4 and C4.7) (approx 1 week)

Queues ADT

Contiguous (linear and circular) queues

Pointers and Linked Lists

Linked Queues

ADT definitions (Section 4.8)

General Lists (C5 except C5.3, C5.4, C5.5, C5.6) (approx 1 week)

General Lists ADT (vs. restricted lists ADTs)

Contiguous

Simply linked and doubly linked

Comparison of Implementations (contiguous vs. linked)

Searching (C6 except C6.3) (approx 2 weeks)

Sequential

Binary Search

Lower Bounds and Asymptotics

Applications

Sorting (C7 except C7.4, C7.9) (approx 2 weeks)

Insertion Sort

Selection Sort

Divide-and-Conquer Sorts

Mergesort

Quicksort

Complexity analysis of sorting algorithms

Comparisons

Hashing (only C8.6, C8.7 and C8.4 ) (approx 1.5 weeks)

Tables

Hashing Methods

Analysis

Trees (C9 except 9.3, 9.5,) (approx 2 weeks)

Binary, AVL

Graphs (only C11.1, C11.2 and C11.3)

Depth-First and Breadth-First Algorithms

CPS305 Course Management Form
CPS305 Announcements
Course Start Page