|
|
|
|
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
- 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
|