To Dr. Woit's HomePage

To CPS305 Course Management Form

To CPS305 Topics

Course Directory

To CPS305 Announcements

# Outline/Readings CPS305: Data Structures

## Dr. Woit

Check page periodically for modification.

__Text__: __Data Structures, Algorithms & Software Principles in C__. by Thomas A. Standish. Addison Wesley, 1995

### Potential Topics (subject to change):

Note:

Ci means Chapter i in the text.

Ci.k means Section k of Chapter i in the text.

Wj means covered in Week j (j=0..11).

Introduction to Course [W0]
Course Administrative Information
Use of C and Linux

Data Structures and C Review (C1, C2) [W1]
Introduction to Data Types and Structures
Pointers
Structures
Dynamic Memory Allocation
Examples using Simple Linear Lists

Recursion (C3, C14.1, C14.2) [W2]
Call Traces and Call Trees
Divide-and-Conquer Decompositions
Tail Recursion
Infinite Regress
Simple Analysis
Dynamic Programming

Complexity (C6--except cover "Analysis of Mergesort [pg 236-240] under Sorting below) [W3]
Complexity Classes
Big-O Notation
Time Complexity
Space Complexity
Complexity Trade-offs

Test 1 [W4]

Lists (C7, C8.1-C8.2) [W5]
Single-linking
Multiple-linking
Stacks
Queues
Dequeues
Applications

Trees (C9.1-C9.4, C9.6-C9.8) [W6-W7]
General Trees
Binary Trees
Binary Search Trees
AVL-Trees

Test 2 [W8]

Trees Ctd (C9.5, C9.9-C9.11) [W9]
B-Trees
Tries
Huffman Codes (and Greedy Algorithms)
Heaps
Analysis and comparison

Hashing (C11) [W10]
Basic Concepts
Hashing Functions
Collision Resolution

Sorting (C13) [W11]
Divide-And-Conquor Methods
Insertion-Based Methods
Address-Calculation Methods
Priority-Queue Methods
Other sorting
Analysis and Comparisons

Graphs (C10) [W12]
Introduction
Representations
Searching
Topological Ordering
Shortest Paths
Task Networks
Applications

To Dr. Woit's HomePage

To CPS305 Course Management Form

To CPS305 Topics

Course Directory

To CPS305 Announcements