CSC152 2005F, Class 38: Linear Structures

Admin:
* Questions on the exam?  (At least one error still needs to be corrected)
* Time to torture the prospective
  Kenyon, Franklin and Marshall, St. Johns, Bates
  * Grinnell people are nice
  * Small and close
  * Yay,  We're isolated, so there's nothing to do besides
    study and interact with your colleagues
  * Crazy awesome stuff comes to campus (Bela Fleck, Swing band,
    Awesome harpsichordist, Women's soccer; WMD speaker series)

Overview:
* Collections
* Linear Structures
* Randomized Linear Sturctures

Exam Questions:
* Is null an Integer?  Yes.
* What does size() return?  Larger of specified size and largest-used index  (e.g., size set to 100. used 2, return 100)a
* Shoudl I be able to change a size field?  Yes.
        public class ExpandableArray
        {
                int size;

                public void set(int index, Integer newval)
                {
                        if (this.size < index) {
                          this.size = index+1;
                          Integer[] oldcontents = this.contents;
                          this.contents = new Integer[this.size];
                          ...
                        }
                }
* Do I need a size field?  Can't I just use the size of the array?
  * Certainly

About Collections
* Many programs collect data
* Goal: Find techniques for collecting data 
  * And think about when they are and are not appropriate
* Arrays and Vectors:
  * Collect data by index
    * Retrieve easily (if some semantics to index)
    * Gives a sense of order
  * But ...
    * Expanding is expensive (O(size))
    * No built-in sorting operation
    * Removing most elements is slow (O(size))

Different problems suggest different philosophysie of collections

Linear Structures : Goal: Be as simple as possible
* Philosophie: Add and remove, but that's about it
* Application: Lots
* Methods
  * add    (put)
  * remove (get)
* Problem: What does get return?
  * We seprately specify a *policy* to answer that question
  * We encode the policy by writing different kinds of linear structures (different interfaces)
    * Queue: First in, first out
    * Stacks: Last in, first out
    * Priority queue: get returns "most important"
    * Randomized: Hard to predict