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

Friday, June 3, 2011

June 3st - 2011

public class sailboat extendets watercraft
{



public stringtostring(){
string assembply;
final double poundspertonne= 2204/62262;
double pounds = getDisplacement()*poundsPerTonne;
assembly += "masks, displacement";
assembly += Double.toString(pound);
assembly += " pounds." ;
return (assembly);



Question 12:52 PM
Sailboar laser2 = new Sailboat();
laser2.toString();



choice of overload is made at compile time based on signaure of the method
choice of override is made at runtime based on type of object

Monday, May 30, 2011

May 30th - 2011

To create an array :
int[] arrayName = new int[size];
int someVar = arrayName [3];

Classes:
a class is a blueprint (directions) for creating objects
-attributes (data values ; state)

-methods (algorithms to manipulate the data)

overload: multiple methods with the same name
the compiler chooses the right method based on the method signature:
-name
-types of the parameters
-order of the parameters



to create a class: 

public class Die  {

Maximum value for the die (final meaning we cannot change the max_value anymore)
 
private final int MAX_VALUE = 6 ;
Value of the die
private int faceValue ;

default constructor
sets the initial fce value to 1
public Die ()
{ faceValue = 1 ; }

constructor with initial face value
public Die (int initialValue)
{faceValue - initialValue ; }

Roll and the die return the result.
public int roll ()
{faceValue = ((int) (math.random().MAX_Value)) +1 ;
return (faceValue) ;}

Wednesday, May 25, 2011

May 25th - 2011





An array is many instances of a single data type: 37 char, or 352 doubles.

To declare an array:
double[] arrayofDouble = new double[25];
to declare one variable:
double oneDouble ;



the size of an arrat need not be known until runtime

int k ;
k = Integer.valueOf(args[0]);
double[] arrayofDouble = new double[k];



public static main (string [] args) { }


reminder :

double firstDblval, secondDblval ; firstdblval = 42.0; secondDblval = firstDblVal

------------
we're gonna declare :

double [] firstDblArray, secondDblArray ;
firstDblArray = new double[50000] ; ( it creates a reference )
secondDblArray = firstDblArray ;


secondDblArray[42] = 357.8 ;
if (firstDblArray[42] == 357.8)
System.out.println ("True") ;


Will print True !

When we write

if (firstDblArray == secondDblArray) {




}

What is being checked?

It is checking if the value of firstDblArray is the same as secondDblArray, not the content.

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


Arrays are a derived class of Object.


When i really want a separate copy of an array, I can clone it.

double[] dblArr1 = new double [50000];
double[] dblArr2 ;
dblArr2 = dblArr1.clone() ;

creates an entirely separate block of space for dblArr2, initialized to the contents of the block of space holding the 50,000 entries of dblArr1

------------
1:14 PM

What if i need a reference to a single value of a basic type ?
-could use double [] trivial = new double[x]

- "Autoboxing" is another way to create a reference to a basic type. for each basic type, a matchin class:

char ===> Character
boolean ==> Boolean
.
.
int ====> Integer

Friday, May 20, 2011

May 20th - 2011

Reading: Section 5.7 pages 209-214
first few sections of chap. 5 Classes
Review

Basic Data Types

Integer:

byte :1byte
short : 2bytes
int : 4bytes
long : 8bytes

Floating Point Values: (IEEE 754)

float : 4bytes +-3.4 * 10^38 to 7 digit decimal
double: 8bytes +-1.7 * 10^308 to 15 digit decimal

Char:

for characters
each 2 byte Unicode
12:41

Boolean:

Two values: true, False
size is implementation- dependent
---------------------

Conversion Between Data Types

widening conversion: does not risk loss of information
narrowing conversion : does risk loss of information

conversion from a signed byte/short to char

12:53

booleans not convertable

narow -> big to small
widening conversion -> small to big


12:57
byte --> smallIt
long -->bigInt

big Int = smallInt // widening-ok

if i want to write:
smallInt = bigInt; //narrowing error
smallInt(byte) BigInt; // narrowing w/
// explicitcast - OK

1:03

-------------------------
Assignment conversion: conversion to match right-hand data type to left hand
bigInt = Smallint converts smallInt to bigInt

casting: explicit conversion specified by the programmer

Promotion: when evaluating expressions, the java compiler tries to make bothoperands be the same dara tyoe using widening conversions.
int a, b;
float c,d;
a = 3
b = 4
c = (a/b); --> zero
d= ((float)a)/b) --> 0.75

long a;
float b;

c = a+ b
1:14
Arrays


Many instances of a single basic types.

- Strings are arrays of characters
- Grocery bill is an array of numbers

Java provides arrays as a basic part of the language

-indexed from 0
- all entries are of the same type
- space required for n items of size k is n*k
- indexed by entry
byte[] = arrayeofbyte[5] ;
1:20

diagrams


Wednesday, May 18, 2011

May 18th - 2011



Memory & Data
- Basic Unit is a bit
- Byte: 8 bits
- Data & instructions are stored in memory
  • Every byte of memory has a unique numeric address
  • To fetch or store in formation, the CPU must specify the numeric address of the information.
Common Prefixes


Terminology

Byte: 8 bits

Word: " natural unit of data in a processor "

unfortunately, in today's world you will encounter 16-, 32-, & 64-bit processors.

at present, a word is most often 32 bits.

Variable declaration
int someVar ;

Java Data Types

*Java is a strongly typed language
Integer Types:
byte 1 - 2^7 2^7 - 1
short 2 -2^15 2^15 -1
int 4 -2^31 2^31 -1
long 8 -2^63 2^63 - 1

2^31 - 1 = 2,147,484,647

Floating Point
42.24 *10^16
.4224 * 10^18

Current representation: IEEE 754
float occupies 4 bytes the range roughly is +- 3.4* 10^38 which gives us a 7 digit accuracy
double occupies 8 bytes, the range is roughly +11.7*10^308 15 digit accuracy.
(when evaluating range, accuracy, remember that 10 ~= 2^3.3
In 32 bits, there are 2^32 unique codes .
computer arithmetic has severe accuracy challenges.




Monday, May 16, 2011

May 16th - 2011

Office hours: CSIL 9840 or 9804

TAs: after conclusion of demos
Read chap.2 section 7.1, 7.2 (arrays)

class: directions to construct an object

object:
  • a collection of data (attributes)
  • algorithms (methods)
Attributes and methods are both members.
an object is an instantiation of a class.
each object has its own unique data storage all objects can share algorithms.

javadoc -author Lincoln.java

args[0] = "-author"
args[1] = "Lincoln.java"


in : input from the console (keyboard)
out: output to console (monitor)
err: error output to console (monitor)

in, out and err are members of the class System.
in is an object of class InputStream
out, err are objects of class PrintStream

Syntax defines the way we can compose letters and symbols into a java program.
semantics defines the meaning of a statement in a program
zaphod = 42 ; syntactically correct!

CORRECT
int zaphod ;
zaphod = 42 ;

semanticallt correct!

WRONG!
boolean zaphod ;
zaphod = 42 ;

not semanticallt correct!

Friday, May 13, 2011

May 13th - 2011




Software demoes start Monday.

CMPT 125:

D101 AS9840
D103

CMPT 126:
D101 AS9804



disk a is local to host A
disk b is local to host B
given the proper setup, A can mount disk A from host B ( a 'network drive or 'remote file system') and access the contents of disk A just as if it were physically connected to host B.

/home/lou : CSIL home directory
/home/lou/sfuhome : ITS home directory --> this is what we need to do ( create a folder within our own home directory and link that to the eclipse environment.

end-of-line conventions:
windows: ctrl + M , ctrl + J
Linux : ctrl + J
Mac : ctrl + M

CODE:
/**
Demonstrates the basic structure of a java application.
This example also shows the most basic yse of javadoc comments.
the sentence above appears in many places as a symmary. this paragraph will appear in many places as a summary. this paragraph will

public class Lincoln
(
/**
Prints a presential quote.
*/
public static void main (sring[] args)
( system.out.printin("A quote by Abraham Lincoln:") ;
system.out.printIn("Whatever you are, be a good one.") ; )
)











What is a class?

A class is the direction for constructing an object
An object is a collection of data and behaviors

- the data are called attributes
- the behaviors are called methods
- attributes and methods are members

class:
data storage :
  • inches
  • feet
  • miles
algorithms : add {inches,ft,mi.}
to {inches, ft, mi}
to get { inches, ft, mi}

Wednesday, May 11, 2011

May 11th - 2011

Read Chapter 1.
-----------------------------------------------------
At the bottom, a computer understands only binary patterns.
- instructions and data are both binary patterns.
- whether a particular group of bits is instructions or data depends entirely on context.

Progress to higher level languages.
- Machine language (binary patterns)
- Assembly language ( mnemonics in one-to-one correspondence with machine language)
- Fortran & Cobol : first high-level languages.
- Present day : hundreds of languages.

How do we translate a high-level language to machine language?

In particular , Java.

Two general techniques:

Interpretation : Execute line by line as lines of code are written / edit -> run
Compilation : translate to machine code as one unit / edit-> compile-> run


java source code ---> Compiler (JavaC) ---> Java byte code ---> java virtual machine (JVM java virtual machine executes java byte code ) ---> machine language .

Five steps for problem solving

1) Understand the problem
2) Design a solution
3) Consider alternatives & refine the solution
4) Implement the solution
5) Test the solution and fix any problems.

/** --> indicates a javadoc comment
demonstrates the basic structure of a java application
this example also shows the most basic use of javadoc comments.
the sentence above appears in many laces as a summary. this paragraph will appear only in the detailed description of the class. the text of the comment can be followed by special tags, such as '@author', below. the tag section starts at the first line beginning with '@'.
@author lewis & Loftus
*/

public class Lincoln
(

/**
prints a presedential quote/
*/
public static void main (string[] args)
( system.out.println(" A Quote by Abraham Lincoln:") ;
system.out.println(" Whatever You are, be a good one.") ; )

/*
some comment
*/

Comments

- convey the intent of the programmer what is this piece of code supposed to accomplish.
- design assumptions ( particularly implicit assumptions)
- sneaky or clever implementation technique

Monday, May 9, 2011

May 9th - 2011

Lou Hafer
Office: TASC 9421
lou@cs.sfu.ca
Office hours: MW 4:30-5:30
Rate My Prof

Eclipse IDE (The environment we work in)
Java Run-time Environment

Text Book We Use :
Java Foundation by Lewis, Depasquale, Chase

Course Website


From CMPT 120:
*Data types and conversions, sections 2.1-2.3,2.5
*Expressions section 2.4
*Strings section 3.2
*Libraries(packages, modules) section 3.3
*Conditionals (if,then,else) section 4.1 - 4.2
*Loops section 4.5,4.7,4.8,
*Subroutines (methods) section 5.4
*Basic Terminal i/o section 2.6



Computing Science:


- Study of algorithms
* Math properties
* Linguistic realization
* Hardware realization
* Application of algorithms


Algorithm : sequence of unambiguous instructions for solving a problem.

- desire efficiency
- desire robustness