Date: Tue, 10 Dec 1996 16:48:51 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 373 Midterm topics

CSE 373 Midterm topics

The midterm examination on Wednesday, October 30 will cover the following topics. Nearly all of these are covered in the text in the associated chapters.

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