Topics covered on Midterm

Java syntax and semantics that we have learned (as done in your assignments)
reference types vs. primitive types
class structure (fields, methods, constructor)
static vs dynamic fields 
access control modifiers like public, private

Expressing ADTs in Java
abstraction in Java
encapsulation in Java

static vs. dynamic memory management
Runtime stack (call stack)
Runtime heap 
Recursion
garbage collection



List data structure
  general ops: get kth item
               insert at slot k
               delete at slot k

implementing lists:
  as array
  as linked cells

Ordered lists are especially nice
order information can assist in list searching
binary search can find an item in O(log N) time worst case
understand binary searching in an ordered sequence
this only works efficiently though if you can find the middle of the sequence in O(1) time
(like addressing an array subscript)
         
special lists:
  Stack
    general ops: push, pop, top, empty, size
    keep pointer to most recent slot (t)
    push is insert at slot t
    pop is delete from slot t
    push, pop are O(1) since we access the top slot ddirectly via pointer
      no searching through the list, no rearrangement of locations
      this applies to implementations by links or array
    
  Queue
    general ops: add, remove, front, empty, size
    keep pointers to front slot, back slot
    add is insert at slot front
    remove is delete from slot back
    add, remove are O(1) since we access the slots directly by pointer
      no searching through the list, no rearrangement of locations
      this applies to implementations by links or array



Bubble sort
  O(N^2) time required to sort list of N items
  pro: easy to program
  con: very slow, useless for sorting lists of any serious size


Tree data structure in general (n-ary tree)

Binary Tree data structure
  Any n-ary tree can be represented as a binary tree

Binary Search Tree
  order property: all nodes in left child subtree have smaller
                  value than root, all nodes in right child subtree
                  have values greater

traversals:
  in-order, pre-order, post-order
    in-order gives sorted list from a BST
    pre-order, post-order give lists dependent on tree structure
  breadth-first

implementing a BST (and binary tree in general) as linked cells
  

BST Sort
  Not a real sorting algorithm name, but a way to remember that sometimes
  fairly efficient way to sort a list is to first build a binary search tree,
  then traverse it in the proper way

  Average case analysis:
    1) build a BST from the list: O(N log N)
         one insert in a BST: O(log N) for tree with N elments
         doing N inserts: O(N log N)
    2) in-order traversal to get the sorted order of elements
         O(N) since we have to visit each of the N nodes in the BST
    So total avg case time complexity is
       O(N log N) + O(N) which is O(N * (1 + log N))
                         which is O(N log N)
  Worst case analysis:
    1) build a BST from the list: O(N * N) is O(N^2)
         one insert in a BST: O(N) for tree with N elments
         doing N inserts: O(N * N) is O(N^2)
    2) in-order traversal to get the sorted order of elements
         O(N) since we have to visit each of the N nodes in the BST
    So total worst case time complexity is
       O(N^2) + O(N) which is dominated by O(N^2)


"Big Oh" notation for expressing growth rates of functions
specific to operations for the data structures we have discussed

know worst case and average case for each op

  General List of length N 
    know these for array impl and linked cells impl
    insert at index 
    remove at index 
    find index of a value
    find value at index (get at index)

  Queue containing N items
    know these for array impl and linked cells impl
    can't get middle elements like general List
    enque (add) 
    deque (remove) 
    front (what is at the head of the queue)

  Stack containing N items
    know these for array impl and linked cells impl
    can't get middle elements like general List
    push 
    pop 
    top 
    know these for array impl and linked cells impl

  Binary Search Tree with N nodes
    common impl is via linked cells
    know worst case and average case
    insert 
    remove 
    find a value ... is it in the tree
    findMin
    findMax

    traversals are O(N) (list every element in some order)
    we get ordering (sorting) information from the tree structure
    degenerate case of BST is a List
 
"Big Oh" is an upper bound on growth speed of an operation/algorithm
    but it is not necessarily a good (tight) upper bound

    if some operation F is O(N^2) in worst case time use
                 then F is also O(N^3)... and 
                 then F is also O(2^N)
                 etc.
    but O(N^2) is the lowest (tightest) bound of those given.
    we would say O(N^2) is the "best" worst case time complexity of those choices
                        or the "least bad" worst case

Time-space trade-off
  -- sometimes we can gain some speed (save execution time) for an operation 
     by using more space (memory)
  -- we can also sometimes design ways to use less space for an operation, but 
     then lose speed when doing so

  examples?

Recursion: it's turtles all the way down (until the armadillo)
  -- a programming pattern in which the code in the body of a function contains one or 
     more calls to itself 
  -- well-formed recursive function must have
       -- a base case, which returns a simple result for a simple "small enough" 
          instance of the problem defined by the parameter values, and this result 
          is returned without a recursive call
       -- a recursive case, in which a recursive call is made (a call to the very function
          being defined); the recursive call is made on a "smaller" instance of the 
          problem being solved; the problem (its size) is defined by the parameters passed to
          the recursive call.
  -- a recursive function may have more that one base case, and may have more than one
     recursive case
  -- the base case(s) should proceed the recursive case(s)... testing for base case is testing
     for stopping the recursion, and it the first thing to do in the code
  -- proper termination (preventing infinite recursing) involves 
       1) making sure each recursive call is passed a smaller problem
       2) the problem is decreasing towards a base case
       3) the base case checks are written so that the problem size eventually trips
          a base case (and does not bypass it)

  -- poorly formed recursions can blow out the call stack
  -- using recursion when iteration is better can blow out the call stack
  -- proven theory: 
       -- any program that uses iteration (loops) and no recursion, can be re-written 
          to use recursion and no loops, while still computing the same function (results)
       -- any program that uses recursion no loops, can be re-written to use loops and no
          recursion, while still computing the same function (results)
       -- this means recursion give us expressive convenience for some problems, 
          but no extra computing power... there are no function that we can compute with 
          recursion, but cannot compute without it.
     
  

Runtime stack and runtime heap 
  the runtime system is how a programming language does the computations that 
  programs call for

  runtime stack allocates stack frames (call frames) when procedure/methods are called
    -- manages this dynamic memory is LIFO order, so the first call to end is the 
       most recent one started
    -- a stack frame (call frame) has memory space for the parameter values sent in
       when a function is called, the return address of the code that called it, 
       the local variables in the function , and some bookkeeping data 

  runtime heap is dynamic memory from which objects are allocated on calls to "new"

  heap is not managed with any particular discipline like LIFO etc.

  heap can get fraqgmented, stack cannot
  heap fragmentation is dealt with via gargage collection in Java

  how can the runtime stack blow out (run out of space)?  
    -- too many concurrently active function calls
    -- this can happen with recursion... especially a recursion that is poorly written 
       and does not hit a terminating base case



Sorting
  we have discussed and analyzed these sorting methods:
    -- Bubble Sort: rearranging the items in an array/list to put them in order
                    "gold standard of badness" since it's O(N^2) worst case as well as avg case
    -- keeping a basic List sorted (using inSort operation)
    -- BST sort: build a binary search tree and do in-order traversal
            (worst case analysis, and average case analysis)