CSE logo University of Washington Department of Computer Science & Engineering
 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):
    • 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


CSE logo 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]