CSC153 2004S, Class 40: An Introduction to Abstract Data Types

Admin:
* I am soooooooooo very very very thankful that Chase and Erik and Saul and Joe are here today!!!!? And that Andy showed up less than five minutes late.  And that Brian showed up less than ten minutes late.
* Convo Thursday: Catholicism and Democracy
* Transition time: From language details to high-level CS concepts
* Exam to be distributed Wednesday
* Homework: Read about lists; Summarize
* Questions on homework 6?
  * Flip a coin for the first game in a match, alternate thereafter
* General Java question
  * Is there a separation between the language and the API?  Yes, but there's only one real API.
  * Are there things in the API that aren't doable with the core language?  (System-dependent stuff.)
  * Can you write Java in Java plus java.lang?  I think so.

Overview:
* About ADTs and Data Structures
* Designing ADTs and Data Structures
* Example: Arrays
* Example: Collections
* About the homework

/About ADTs and Data Structures/

* Observation: The design of an algorithms can be closely tied to the way the data used in the algorithm are organized.
  * E.g., you don't usually binary search a list because finding the middle element is hard.
* It turns out that thinking carefully about the way you structure your data, you may design new algorithms.
* Two ways to think about the structuring of data
  * Abstract data type (ADTs): Focus is on the interface/methods
  * Data structures: Focus is on the implementation
* There are a number of standard data structures that it benefits you to design and learn (there is some dissension on the design of each structure)
  * List, Array, Vector (Java), Hash tables, Stacks, Queues, Priority Queues, Heaps, Binary Search Trees (BSTs), Graphs (if time)
    * A heap is a nearly-complete binary tree which also has "the heap property"
    * The heap property: The value of a node is less than or equal to the values of its children

/Designing ADTs and Data Structures/

Abstract data type:
* Overall philosophy
* Set of methods
* Applications
  * We write algorithm and need methods on the data
  * We write ADT and look for applications
* Semi-Hierarchical placement
  * Multiple inheritance for ADTs may be good
* We will almost always implement these as interfaces

Data structures provide implementations of ADTs
* Overall philosophy (what is our implementation strategy)
* Implementation details
* Efficiency

/An Example: The Array/

* Philosophy: Collection of values indexed by number; Constant-time access to individual elements
* Methods
  * retrieve(int index) - Look up something at a particular index
     index must be in the range of the array 
  * store(int index, ??? valueToStore) - Put data in the array
  * construct(value_1,value_2,...value_n)
  * construct(int size) // How do we distinguish from the prior?
  * resize(int newsize) // Permissible?
  * int getSize();
* Applications:
  * Lookup table for searching
  * Dynamic programming
  * ...
* What are its likely supertypes?
  * IndexedCollection - No expectation of constant time
  * Collection - No expectation other than that it collects and is "dumpable": Iterable
  * ...
* What are its likely subtypes or sibling types?
  * ResizableArray

Detour: Designing ADTs
* Good strategy: Minimize methods, build subtypes when you want more methods

Detour: Java style
* Class names begin with capital letter
* Constants are all caps
* No other name begins with a capital letter

Detour: Hungarian style
* Variable names are prefaced by an abbreviation of their type

Detour: Dealing with "potential" methods, like resize
* The legendary "UnimplementedException"

/An Example: The Generalized Collection/

* What is a collection?  A group of objects.
* Subtypes:
  * IndexedCollection - Can look up values by number
  * IterableCollection - Can step through the elements
  * Set - Can determine membership
  * Expandable
  * Contractable

/About the Homework/

* Goals
  * Organizing principle of the list ADT.
  * Summary of key methods.
  * Any interesting variations you note.
* Warning! Not all books have a list ADT.  You get to improvise.