Transcript COMP-2001 – Lecture 1 - University College Dublin

DATA STRUCTURES AND
ALGORITHMS I
WELCOME!
Dr ELENI MANGINA
[email protected]
UCD Computer Science
1
Practicals
Sessions as assigned; attendance mandatory
Each will probably require:
2-4 hours prior to your session
1.5 hours in lab
2 hours after session
Several problems each, lifted directly from text-book
Programming requires practice!
45% of total course mark!
Examination will require you understand the practicals!
 1 week late? Maximum of 50%
> 1 week late? No marks earned
UCD Computer Science
2
Don’t
cheat
Practicals
Cooperation and group studying are encouraged.
But it’s easy to detect, and
Cheating will be dealt with according to the
Department’s harsh plagiarism policy.
UCD Computer Science
3
Course outline
•
•
•
•
Java refresher
Object-oriented and modular design
Mathematical tools for analyzing programs
Remaining weeks on a variety of useful topics
–
–
–
–
–
–
–
Stacks
Queues
Lists
Vectors
Trees
Priority queues
Heaps
A useful “bag of tools”
that forms the foundation
of all large software projects
• Topics relevant to all programming languages
2001 is not just a course on “more Java”
UCD Computer Science
4
Textbook
• Goodrich & Tomassia -- Buy it!
Many useful resources at book’s web site.
• You Must read assigned sections before
corresponding lecture!
– Otherwise you’ll be lost
UCD Computer Science
5
Java refresher
• Forget Java over the summer? Try the notes, or any of
the excellent books or Web tutorials (see course Web for
pointers)
• For Thursday: Read G&T Chapter 1
• Start Practical #1
• Some of the following details may be bewildering or
overly complicated at first -- come back to these notes or
resources later when you understand what’s going on
UCD Computer Science
6
Basic Concepts
• Classes: a conceptual “box” that holds data (“instance
variables”) and methods that can be invoked in the data.
• Objects: instances of a given class
• Types: classes + primitive types (int, float, ...) +
built-in data structures (array)
• Methods: a.k.a. “functions”, “subroutines”
• Access modifiers: public, private, static, …
• Expressions: create new values from combinations of
existing values
• Control flow: if, for, return, ...
• Packages: how classes are organized
UCD Computer Science
7
Classes
class Fish {
int nfins;
String name;
// instance
// variables
Fish(int _nfins, String _name) {
nfins = _nfins;
name = _name;
}
// constructor
// method
void morefins(int delta) {
nfins += delta;
}
// “regular” method
}
UCD Computer Science
8
A complete program
• A Java program doesn’t “do anything” unless is
contains a special main method:
class Fish {
int nfins;
String name;
Fish(int _nfins, String _name) {
nfins = _nfins;
name = _name;
}
void morefins(int delta) {
nfins += delta;
}
public static void main(String args[]) {
Fish f = new Fish(3, "Fred"); // object creation
f.morefins(4);
// method invocation
System.out.println("Fred has " + f.nfins + "fins");
}
}
UCD Computer Science
9
Files, packages, classes
• A single Java application typically comprises many
classes, grouped into several packages, much of which
might be shared with other applications:
Human Resources Program
Payroll Program
package A
package C
C1
C2
C5
C8
C6
C7
C3
package D
C9
C10
C4
package B
UCD Computer Science
10
Files, packages, classes - continued
• There must be a 1-to-1 correspondence between:
Classes - Java source files
Packages - directories comtaining the class files
/app/acounting/packageA/C1.java
/C2.java
/packageB/C3.java
/C4.java
/sharedstuff/packageC/C5.java
/C6.java
/C7.java
/human-res/packageD/C8.java
/C9.java
/C10.java
UCD Computer Science
11
Creating objects and values
type variablename = expression
int nfingers = 4;
double weight; // very occasionally, initial value inappropriate/unnessary
boolean defective = weight<0; // initial value can be any expression
Integer ntoes = new Integer(4); // primitive data types aren’t
Boolean problem = new Boolean(defective || (nfingers<0);
objects
String name = "Bob";
Fish f = new Fish(3, "Bob");
UCD Computer Science
12
Simple Input/Output
• Java has an incredibly complicated hierarchy of classes for
performing input/output.
• Output
System.out.println(f.name + " has " + f.nfins + " fins");
• Input
import java.io.*; // enable access to all Java I/O classes
…
BufferedReader stdin =
new BufferedReader(new InputStreamReader(System.in));
String line = stdin.readLine(); // read 1 line of text
Next step depends on what data type the user is expected to enter. For example…
int xnfins = Integer.valueOf(line).intValue();
// expecting an integer
… or …
float weight = Float.valueOf(line).floatValue();
UCD Computer Science
// expecting a float
13
Exceptions
• Any number of exceptional circumstances may
arise during program execution that cause trouble
import java.io.*;
class IOExample {
public static void main(String[] args) {
try {
BufferedReader stdin =
new BufferedReader(new InputStreamReader(System.in));
String line;
System.out.print("Enter the number of fins > ");
// wait til user enters something other than just RETURN
while ((line=stdin.readLine()) == null) ;
int nfins = Integer.valueOf(line).intValue();
}
catch (IOException x) { // oops -- something strange went wrong
System.out.println("Is your keyboard OK?! -- " + x);
}
catch (NumberFormatException x) { // entered something like “frog”
System.out.println("Integers only! -- " + x);
}
}
}
UCD Computer Science
14
Control flow
if (nfins > 10) { // execute block only if condition holds
System.out.println(“Are you sure??!??!”);
}
int a = 10, b = 20;
while (a>0) {
// repeatedly
b = b+a;
if (b > 60) break; // immediately
a = a-1;
execute body until a=0
terminate while loop
}
// now a=5 and b=65
for (int i = 0; i < b; i++) { // set i=0, 1, 2, …, 64
a++; // shorthand for “a = a+1”
}
// now a=70 (and b is still 65)
UCD Computer Science
15
Expressions
• float appendageCost = (nfins + ntoes) * costPerAppendage;
• int remainder = numerator % divisor; // eg 5%2 = 1
• boolean probablySick = (whiteCellCount > 145);
• x = ++j; // increment j, and set x to the new value
• y = j++; // increment j, and set y to the current value
• String fullname = firstname + " " + surname;
•
•
•
•
•
double w = 45;
int x = 45;
double y = w/10;
double z = x/10;
double z = ((double)x)/10;
• int q = 3 + 4 * 5;
UCD Computer Science
//
//
//
//
//
set
set
set
set
set
w
x
y
z
z
to the real number 45.0
to the integer 45
= 4.5
= 4.0 not 4.5 !!??!!
= 4.5
// sets q to 23, not 60 !!?!?
16
Arrays
• Java has one built-in “primitive” data structure
• When array is created, its capacity must be specified
(with any integer expression!) and then can’t change
System.out.println("Enter the number of cities >");
int ncities = Integer.valueOf(stdin.readLine()).intValue();
int rainfall[ncities];
String name[ncities];
for (int i = 0; i < cities.length; i++) {
System.out.print("City " + i + " name > ");
name[i] = stdin.readLine();
System.out.print("City " + i + " rainfall > ");
rainfall[i] = Integer.valueOf(stdin.readLine()).intValue();
}
(danger -- no exception handling for simplicity)
UCD Computer Science
17
Defining methods
class Rectangle {
int height, width;
int area() {
return height*width;
}
void wider(int delta) {
width += delta;
}
void taller(int delta) {
height += delta;
}
RETURN-TYPE NAME( ARG1, ARG2, … ) {
BODY
}
}
UCD Computer Science
18
The Dereference (“Dot”) Operator
• If X is an an object of some class C that contains
an instance variable Y, then X.Y accesses that
value of Y in object X
• Methods work exactly the same way
• stdin.readLine().toLowerCase().indexOf(“dog”)
e keyboard standard-input object
the next string entered at the keyboard
the string formed by replacing all UPPER case letters with lower
the position in that string of the first occurrence of “dog”
UCD Computer Science
19
ARRAYS
public class ArrayDemo
{
public static void main(String[] args) {
int[] anArray;
// declare an array of integers
anArray = new int[10]; // create an array of integers
// assign a value to each array element and print
for (int i = 0; i < anArray.length; i++) {
anArray[i] = i; System.out.print(anArray[i] + " ");
}
System.out.println();
}
}
UCD Computer Science
20
Array types
• An array is an ordered collection or numbered list of
values. The values can be primitive values, objects or even
other arrays, but all of the values in an array must be of the
same type.
–
–
–
–
byte b;
// byte is a primitive type
Byte[] arrayOfBytes;
//byte[] is an array type: array of byte
Byte[][] arrayOfArrayOfBytes; // byte[][] is another is another type: array of byte[]
Point[] points;
//Point[] is an array of point objects
UCD Computer Science
21
Creating Arrays
• Use the “new” keyword
• Arrays do not need to be initialized like objects do, however, so you
don’t pass a list of arguments between parentheses.
• BUT! You need to specify how many byte values you want it to hold.
• Once an array is created, it can never grow or shrink
• byte[] buffer = new byte[1024];
• string[] lines = new String[50];
UCD Computer Science
22
Using arrays
• You use square brackets to access the individual values contained in
the array. The elements of an array are numbered sequentially, starting
with 0. The number of an array element refers to the element. This
number is often called the index, and the process of looking up a
numbered value in an array is sometimes called indexing the array.
• To refer to a particular element of an array, simply place the index of
the desired element in square brackets after the name of the array
String[] responses = new String[2]; //Create an array of two strings
responses[0] = “Yes”;
//Set the first element of the array
responses[1] = “No”;
//Set the second element of the array
//Now read these array elements
System.out.println(question + “(“ + response[0] + “/” + responses[1] + “ )”;
UCD Computer Science
23
Multidimensional arrays
When the elements of an array are themselves arrays,
we say that the array is multi-dimensional
int[][] products = new products[10][10];
• Declares a variable named products to hold an
array of arrays of int
• Creates a 10-element array to hold 10 arrays of int
• Creates 10 more arrays, each of which is a 10element array of int. It assigns each of these 10
new arrays to the elements of the initial array. The
default value of every int element of each of these
10 new arrays is 0.
UCD Computer Science
24
Multidimensional arrays
The previous line is the same with the code
below:
int[][] products = new int[10][];
for (int i=0; i<10; i++)
products[i] = new int[10];
The new keyword performs the additional
initialisation automatically for you
Float[][][] globalTemperatureData = new float[360][180][100];
UCD Computer Science
25
Multidimensional arrays
Int[][] products = {
{0,0,0,0,0},
{0,1,2,3,4},
{0,2,4,6,8},
{0,3,6,9,12},
{0,4,8,12,16}
A 5x5 multiplication array
UCD Computer Science
};
26
Multidimensional arrays
arraycopy() method:
char[] text = “Now is the time”;
char[] copy = new char[100];
System.arraycopy(text,4,copy,0,10);
//move some of the text to later
elements,making room for instertions
System.arraycopy(copy,3,copy, 6,7)
UCD Computer Science
27
Multidimensional arrays
import java.util.Arrays;
int[] intarray = new int[] {10,5,7,-3};
Arrays.sort(intarray);
int pos = Arrays.binarySearch(intarray, 7);
pos = Arrays.binarySearch(intarray,12);
//An array of integers
//sort it in place
//Value 7 is found at index 2
//not found, negative return value
//arrays of objects can be sorted and searched too
String[] strarray = new String[] { “new”, “is”, “the”, “time”);
Arrays.sort(strarray); //{“is”, “now”, “the”, “time”}
//arrays equals() compares all elements of two arrays
String[] clone = (String[]) strarray.clone();
boolean b1 = Arrays.equals(strarry, clone); // Yes, they are equal
//arrays.fill() initialises array elements
byte[] data = new byte[100];
//an empty array: elements set to 0
Arrays.fill(data, (byte) –1);
//Set them all to –1
Arrays.fill(data,5,10,(byte) –2); //set elements 5,6,7,8,9 to -2
UCD Computer Science
28
Arrays
•
•
Java has one built-in “primitive” data structure
When array is created, its capacity must be specified (with any integer
expression!) and then can’t change
System.out.println("Enter the number of cities >");
int ncities =
Integer.valueOf(stdin.readLine()).intValue();
int rainfall[ncities];
String name[ncities];
for (int i = 0; i < cities.length; i++) {
System.out.print("City " + i + " name > ");
name[i] = stdin.readLine();
System.out.print("City " + i + " rainfall > ");
rainfall[i] =
Integer.valueOf(stdin.readLine()).intValue();
}
UCD Computer Science
29
Input and Output streams
The java.io package defines a large number of
classes for reading and writing streaming, or
sequential, data. The InputStream and
OutputStream classes are for reading and writing
streams, while the Reader and Writer classes are
for reading and writing streams of characters.
Streams can be nested, meaning you might read
characters from a FilterReader object that reads
and processes characters from an underlying
Reader stream. This underlying Reader stream
might read bytes from an InputStream and convert
them to characters.
UCD Computer Science
30
Read lines of input the user types
import java.io.*;
BufferedReader console = new Bufferedreader(new
InputStreamReader(System.in));
System.out.print(“What is your name:”);
String name = null;
try {
name = console.readLine(); }
catch (IOException e) {name = “<“ + e + “>”;}
System.out.println(“Hello “ + name);
UCD Computer Science
31
Reading lines of text from a file
String filename = System.getProperty(“user.home”) +
File.separator + “.cshrc”;
try {
BufferedReader in = new BufferedReader(new
FileReader(filename));
String line;
while((line = in.readLine()) !=null) {
System.out.println(line);}
in.close();
}
catch (IOException e) {
//Handle FileNootFoundException etc..
}
UCD Computer Science
32
Print text to Output Stream
try {
File f = new File(homedir, “.config”);
PrintWriter out = new PrintWriter(new
FileWriter(f));
out.println(##Automatically generated config file.
DO NOT EDIT”);
out.close(); //We’re done writing
}
catch (IOException e) {/*Handle exceptions*/}
UCD Computer Science
33
Not all files contain text, however. The following lines of code treat a file as a stream of bytes
and read the bytes into a large array
try {
File f;
//file to read
int filesize = (int) f.length();
//figure out the file size
byte[] data = new byte[filesize]; //create an array that is big enough
//create a stream to read the file
DataInputStream in = new DataInputStream(new FileInputStream(f));
in.readFully(data);
in.close();
}
catch (IOException e) {/*Handle exceptions */}
UCD Computer Science
34
How to use stream classes from java.util.zip to compute a checksum of data and then compress
the data while writing it to a file
import java.io.*;
import java.util.zip.*;
try {
File f;
//file to write to
byte[] data;
//data to write
Checksum check = new Adler32()
//an object to compute a simple checksum
//create a stream that writes bytes to the file f
FileOutputStream fos = new FileoutputStream(f);
//create a stream that compresses bytes and writes them to fos
GZIPOutputStream gzos = new GZIPOutputStream(fos);
//create a stream that computes a checksum on the bytes it writes to gzos
CheckedOutputStream cos = new CheckedOutputStream(gzos,check);
cos.write(data);
//now write the data to the nested streams
cos.close();
//close down the nested chain of streams
long sum = check.getValue();//obtain the computed checksum
}
catch (IOException e) {/* handle exceptions */}
UCD Computer Science
35
Sample practical problem
• R1.13 - write a Java function that takes an integer n and
returns the sum of the odd integers smaller than n.
class R113 {
static int oddsum(int x) {
…
return …;
}
}
Assumption: presumably the sum of all positive ints  x !
We need to loop over all odd integers less than x
We need a variable to store the sum
UCD Computer Science
36
R113 - continued
int sum = 0;
for (int i = 1; i<=x; i+=2) {
… // i=1,3,5,…
}
Before proceeding… does this loop stop at the
correct value of i??
UCD Computer Science
37
R113 - continued
int sum = 0;
for (int i = 1; i<x; i+=2) {
sum += i;
}
// now sum = sum of all odd integers less than x
Does this handle negative values of x properly?
Does this handle zero properly?
Does this handle one properly?
Hint: what is the minimum number of times
any “for” loop will execute!
UCD Computer Science
38
R113 - putting it all together
class R113 {
static int oddsum(int x) {
if (x<2) return 0; // special case!
int sum = 0;
for (int i=1; i<x; i+=2) {
sum += i;
}
return sum;
}
public static void main(String[] args) {
int i = 6; // “regular” input
int osi = oddsum(i);
System.out.println("got " + osi + " should be 9");
int j = -10; // problem with negative inputs?
int osj = oddsum(j);
System.out.println("got " + osj + " should be 0");
int k = 5; // problem with odd inputs?
int osk = oddsum(k);
System.out.println("got " + osk + " should be 4");
}
}
UCD Computer Science
39
Object-oriented design
• Learning the basic building blocks of programming is
straightforward...
• On the other hand.... Designing/implementing large
software systems is part art, part craft, part science, and
takes years to learn.
• Well-designed and built software is...
– Correct - the code must do what it is supposed to
– Efficient - it should do so as rapidly as possible
– Reusable - the code should be sufficiently generic so that it can
be used again in related systems
– Readable - humans read code too, not just machines!
– Extensible - the code should be easily modified to handle
modified requirements
...
• Read Ch 2; complete Practical!
UCD Computer Science
40
Three Fundamental Ideas
• Three ways to “think like a computer scientist” in
order to create high-quality software
– Abstraction
– Encapsulation
– Modularity
• These are perhaps the most fundamental ideas in
all of computer science
UCD Computer Science
41
1. Abstraction
• Abstraction = distill complex software system down to a its
fundamental/primitive components/properties/functions
• Your simplified, abstract view of the problem will ignore
(“abstract away”) from [relatively] unimportant details and
capture the “essense” of the problem
• Analogy. A good company manager doesn’t get bogged down in
details, but rather has a high-level perspective. However: this
works only when the lower-level processes are understoof well
enough to know what can be ignored and what must be managed.
• Example. Write program to convert from €£¥$
Don’t write one function to convert €£, another for €$, etc
Instead write one generic conversion function that takes as a
parameter the exchange rate
• Why? Correctness: easier to verify rounding is handled properly
(only need to look at one function); Extensable: easier to add new
currencies; Reusability: easier to extend to ºFºC, m2acres etc
UCD Computer Science
42
2. Encapsulation
• Encapsulation = design code so that each component is a
“black box”: other components don’t need to know internal
details in order to use on another
• Analogy. The manager of a hotel conference center relies on the
Catering Dept, the Cleaning staff, the Audio/Visual staff. But she
shouldn’t need to know in detail how these other organizations do
their job (eg, which supplies the caterer uses, how many window
cleaners the Cleaning dept employs, etc)
• Example. A application used by the Accounting department
shouldn’t need to know anything about how the exchange rate
function works in detail in order to invoke it.
• Why? Correctness: If acounting app relies on implementation
details of the exchange rate, harder to to know that the acoutning
software works properly; Extendability: If exhange rate is
modified, then aounting app probably needs to be updated too, etc
UCD Computer Science
43
3. Modularity
• Modular = program is organized so that the various
functions/properties are cleanly divided into separate units of
code
• Analogy. The Cleaners, Caterers, Accountants, etc all have welldefined and distinct positions in the management hierarchy.
• Example. The exchange rate just converts prices -- it doesn’t
print them, or store them in files, or verify them for accuracy, or
compare them to competitor’s prices, or... These may all be
essential funtions of the accounting software, but they must not be
the responsibility of the exchange rate code.
• Why? Modularity makes it easier to validate, understand, extend,
analyze, etc the system.
UCD Computer Science
44
Modularity - Example
Building
Apartment
Low-rise
apartment
High-rise
apartment
UCD Computer Science
House
Two- Story
house
Commercial
building
Ranch
Skyscraper
45
Modularity - example
• “Write a function to compute the interest earned on an amount £p
invested at an annual rate of R% over a period of T years”
• Right, good, modular, clean, organized, ...
double earnedInterest(double p, double r, int y) {
if (y==0) return p;
else
return earnedInterest(p,r,y-1)*(1+r);
}
• Wrong, bad, unmodular, complicated, messy, ...
double earnedInterest(double p, double r, int y) {
if (y==0) {
System.out.println(“No interest in first year”);
return p;
} else {
double prev = earnedInterest(p,r,y-1);
double new = prev*r;
double tot = prev + new;
System.out.println(“Interest from prev years = “ +
prev + “; year “ + y + “ = “ + new +
“; total interest = “ + tot);
return totInterest;
}
}
UCD Computer Science
46
Are these principles sacred?
• These are principles (“modular designs are preferable”) , not laws
(“valid Java statements end with a semicolon”)
• Sometimes it is necessary to violate one or more of these
principles (usually for the sake of efficiency)
• Analogy. The Cleaners and Caterers share a sink in order to save
space & money, and Fred works for the Caterers in the afternoon
and the Accounting Dept in the morning.
• Example. Suppose the Accounting app needs to calulate 10,000
exchange rates at a time. It is much to slow to invoke the
exchange mechanism 10,000 separate times, so perhaps it should
be extended to handle bulk transactions. Result: the exchange
code is more complicated, harder to maintain, less generic -- but
the benefit is probably worth the cost
UCD Computer Science
47
Using these ideas in Java (& other OO languages)
classes
inheritance
interfaces
Object-oriented
programming
constructs to help
you write code
that is more...
•Abstract
•Encapsulated
•Modular
Java does not force you to write modular/abstract/encapsulated code
You can get all the rope you want to hang yourself.
Designing good code takes more thought, and sometimes more code.
The advantages won’t always be obvious in the tiny programs we
build in the practicals. Nevertheless, we’re going to insist you stick
with these principles since they will be crucial in the future.
UCD Computer Science
48
Inheritance
• Data and functions are often hierachially structured
Numeric Conversion
Linear Conversion
Logarthmic Conversion
For. Exch
F/C
¥/£
£/$
m2 /acres
€/£
• OO inheritance constructs help you to directly encode
such valuable information directly in your code
Simple conrete example: Figure 2.4
UCD Computer Science
49
Dispatching & overloading
• But what does inheritance really “mean”??!?
What do such classes “do”??!?
• Answer: Given some object O of class C, if the code
calls function M on O (ie, “O.M()”) then:
– 1. Look for a method M in C and execute it if found
– 2. If M not found in C, try C’s superclass.
– 3. Repeat step 2 all the way up the class hierarchy to the root,
and give error if M isn’t ever found
• “Overleading”: if M is defined more than once, only the
definition closest to C is executed
• Overloading is an incredibly powerful tool for designing
software: “A $/£ exchange rate mechanism is just like a
generic linear converter, except for specific functions X,
Y, Z.”
UCD Computer Science
50
Example
• G&T pages 68-75: Numeric progressions
• Simple incremental progression:
– 1, 1+1=2, 2+1=3, 3+1=4, 4+1=5, ...
• General arithmetic progression:
– x, x+y, x+2y, x+3y, x+4y, x+5y, ...
• Geometric progression:
– x, x2, x3, x4, x5, ...
• Fibonacci progression
– x, y, x+y, x+2y, 2x+3y, 3x+5y, 5x+8y, ...
• Study this example until you vomit!
UCD Computer Science
51
Numeric progressions Example
public class Progression {
protected long first;
protected long cur;
Progression () {
cur = first = 0;}
protected long firstValue() {
cur = first;
return cur;}
protected long nextValue() {
return ++cur;}
public void printProgression(int n) {
System.out.print(firtsValue());
for (int i=2; i <= n; i++)
System.out.print(“ “ + nextValue());
System.out.println();
}
}
UCD Computer Science
52
Geometric progressions Example
class GeomProgression extends Progression{
protected long inc;
GeomProgression () {
this(2);}
GeomProgression (long base) {
first = base;
cur = first;}
protected long nextValue() {
cur *= first;
return cur;}
}
UCD Computer Science
53
Numeric progressions Example
class FibonacciProgression extends Progression{
long prev;
FibonacciProgression () {
this(0,1);}
FibonacciProgression (long value1, long value2) {
first = value1;
prev = value2 – value1;}
protected long nextValue() {
long temp = prev;
prev = cur;
cur += temp;
return cur;}
}
UCD Computer Science
54
Inheritance diagram
Class: Progression
Fields: long first, long cur
Methods: Progression(), long
firstValue(), long
nextValue(), void
printProgression(int)
Class: ArithProgression
Class: GeomProgression
Class: FibonacciProgression
Fields: long inc
Fields:
Fields: long prev
Methods: ArithProgression(),
ArithProgression(long), long
nextValue()
Methods:
GeomProgression(),
GeomProgression(long),
long nextValue()
Methods:
FibonacciProgression(),
FibonacciProgression(long,long),
long nextValue()
UCD Computer Science
55
Testing the progression classes
class Tester{
public static vid main(String[] args) {
System.out.println(“Arithmetic progressions with default increment”) ;
prog = new ArithProgression();
prog.printProgression(10);
System.out.println(“Arithmetic progressions with increment 5:”) ;
prog = new ArithProgression(5);
prog.printProgression(5);
System.out.println(“Geometric progressions with default base”) ;
prog = new GeomProgression();
prog.printProgression(10);
System.out.println(“Geometric progressions with base 3:”) ;
prog = new GeomProgression(3);
prog.printProgression(3);
System.out.println(“Fibonacci progressions with default default start values”) ;
prog = new FibonacciProgression();
prog.printProgression(10);
System.out.println(“Fibonacci progressions with start values 4 and 6:”) ;
prog = new FibonacciProgression(4,6);
prog.printProgression(10);
}
}
UCD Computer Science
56
Output
Arithmetic progression with default increment:
0123456789
Arithmetic progression with increment 5:
0 5 10 15 20 25 30 35 40 45
Geometric progression with default base:
2 4 8 16 32 64 128 256 512 1024
Geometric progression with base 3:
3 9 27 81 243 729 2187 6561 19683 59049
Fibonacci progression with default start values:
0 1 1 2 3 5 8 13 21 34
Fibonacci progression with start values 4 and 6:
4 6 10 16 26 42 68 110 178 288
UCD Computer Science
57
Interfaces
• Encapsulation says a class C should be a “black box” --class D that refers to class C needn’t know anything
about the internal details of how C “does its job”
• Java interface construct enourages encapsulation:
an interface is like a class, except there are no
method definitions -- just “signatures” indicating
what methods can be invoked on classes that
implement the interface
• Note that implementing an interface is completely
different from extending a class!!
– Implementing an interface means “I promise to support all of
the operations specified by the interface”
– Extending a class means “I am similar to the parent class,
except in the following ways...”
UCD Computer Science
58
Example - Inheritance
interface CurrencyExchanger {
double convert(double amount);
}
If your are building an accounting application that needs
currency conversion, this interface specification tells you
everything you need to know to decide whether these
classes satisfy your requirements.
You do not need to see code for a class that
actually does the coversion....
UCD Computer Science
59
Example - 2
class SterlingToDollarExchanger implements CurrencyExchanger {
SterlingToDollarExchanger() {}
double convert(double amount) {
return amount*1.642;
}
}
class YenToEuro Exchanger implements CurrencyExchanger {
YenToEuroExchanger() {}
double convert(double amount) {
Oops!
return amount*0.00384;
Duplicated code
}
}
UCD Computer Science
60
Example - 3
class GenericExchanger implements CurrencyExchanger {
double rate;
GenericExchanger(double _rate) {
CurrencyExchanger
rate = _rate;
}
double convert(double amount) {
return amount*rate; // only need to specify formula once!
}
GenericExchanger
}
class SterlingToDollarExchanger extends GenericExchanger {
SterlingToDollarExchanger() {
super(1.642);
£/$
¥/€
}
}
class YenToEuroExchanger extends GenericExchanger {
YenToEuroExchanger() {
super(0.00384);
}
}
UCD Computer Science
61
Thinking like a computer scientist
• Doctors see the world in terms of
illness, health, prevention, medicine, ...
• Architects see the world in terms of
spaces, buildings, ocupants, engineering
constraints, ...
• Managers see the world in terms of
people, roles, tasks, shedules, skills,
training, hierarchy, evaluation, ...
They wouldn’t be
good at their job
if they didn’t
• Software engineers see the world in
computational terms: components,
interactions, objects, data, behavior, methods,
abstractions, protocols, complexity, ...
• Soon you will too
UCD Computer Science
62