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

	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]