CS14a  Final Topics 

Running times and complexity.
-----------------------------
- Big-Oh notation; determining the running time of code segments;
- Omega, Theta -- know the definition.
- 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 
-----
- implementations: array, singly linked lists, doubly linked lists. 
- operations: inserting, removing, searching.
- advantages/disadvatages of the different implementations; time bounds for    
  operations in each.
- list traversal: sequential, can go only forward (sll) both ways (array, dll).
- dummy nodes and their uses.
- uses of lists: maintaining sorted data.
  
Stacks
------ 
- operations: push, pop, top, ...
- implementations: array, linked lists; advantages/disadvatages of each;
  time bounds for operations in each.
- uses of stacks: function calls, evaluation of postfix expressions,
  checking for balanced parentheses
  
Queues 
------
- operations: enqueue, dequeue, front, ...
- implementations: array, linked lists; advantages/disadvatages of each;
  time bounds for operations in each.
- uses of queues: printer queue, simulation of real life situations,
  e.g. line at a checkout lane.
  
Trees 
-----
- general terminology: root, leaves, internal nodes, path, child,
  parent, height. 
- structure of a tree node
- uses: binary search trees, expression trees.

Expression 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, ...
- tree traversal (preorder, inorder, postorder)
- height of BST: average case, worst case.
- running time of tree operations
- implementation issues
- uses of BSTs: data storage, tree sort.
- balanced tree structure (know they exist)

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

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

Hash tables
-----------
- used for quick lookup, dictionaries, spellcheckers
- hash functions
  - fast to compute
  - distribute data evenly
- collision resolution
  - open has tables with chaining (list operations)
  - closed hash table with open addressing
    - linear probing (problem: primary clustering)
    - quadratic probing (minor problem: secondary clustering)
    - double hashing
- table load factor (data size/table size)
  - > 1 for open hash table
  - < 1 for closed hash table
- rehashing (going to a bigger table when load factor is too high)
  - expensive but rare
- prehashing and perfect hash functions 
  - when dictionary is known in advance
  - extra effort up front to save in search time

Sorting
-------
- insertion sort
  - sorting with a linked list (insertion sort) 
- selection 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
- radix sort
  - start with least significant digit (units)
- bucket sort
- 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

C++ Issues
----------
- classes, objects and methods
- dynamic memory allocation
- deleting lists through node destructors
- references to pointers - when used
- recursive functions
- exception handling