Sing, Pray

Announcements
===============
* Homework 5 due Today
* Today is the penultimate day of class
* Monday is the last day of class.  We will review for the Final exam.
* ALL PROJECTS ARE DUE ON MONDAY BY THE TIME THE LAST T.A. LEAVES


Any Questions? 
===========================
We can discuss any questions you have on projects or the material that we have covered so far.


Items
===========================
* Use a hash table instead of a binary search tree if you do not need order statistics and are not worried about non-random inputs.  For example, hashing is used for spell checkers.  If misspelling detection (as opposed to correction) is important, an entire dictionary can be prehashed and words can be checked in contant time. (Project 7)

* Hash algorighms have various collision resolution techniques (linear probing, quadratic probing, chaining, and others).  Primary clustering occurs with linear probing (affects performance), secondary clustering can occur with quadratic probing (which is a "minor theoretical blemish").

* double-hashing is another collision resolution technique.  It does not suffer from secondary clustering.  It is performed by using a second hash function on the index to resolve a collision.


Outline
===========================
21.3 buildHeap (Review)
21.5 Heapsort (Review, Example)
### Group Work ###
16.2 Linked-List Stack and Queue
16.1 Array Stack
16.1 Array Queue
16.3-16.5 Comparison


Notes
===========================

21.3 buildHeap and  21.5 Heapsort
---------------------------
	<< buildHeap example >>

	Given an array (which can easily be represented by a Complete Binary Tree) what is the result after performing buildHeap (heapify)?

	<< Heapsort example >> in-place sorting algorithm takes O(n log n)

	Given an array how can it be sorted using heapsort?


Stack and Queue Implementation 16.1-16.5
---------------------------

The advantage of a linked list implementation is that the excess memory is only one reference per item.  The disadvantage is that the memory management could be time consuming.

Stack Linked-List
-----------------
- In implementing the stack class, the top of the stack is represented by the first item in a linked list.
- The stack routines are essentially one-liners

Queue Linked-List
-----------------
- A linked list in which we maintain a reference to the first and last item can be used to implement the queue in constant time per operation
- Enqueueing the first element is a special case because there is no next reference to which a new node can be attached.

Stack Array
-----------------
- A stack can be implemented with an array and an integer that indicates the index of the top element.
- Most of the stack routine are applications of previously discussed ideas
- Recall that array doubling does not affect performance in the long run. Dynamic expansion is infrequent because an array doubling that involves N elements must be preceeded by at least N/2 pushes that do not involve an array doubling.  Consequently we can chare the O(N) cost of the doubling over these N/2 easy pushes, thereby effectively raising the cost of each push by only a small constant (amoritization).


Java Collections API
	empty: Tests if this stack is empty.
	peek: Looks at the object at the top of this stack without removing it from the stack.
	pop: Removes the object at the top of this stack and returns that object as the value of this function.
	push: Pushes an item onto the top of this stack.
	search: Returns the 1-based position where an object is on this stack.
        
Additional Reference: http://www.cs.bu.edu/teaching/c/stack/array/

Queue Array
-----------------
- Storing the queue items beginning at the start of any array makes dequeueing expensive
- A dequeue is implemented by incrementing the front position
- Wraparound returns front or back to the beginning of the array when either reaches the end.  Using wraparound to implement the queue is called a circular array implementation
- If the queue is full, we must implement array doubling carefully


Comparison
-----------------
The array versus linked list implementations represent a classic time-space trade-off.