Date: Tue, 10 Dec 1996 16:48:51 GMT Server: NCSA/1.4.2 Content-type: text/html
Chapter 1 Abstract data type. Data structure. Encapsulation. Chapter 2 Sets: notation, standard operations, Cartesian product. Linear order (also called total order). Permutations, factorial, Stirling's formula. Generating random permutations in C++ (e.g., see p22). Boolean variables, floor and ceiling, modulus operator. Logarithms and their properties. Recursion, recursive factorial in C++, recursive Towers of Hanoi. Summations and recurrences, sum of first n integers. Sum of first n squares, Fibonacci sequence. Proof by contradiction. Proof by induction. Chapter 3 Running time formulations in terms of input size n and constants: e.g., T(n) = cn. Largest value sequential search in C++ (e.g., see p43). Constant, linear, quadratic, cubic and exponential running times. Big-Oh, big-Omega, and big-Theta definitions, notations. Simplifying big-Oh expressions. Calculating running times of programs. Binary search. Ordering functions by their growth rates. Chapter 4 Lists and the ADT on p81. Comparison of array and pointer implementations of lists. Freelists, doubly linked lists. Stack ADT, Queue ADT. Chapter 5 Binary tree, depth, height, full binary tree, complete binary tree. Full binary tree theorem. Binary tree node ADT (e.g., see p126). Preorder, inorder, and postorder traversal. Space requirements for pointer-based impl. of binary trees. Array implementation for complete binary trees. Huffman trees, encoding and decoding with Huffman trees. Prefix property of codes, efficiency of a Huffman code. Binary search tree property. Searching for an element in a BST (the find and findhelp methods). Insertion and deletion in a BST. Heap data structure and its use in implementing the priority queue. Siftdown and Buildheap operations. Time required to build the heap. Chapter 6 Parent pointer implementation of general trees. Implementation of FIND and UNION operations. Path compression. Chapter 7 Terminology for graphs. Comparison of adjacency matrix and adjacently list implementations.Last updated 25 October 1996 by S. Tanimoto