CSE 326: Data Structures

Purpose:

Fundamental abstract data types and their implementations as data structures. Asymptotic analyses of algorithms involving these data structures.

Precondition Concepts:

• abstraction
  • modularity, encapsulation, information hiding
  • interface vs. implementation; multiple implementations of interface
  • language constructs: modules, user-defined data types
• simple abstract data types and their implementations
  • stacks
  • queues
• recursion
• simple data structures (representations):
  • linked lists
  • trees (including preorder, inorder, postorder traversals)
• simple analysis of running time
  • basics of big-O notation
  • comparison of implementations
• searching (sequential, binary)
• basics of discrete mathematics
  • sets and lists
  • relations and functions (injective, surjective, bijective)
  • modular arithmetic
• logarithmic, exponential, floor, and ceiling functions

Precondition Abilities:

• design and implement medium-sized programs (up to about 1000 lines), consisting of several (4-12) modules
• understand and extend medium-sized (500+ lines) programs
• read, write, use, and document (own and others') software components
• write clients, implementations separately, given spec of interface
• write simple proofs, including proofs by induction
• analyze the asymptotic running times of simple algorithms involving, e.g., nested loops

Precondition Skills:

• programming skill in C++ or Java
• familiarity with creating, manipulating, and editing files within the framework of a multiuser timesharing system.

Postcondition Concepts

• dictionary abstract data type, and its implementations
  • unsorted and sorted lists
  • binary search trees (without balancing)
  • balanced search trees: AVL trees and/or 2-3 trees and/or splay trees
  • hashing (separate chaining, open addressing, universal classes)
• priority queue abstract data type, and its implementations
  • partially ordered trees
  • heaps and heapsort
  • Dijkstra's algorithm for single source shortest paths
• disjoint union-find
  • up-trees with weighted union
  • find with path compression
  • Kruskal's algorithm for minimum spanning tree
• adjacency list and adjacency matrix representations of graphs
• sorting
  • mergesort
  • quicksort
  • decision trees and the lower bound

Postcondition Abilities

• specify an abstract data type for a given application
• design, analyze, and compare implementations

Postcondition Skills

• familiarity with UNIX