Transcript Java Software Solutions Foundations of Program Design

Slide #1
Lecture #10 - Design with Interfaces,
Recursion, Trees
•
In this lecture:
•
•
•
•
Some examples of design with interfaces
Runtime Stack
Recursion
Trees and algorithms on trees
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #2
The Clock Alarm Problem
•
•
•
•
Recall the Alarm Clock Example
Whenever the alarm time has been reached, an “alarm
event” occurred, which caused the alarm clock to activate
an alarm
In your exercise, the clock opened a window with the
proper alarm message
This is not general enough:
• We wish to have a technique which enables us to invoke a
method on an arbitrary object of our choice when an alarm
occurs
• Sometimes there are several objects which are interested in
this event
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #3
Multiple Listeners to an Event
Alarm
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #4
The “Observer-Observable” Pattern
•
•
•
•
•
This pattern enables several “observers”, which
are interested in a certain event, to get notified
when this event occurs
The event is generated by an “observable” object
Sometimes the “observers” are called “listeners”
To get notified about an event, an observer
registers itself at the observable object
The observable maintains a list of interested
observers, and notifies them when the event
occurs
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #5
Example: Alarm Clock
/**
* A listener interface for receiving alarm events
* from a clock
*/
public interface AlarmClockListener {
public void alarmActivated(AlarmEvent e);
}
public class AlarmEvent {
Object eventSource;
public AlarmEvent(Object EventSource) {
this.eventSource = eventSource;
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #6
Example: Alarm Clock
public AlarmClock extends Clock {
private Clock alarmTime;
private Vector listeners;
// constructor...
public void secondElapsed() {
super.secondElapsed();
if (alarmTimeReached()) {
notifyListeners();
}
}
// returns true if alarm time has been reached
private boolean alarmTimeReached() {
if (getHours() == alarmTime.getHours() &&
getMinutes() == alarmTime.getMinutes() &&
getSeconds() == alarmTime.getSeconds())
return true;
return false;
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #7
Example: Alarm Clock
/**
* Adds an alarm listener to this clock
*/
public void
addAlarmClockListener(AlarmClockListener listener) {
listeners.add(listener);
}
/**
* Notifies all alarm listeners of an alarm event
*/
private void notifyListeners() {
AlarmEvent event = new AlarmEvent(this);
for (int i = 0; i < listeners.size(); i++) {
AlarmClockListener listener =
(AlarmClockListener)listeners.getElementAt(i);
listener.alarmActivated(event);
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #8
Example: Alarm Clock
public class InterestedListener
implements AlarmClockListener {
// …
public InterestedListener(…) {
// ...
}
public void alarmActivated(AlarmEvent event) {
System.out.println(“Wake me up before you go go”);
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #9
GUI Components: Observable Objects
•
•
•
•
Java GUI components are observable objects
This means that any listener can register for events
fired from any GUI component
For example, a button can fire an “action
performed” event whenever it is pressed
Interested objects can register themselves as
listeners to an “action event” fired by a button and
implement the ActionListener interface
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #10
Example: Button
import java.awt.*;
import java.awt.event.*;
public class ButtonExample extends Frame
implements ActionListener {
private Button button = new Button(“press!”);
public ButtonExample() {
add(button);
button.addActionListener(this);
}
public void actionPerformed(ActionEvent e) {
System.out.println(“Button Clicked”);
}
public static void main(String[] args) {
Frame f = new ButtonExample();
f.setSize(100,100);
f.setVisible(true);
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #11
The Runtime Stack
•
•
•
•
During the execution of a program, there is a
sequence of method calls
The interpreter (or the operating system) has to
keep track of the calling sequence and of the
parameters
This is done in the main memory using a runtime
stack
A copy of each formal formal parameter (the
actual parameter), which can be a primitive type
or a reference, is pushed onto the stack
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #12
Example: Runtime Stack
public class Test {
public static void main(String[] args) {
f(3,2);
}
public static void f(int a, int b) {
Point p = new Point(a,b);
g(p,9);
h();
}
public static void g(Point p, int c) {
p.setX(5);
p.setY(7);
c = 15;
}
public static void h() {
// ...
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #13
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #14
f
a = 3
b = 2
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #15
g
p = Point(3,2)
c = 9
f
a = 3
b = 2
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #16
f
a = 3
b = 2
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #17
h
f
a = 3
b = 2
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #18
f
a = 3
b = 2
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #19
main
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #20
Recursion -- Introduction
•
•
•
Recursion is a fundamental programming
technique that can provide an elegant solution
certain kinds of problems
Recursion is often used in programs
In certain cases recursion dramatically simplifies
the readability of a program, and provides a
simple solution to complex problems
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #21
Recursive Thinking
•
•
•
A recursive definition is one which uses the word
or concept being defined in the definition itself
Consider the definition:
A folder is a collection of zero or more file and/or
folders
When defining a folder we use the defined term in
the definition body.
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #22
Recursive Definitions
•
Consider the following list of numbers:
24, 88, 40, 37
•
Such a list can be defined as
A LIST is a:
or a:
•
•
number
number
comma
LIST
That is, a LIST is defined to be a single number, or
a number followed by a comma followed by a
LIST
The concept of a LIST is used to define itself
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #23
Recursive Definitions
•
The recursive part of the LIST definition is used
several times, terminating with the non-recursive
part:
number comma LIST
24
,
88, 40, 37
number comma LIST
88
,
40, 37
number comma LIST
40
,
37
number
37
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #24
Infinite Recursion
•
•
•
•
•
All recursive definitions have to have a nonrecursive part
If they didn't, there would be no way to terminate
the recursive path
Such a definition would cause infinite recursion
This problem is similar to an infinite loop, but the
non-terminating "loop" is part of the definition
itself
The non-recursive part is often called the base
case
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #25
Recursive Definitions
•
•
•
•
N!, for any positive integer N, is defined to be the
product of all integers between 1 and N inclusive
This definition can be expressed recursively as:
1! = 1
N! = N * (N-1)!
The concept of the factorial is defined in terms of
another factorial
Recursive definitions are common in mathematics
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #26
Recursive Definitions
5!
120
5 * 4!
24
4 * 3!
3 * 2!
6
2 * 1!
2
1
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #27
Recursion - Yet Another Form of Reduction
•
•
•
When we have a problem that can be defined
recursively, we can solve it using recursion
When we solve a problem using recursion, we
reduce the problem to a problem that is similar to
the original and is different only by a parameter
Example:
Problem p(5) - compute 5!.
5!=4!*5, so we can reduce the problem to the
problem of finding 4!. But 4!=3!*4, so we can
reduce further. We end up with the problem of
finding 1! which is simple.
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #28
Recursive Programming - Behind the Scenes
•
•
•
•
A method in Java can invoke itself; if set up that
way, it is called a recursive method
The code of a recursive method must be structured
to handle both the base case and the recursive case
Each call to the method sets up a new execution
environment, with new parameters and local
variables
As always, when the method completes, control
returns to the method that invoked it (which may
be an earlier invocation of itself)
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #29
Example - n!
public static long factorial(long n) {
if (n == 0) {
return 1;
}
return n * factorial(n-1);
}
public static long factorial(long n) {
return (n == 0) ? 1 : n * factorial(n-1);
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #30
Example: Sum of Integers - Definition
•
•
Consider the problem of computing the sum of all
the numbers between 1 and any positive integer N
This problem can be recursively defined as:
N
N-1
i =
N +
i=1
The Interdisciplinary Center, Herzelia
N-2
i = N +(N-1)+
i=1
i + ...
i=1
Lecture 10, Introduction to CS - Information Technologies
Slide #31
Example - Sum of Integers - Program
// Compute the sum of the series 1,2,..,n
// n is given as a command line argument
class ArithmeticalSum {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
System.out.println(sum(n));
}
static int sum(int n) {
return (n == 1) ? 1 : n + sum(n-1);
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #32
Sum of Integers Call Stack
result = 6
main
sum(3)
result = 3
sum
sum(2)
sum
result = 1
sum(1)
sum
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #33
When Should Recursion be Used?
•
•
•
•
Note that just because we can use recursion to
solve a problem, doesn't mean we should
For instance, we usually would not use recursion
to solve the sum of 1 to N problem, because the
iterative version is easier to understand
However, for some problems, recursion provides
an elegant solution, often cleaner than an iterative
version
You must carefully decide whether recursion is the
correct technique for any problem
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #34
Example Depth First Search (DFS)
Recall the definition of the term folder
• Suppose we want to list all the files under a given
folder. We can do it as follows:
list folders under(Folder f) :
Let L be the list of all files and folders directly
under f.
For each element f1 in L :
if f1 is a folder : list folders under f1
otherwise : print the name of f1
•
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #35
File Listing Example
import java.io.File;
// List all the files under a given folder
// Usage: java ListFiles <folder-name>
class ListFiles {
/**
* List of the files under a given folder
* given as an argument.
*/
public static void main(String[] args) {
listFiles(new File(args[0]));
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #36
File Listing Example
// List all files under a given folder
public static void listFiles(File folder) {
String[] files = folder.list();
for (int i=0; i<files.length; i++) {
File file = new File(folder, files[i]);
if (file.isDirectory()) {
listFiles(file);
}
else {
System.out.println(file);
}
}
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #37
Indirect Recursion
•
•
•
•
•
A method invoking itself is considered to be direct
recursion
A method could invoke another method, which
invokes another, etc., until eventually the original
method is invoked again
For example, method m1 could invoke m2, which
invokes m3, which in turn invokes m1 again
This is called indirect recursion, and requires all
the same care as direct recursion
It is often more difficult to trace and debug
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #38
Indirect Recursion
m1
m2
m3
m1
m2
m1
The Interdisciplinary Center, Herzelia
m3
m2
m3
Lecture 10, Introduction to CS - Information Technologies
Slide #39
Example: Maze
•
•
•
•
A maze is solved by trial and error -- choosing a
direction, following a path, returning to a previous
point if the wrong move is made
As such, it is another good candidate for a
recursive solution
The base case is an invalid move or one which
reaches the final destination
Solving a maze can be done in a similar manner to
that of listing the files under a given directory.
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #40
d d d
d
d
d
d d d d
d
d d
d d
d
d
d
d d d d d
d
d d d d
d
d
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #41
Example: Binary Search
Binary Search(element, left, right, arr)
if (left == right) // termination condition
return (arr[left] == element);
else {
middle = (left + right) / 2;
if (a[middle] < element)
Binary Search(element,left,middle-1,arr);
if (a[middle] > element)
Binary Search(element,left+1,right,arr);
return true; // a[middle] == element;
}
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #42
Example: Binary Tree
•
Definition: A binary tree is:
• A leaf (a single vertex)
• or a vertex connected to two disjoint binary trees,
left tree and right tree
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #43
A Binary Tree
A
B
D
G
C
E
H
The Interdisciplinary Center, Herzelia
F
I
Lecture 10, Introduction to CS - Information Technologies
Slide #44
Example: Expression Tree
+
*
/
7
-
2
3
+
14
2
The Interdisciplinary Center, Herzelia
9
5
Lecture 10, Introduction to CS - Information Technologies
Slide #45
Definition of Expression: Resemblance to Tree
•
An Expression is:
• A number
• or (exp1 op exp2) where exp1 and exp2 are
expressions, op is an operator
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #46
An Interface to Trees
•
for a tree t:
• t.leftSubTree() returns the left sub-tree of t
• t.rightSubTree() returns the right sub-tree
of t
• t.isLeaf() returns true if t is a leaf
• t.getRoot() returns the value of the root
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #47
Computing the Value of an Expression Tree
int Expression Tree Value(t)
if (t.isLeaf())
return t.getRoot()
else
int left = Expression Tree Value(t.leftSubTree());
int right = Expression Tree Value(t.rightSubTree());
operator op = t.getRoot();
return (left op right); // switch to cases...
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #48
Printing a Tree
•
•
•
Inorder: print left subtree, print root, print right
sub tree
Preorder: print root, print left subtree, print right
subtree
Postorder: print left subtree, print right subtree,
print root
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #49
Polish Notation
•
•
Definition: The polish notation of an expression is
the postorder scan of the tree
Example:
• For the binary tree presented earlier, the polish
notation representation is:
• 7 3 / 2 * 14 2 5 - + 9 - +
•
Computing a polish notation expression value:
using a stack
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #50
Some Facts on Trees
•
•
•
•
A tree with n vertices has n-1 edges
A full binary tree with k levels has has 20 + 21 +
… + 2k = 2k+1 - 1 vertices.
If the binary tree is not full, then it has at least k+1
vertices.
What is the height of a binary tree with n vertices?
(number of levels)?
• A full binary tree has height has k = O(log n)
levels.
• A “slim” binary tree has k = O(n) levels.
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #51
Binary Search Tree
•
A binary tree with a special restriction: at each
vertex, the value of the vertex is
• greater than or equal to any vertex in the left
subtree, and
• smaller than any vertex in the right subtree
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #52
Example: Binary Search Tree
15
6
5
15
9
26
8
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies
Slide #53
Algorithms on Binary Trees
•
•
•
Printing in order: inorder…
Finding an element: recursion…
Finding minimal element:
• Base case: if leaf or empty left subtree, return root
• Recursion: return minimum of left subtree.
The Interdisciplinary Center, Herzelia
Lecture 10, Introduction to CS - Information Technologies