Fall 2002, CS 251: Data Structures
Walid G. Aref
See the academic dishonesty policy before you start!
Course Overview
This course covers concepts and analysis of data structures using object oriented design principles and Java as the implementation language. The assignment of topics to weeks is approximate.
Click on "Textbook" above for textbook information.
Topics to be covered include:
Design Principles (Ch.1,2). Data structures and algorithms.
Analysis tools and techniques (Ch.3): asymptotic analysis, big-O notation, loop invariants; mathematical and structural induction.
Stacks, queues, and linked lists, including double-ended queues (Ch.4).
Sequences (Ch.5): Ranked, positional, and general sequences.
Binary trees (Ch.6): representations, traversals, properties, recursive procedures for computing tree functions.
General trees (Ch.6): representations, traversals, properties, example applications.
Priority Queues (Ch.7): ADT, implementations based on linked lists and arrays, heap as a data structure.
Dictionaries (Ch.8): ADT, simple implementations, binary search trees, hashing.
Balanced search trees (Ch.9): AVL, red-black, (2,4) trees; insertion and deletion procedures; Applications of balanced search trees beyond dictionaries.
Sorting, Sets, and Selection (Ch.10).Merge-sort, quick-sort, lower bound on
comparison-based sorting, bucket-sort, radix-sort.Disjoint Sets: array and linked list implementations, tree representations with weighted Union and path compression; amortization.
Introduction to graphs (Ch. 12): representations, traversals, directed versus undirected graphs, basic operations; Graph algorithms: shortest paths and minimum-spanning trees.
Selected topics: multi-dimensional search trees, range trees, tries, memory management, external searching and sorting.