July 6th, 2011

Read: 

Chapter 14 Stacks

4.6,4.8 Iterators
9.3
Chapter 15 Queues


Searching :


String [] planets = { "Neptune" , "Uranus", " Saturn", "Jupiter", "Mars", "Earth" , "Venus" , "Mercury:" }

To find a given element, scan the list for a match. O(n) for linear search.
To prove absence, must look at all elements.

Sort planets alphabetically:
Earth, Jupiter, Mars, Mercury, Neptune, Saturn, Uranus, Venus

Each comparison eliminates a portion of the list, because we know from a comparison whether the element we want is earlier or later in the list.

Given a sorted sequence, use binary search
- compare with middle element
- discard the irrelevant 1/2
- repeat with relevant 1/2

Because the problem is reduced by 1/2 with each iteration, in log2 n iterations we will find the element or prove the element is not in the list. O (log2 n)

Effort to sort: n log2 n
Effort for linear search: n
Effort for binary search: log2n

n log2 n + k log2 n <= kn
(n+k) log2 n <= kn
log2 n <= (kn/(n+k))
log2 n <= k/(1+(k/n))
first approx : sort first if log2 n <= k




Collection:
- An object that gathers & organizes other objects.
- It defines the specific ways in which those objects can be accessed and managed.
- The user must interact with the collection only with the prescribed ways of access & management.

Text:
- linear collections are organized in a straight line
- nonlinear collections are not.

Things : Members of Parliament (MP's)

How to organise?

- unorganized rabble :
* a set
* easy to add
* difficult to extract

"member from calgary southwest, conservative, ..."

- linear order (alphabetically by name):
* easier to find ( "Harper")
* can also specify by pos'n.
* insertion requires more effort (find the right place)

- nonlinear order ( geographic )

Why should we accept the restriction of a collection?

Users:
-a relatively small number of Abstract Data Types (collections) cover an enormous range of situations.

Implementor:
the task of implementing an ADT is bounded (manageable ), can concentrate on a good implementation or a relatively small number of methods.