CS14  Final Topics 

Running times and complexity.
-----------------------------
- Big-Oh notation; determining the running time of code segments;
- comparing program performances.

Recursion.
----------
- determining the output of a recursive function.  Writing recursive
  functions. 
- recurrence relations -- what they are, how to solve (substitution
  until you see a pattern)

Lists 
-----

Stacks
------ 
  
Queues 
------
  
Hash tables
-----------

Trees 
-----
- general terminology: root, leaves, internal nodes, path, child,
  parent, height. 

Binary trees 
------------
- structure of a tree node
- special trees: full, complete
- relation between heigh, number of nodes, number of leaves
- traversals (inorder, preorder, postorder)
- instances of where each traversal is used (preorder to copy, inorder 
  for visiting bst nodes in order, postorder in evaluating expression trees)
- representation of general trees using binary tree node strucure 
  (first child, next sibling)
 
Expression trees 
----------------
- binary trees
- operands at leaves, operators in internal node
- evaluating expressions: by combining leaf nodes; by postorder
  traversal then stack. 
     
Binary search trees 
-------------------
- basic properties
- operations: insert, remove, search, ...
- height of BST: average case, worst case.
- running time of tree operations
- implementation issues
- uses of BSTs: data storage, tree sort.
- balanced tree structures (AVL, 2-3, red-black: know they exist)

Heaps
-----
- structure
  - full binary tree (all full rows, last row full from left)
  - parent always larger that either child
- operations
  - buildheap, insert, extractmax, reheap
  - time bounds on operations:
    buidheap O(n), insert, reheap, extractmax O(lgn)
- how stored 
  - in an array, starting from cell 1
  - parent in cell I, children in 2i, 2i+1.
  - count in cell 0

Sorting
-------
- selection sort
- insertion sort
  - sorting with a linked list (insertion sort) 
- Shell sort
- sorting with a binary search tree
  - inserting one by one into the tree, then inorder traversal
- sorting with a heap:
  - inserting one by one into a heap, then a sequence of extract max
  - one buildheap, then a sequence of extract max
- quicksort
  - methods for improving performance of
    - random pivot
    - median of three pivot
    - cutting off recursion and substituting insertion sort for 
      small array size
- merge sort (need extra space)
  - top down (recursive)
  - bottom up
- bucket sort
- radix sort
  - start with least significant digit (units)
- properties of the different sorting algorithms
  - advantages and disadvantages of the different sort methods, 
  - which are suitable for what kind of data
  - worst case and average case time bounds for each

Graphs
------

- definition
- terminology: vertices, edges, paths, connected, directed, weighted
- representations: adjacency list, adjacency matrix
- traversals: depth first (recursive) breadth first (use queue)
- spanning trees
- minimum spanning trees
- shortest path

Searching
---------
- sequential search
- binary search
- searching in a BST

C++ Issues
----------
- classes, objects and methods
- dynamic memory allocation
- recursive functions
- compilation and makefiles
- STL
- exception handling