Monday, July 18, 2011

July 18th, 2011

Iterators
enhanced for loop

String [] horsemen = {"war", "famine" , "pestilence", "death" }
for (String horsemen : horsemen )
System.out.println (horseman) ;

There is an
Iterator interface
Iterable interface

Iterator interface defines methods:
- boolean hasNext () : returns true if next() returns an element
- T next()
- boolean remove()

Scanner testScan = new Scanner (~)
while ( scan.hasNext() ) {
String token = testscan.next() ;
/* code to process token */
}

but....

for (String token : testScan ) ! not legal
because Scanner doesn't implement Iterable

Iterable Specifies iterator ()
- iterator returns an object of type Iterator

ArrayList implements both Iterable, Iterator.
-------
ArrayList arrayListOfFoo = new ArrayList ();
for ( Foo refToFoo : arrayListofFoo {
/* do something * /
}

compared to

ArrayList arrayListOfFoo = new ArrayList() ;
Iterator arrayListIter = arrayListOfFoo.iterator () ;
while (arrayListIter.hasNext() ) {
Foo refToFoo = arrayListIter.next() ;
/* Code to do something */
}



Recall collections of MPs
-unorganised rabble (set)
linear order (list)
nonlinear order (Tree)


public void printlistofMPs ( collection all MPs )
{ for (MemberOfParliment one Mp: all MPs )
{ System.out.print;n(oneMP); }
}

Iterable declares

Iterator iterator()
   * return an object of type Iterator

Iterator declares

boolean hasNext() return true iff a call to next() will return an object

T next() return the next object from the collectionl repeared calls to next() will return every element exactly once Order will depend on the type of collection.

void remove () remove the element

Collection extends Iterable

int size() return the number of things in the underlying collection

boolean add (E e) add a thing to the underlying collection

boolean remove (Object o) remove from the underlying collection to the first thing hat is equal to the object provided as a parameter

public interface List extends Collection

void add (int index, E e) add an element at the specified position

E get (int index) Retrieve the element at the specified position

E remove (int index) Remove the element at the specified position.

Monday, July 11, 2011

June 13th , 2011

Abstract Data Types

Example: Stack ADT
- elements are added and removed from the same end; LIFO (Last In First Out)

push() ==> Add (Push) an element
pop() ==> Remove (pop) an element
peek() ==> Look at the top element w/o removing it


is Empty()
size()

Assume some type T to be held by the stack
where T is just a placeholder

push(T elem)
T pop()
T peek ()
boolean is Empty()


Generic Types
- Some way to postpone specifying a type without some of the hazards of polymorphism.



Animal[] creatures = new Mammal[25];

.
..
...
creatures[1] = new Lizard () ;

This causes a runtime error because Lizard is not a subclass of Mammal.

Generic types allow us to help the compiler by providing additional hints about data types.

Recall the comparable interface

class Apple implements Comparable {
.
..
...
public int compareTo (Object otherObject)
.
..
...
}

Comparable is actually a generic interface :

public interface Comparable   { 
public int compareTo ( T thing) ;
}

To compare Apples to Apples (only!)

class Apple implements Comparable {
.
..
..
public int compareTo (Apple otherApple) {.....} ;

Text uses this language:

"Then, when a generic class is needed, it is instantiated with a specific class used in place of T."

Would be nice to allow:

class Apple implement Comparable , Comparable {.......

But doesnt work!

Subtly wrong - information about the actual type used for T is not part of the runtime hidden bookkeeping information. Generics are enforced by the compiler.

Wednesday, July 6, 2011

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.

Monday, June 27, 2011

reversing a String

Native recursion:
-remove first character
-reverse the res of the string
-add (former) first character to the end of the string


Steps to develope a recursive algorithm:

1) Can I divide the problem at hand into smaller problems of the same type?
2) given a sufficiently small instance of the problem, is it simple (or trivial) to find the answer?

--> BASE CASES <--

3) given answers to the smaller problems,
can I reassemble the answers to get an answer for the whole problem?

Wednesday, June 22, 2011

June 22, 2011

ArrayList
- a generic class, should be restricted for use
Array List tmpCards = new ArrayList ()
.
.
.
tmpCards.add(anotherCard);
.
.
.
Card[] allCards = new Card[tmpCards.size()]
allCards= tmpCards.toArray(allCards);


How to check if Equal?

String s1 = "abc"
String s2 = "abc"

'==' tests equality of reference

if (s1 == s2) or s1.equals(s2)
System.out.println ("equal")
else
System.out.println("not equal")

the answer is equal!

why?
even
String s3 = "a" + "b" + "c"
if (s1==s3) .....
will be equal

but
String s4 ;
s4 = "b";
s4 = "a" + s4;
s4 += "c" ;
if (s1 == s4)....

NO it is not equal

but 

s1.equals(s4)

Yes it is equal!



Recursion

GNU ::= GNU is not Unix
"recursive acronym"

----------------

name list ::= name, namelist | name



Fibonacci Numbers
F(0) = 0
F (1) = 1
F(k) = F(k-1) + F(k-2)
int fibonacci (int k) {
if (k==0) return(0);
if(k==1) return(1);
return(fibonacci(k-1) + fibonacci(k-2));
}

Monday, June 13, 2011

June 13th , 2011

Polymorphism & inheritance
Design Principles:

* A derived class should have an ' is-a, plus ' relationship to the superclass.
- The derived class is an instance of the superclass, plus same additional attributed & methods.
* Push common attributes & methods as high as possible in the hierarchy.
*If the derived class needs to manipulate attributes in superclass, use the methods of the superclass where possible.

Java Keywords:
'super' refers to the immediate superclass
'this' refers to the current class

Wednesday, June 8, 2011

June 8th , 2011

Posted a list of topics to course website.
Notes and code for i/o posted on course website.


I/O - Input & Output