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