CSE 326: Data Structures, Summer 2003
 CSE Home About Us Search Contact Info

 Main page Administrative Knowledge Pre and Postconditions Using Course Email Course Announcements Archive Course Discussion Archive Academic Accomodations Anonymous Feedback Course Content Calendar & Lecture Slides Quiz Section Exam Information Assignments Policies Grading Programming Guidelines Written HW Guidelines Collaboration Computing Computing Info Turnin Info

### 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):
• 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
• 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

 Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse326-staff@cs.washington.edu]