|
|
|
|
|
Course Syllabus
The purpose of this course is to teach fundamental abstract data
types, their implementations as data structures, and asymptotic
analyses of algorithms involving these data structures.
Knowledge Preconditions
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
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
Skills
- programming skill in Java
- familiarity with creating, manipulating, and editing files within
the framework of a multiuser timesharing system (unix)
Knowledge Postconditions (tentative)
Concepts
- abstract data types (ADTs) vs. implementations
- asymptotic complexity analysis of data structures and algorithms
- priority queue abstract data type, and its implementations
- partially ordered trees
- heaps and heapsort
- 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)
- sorting
- mergesort
- quicksort
- decision trees and the lower bound
- adjacency list and adjacency matrix representations of graphs
- Dijkstra's algorithm for single source shortest paths
- disjoint union-find
- up-trees with weighted union
- find with path compression
- Kruskal's and Prim's algorithms for minimum spanning tree
- Tentative :: Basics of algorithm design
- Greedy algorithms
- Divide and Conquer
- Dynamic Programming
- Tentative :: Basics of complexity theory: P vs. NP
Abilities
- specify an abstract data type for a given application
- design, analyze, and compare implementations
Skills
- robustness and clarity in programming
- familiarity with UNIX
|
Main Page 
