Transcript Iteration

Iteration
Chapter 4
Spring 2007
CS 101
Aaron Bloomfield
1
Java looping
 Options
 while
 do-while
 for
 Allow programs to control how many times a statement list is
executed
2
Averaging values
3
Averaging
 Problem
 Extract a list of positive numbers from standard input and
produce their average
 Numbers are one per line
 A negative number acts as a sentinel to indicate that
there are no more numbers to process
 Observations
 Cannot supply sufficient code using just assignments and
conditional constructs to solve the problem
 Don’t how big of a list to process
 Need ability to repeat code as needed
4
Averaging
 Algorithm
 Prepare for processing
 Get first input
 While there is an input to process do {
 Process current input
 Get the next input
 }
 Perform final processing
5
Averaging
 Problem
 Extract a list of positive numbers from standard input and
produce their average
 Numbers are one per line
 A negative number acts as a sentinel to indicate that
there are no more numbers to process
 Sample run
Enter positive numbers one per line.
Indicate end of list with a negative number.
4.5
0.5
1.3
-1
Average 2.1
6
public class NumberAverage {
// main(): application entry point
public static void main(String[] args) {
// set up the input
// prompt user for values
// get first value
// process values one-by-one
while (value >= 0) {
// add value to running total
// processed another value
// prepare next iteration - get next value
}
// display result
if (valuesProcessed > 0)
// compute and display average
else
// indicate no average to display
}
}
int valuesProcessed = 0;
double valueSum = 0;
// set up the input
Scanner stdin = new Scanner (System.in);
// prompt user for values
System.out.println("Enter positive numbers 1 per line.\n"
+ "Indicate end of the list with a negative number.");
// get first value
double value = stdin.nextDouble();
// process values one-by-one
while (value >= 0) {
valueSum += value;
++valuesProcessed;
value = stdin.nextDouble();
}
// display result
if (valuesProcessed > 0) {
double average = valueSum / valuesProcessed;
System.out.println("Average: " + average);
} else {
System.out.println("No list to average");
}
Program Demo

NumberAverage.java
9
While syntax and semantics
while
(
Expression
)
Action
Logical expression that
determines whether Action
is to be executed
Action is either a single
statement or a statement
list within braces
10
While semantics for averaging problem
Test expression is evaluated at the
start of each iteration of the loop.
// process values one-by-one
while ( value >= 0 ) {
// add value to running total
valueSum += value;
// we processed another value
++valueProcessed;
// prepare to iterate – get the next input
value = stdin.nextDouble();
}
If test expression is true, these statements
are executed. Afterward, the test expression
is reevaluated and the process repeats
11
While Semantics
Expression is
evaluated at the
start of each
iteration of the
loop
Expression
If Expression is
true, Action is
executed
true
Action
false
If Expression is
false, program
execution
continues with
next statement
12
Suppose input contains: 4.5 0.5 1.3 -1
Execution Trace
valuesProcessed
int valuesProcessed = 0;
double valueSum = 0;
0
1
2
3
valueSum
4.5
6.3
5.0
0
value
0.5
1.3
4.5
-1
average
2.1
double value = stdin.nextDouble();
while (value >= 0) {
valueSum += value;
++valuesProcessed;
value = stdin.nextDouble();
}
if (valuesProcessed > 0) {
double average = valueSum / valuesProcessed;
System.out.println("Average: " + average);
}
else {
System.out.println("No list to average");
}
13
What do these pictures mean?













Light beer
Dandy lions
Assaulted
peanut
Eggplant
Dr. Pepper
Pool table
Tap dancers
Card shark
King of pop
I Pod
Gator aide
Knight mare
Hole milk
14
Converting text to lower case
15
Converting text to strictly lowercase
public static void main(String[] args)
{
Scanner stdin = new Scanner (System.in);
System.out.println("Enter input to be converted:");
String converted = "";
while (stdin.hasNext()) {
String currentLine = stdin.nextLine();
String currentConversion =
currentLine.toLowerCase();
converted += (currentConversion + "\n");
}
System.out.println("\nConversion is:\n" +
converted);
}
16
Sample run
An empty line
was entered
A Ctrl+z was
entered. tI is the
Windows escape
sequence for
indicating
end-of-file
17
Program Demo

LowerCaseDisplay.java
18
Program trace
public static void main(String[] args)
{
Scanner stdin = new Scanner (System.in);
System.out.println("Enter input to be converted:");
String converted = "";
while (stdin.hasNext()) {
String currentLine = stdin.nextLine();
String currentConversion =
currentLine.toLowerCase();
converted += (currentConversion + "\n");
}
System.out.println("\nConversion is:\n" +
converted);
19
Program trace
The append assignment operator updates the representation
of converted to include the current input line
converted += (currentConversion + "\n");
Representation of lower case
conversion of current input line
Newline character is needed
because method nextLine()
"strips" them from the input
20
Another optical illusion
21
Loop Design & Reading From
a File
22
Loop design
 Questions to consider in loop design and analysis
 What initialization
expression?
is
necessary
for
the
loop’s
test
 What initialization is necessary for the loop’s processing?
 What causes the loop to terminate?
 What actions should the loop perform?
 What actions are necessary to prepare for the next
iteration of the loop?
 What conditions are true and what conditions are false
when the loop is terminated?
 When the loop completes what actions are need to
prepare for subsequent program processing?
23
Reading a file
 Background
Same Scanner class!
filename is a String
Scanner fileIn = new Scanner (new File (filename) );
The File class allows access to files
It’s in the java.io package
24
Reading a file
 Class File
 Allows access to files (etc.) on a hard drive
 Constructor File (String s)
 Opens the file with name s so that values can be extracted
 Name can be either an absolute pathname or a pathname
relative to the current working folder
25
Reading a file
Scanner stdin = new Scanner (System.in);
System.out.print("Filename: ");
String filename = stdin.nextLine();
Scanner fileIn = new Scanner (new File (filename));
String currentLine = fileIn.nextLine();
while (currentLine != null) {
System.out.println(currentLine);
currentLine = fileIn.nextLine();
}
Close
Determine
Set
Process
Display
Get
Make
up
first
next
sure
the
standard
file
current
lines
line
line
file
stream
got
fileone
stream
name
aline
input
line
by one
tostream
process
If not, loop is done
26
Today’s demotivators
27
The For statement
29
The For Statement
The body of the loop iterates
while the test expression is
true
Initialization step
is performed only
After each iteration of the
once -- just prior int currentTerm = 1;
body of the loop, the update
to the first
expression is reevaluated
evaluation of the for ( int i = 0; i < 5; ++i ) {
test expression
System.out.println(currentTerm);
currentTerm *= 2;
The body of the loop displays the
}
current term in the number series.
It then determines what is to be the
new current number in the series
30
Evaluated once
at the beginning
of the for
statements's
execution
If ForExpr is true,
Action is
executed
After the Action
has completed,
the
PostExpression
is evaluated
ForInit
ForExpr
true
Action
ForUpdate
After evaluating the
PostExpression, the next
iteration of the loop starts
The ForExpr is
evaluated at the
start of each
iteration of the
loop
false
If ForExpr is
false, program
execution
continues with
next statement
for statement syntax
Logical test expression that determines whether the action and update step are
executed
Initialization step prepares for the
first evaluation of the test
expression
for
( ForInit
; ForExpression
Update step is performed after
the execution of the loop body
; ForUpdate
) Action
The body of the loop iterates whenever
the test expression evaluates to true
32
for vs. while
 A for statement is almost like a while statement
for ( ForInit; ForExpression; ForUpdate ) Action
is ALMOST the same as:
ForInit;
while ( ForExpression ) {
Action;
ForUpdate;
}
 This is not an absolute equivalence!
 We’ll see when they are different in a bit
33
Variable declaration
 You can declare a variable in any block:
while ( true ) {
int n = 0;
n++;
System.out.println (n);
}
System.out.println (n);
Variable n gets created
(and initialized) each time
Thus, println() always
prints out 1
Variable n is not
defined once while
loop ends
As n is not defined
here, this causes
an error
34
Variable declaration
 You can declare a variable in any block:
if ( true ) {
int n = 0;
n++;
System.out.println (n);
}
System.out.println (n);
Only difference
from last slide
35
Execution Trace
i
for ( int i = 0; i < 3; ++i ) {
0
3
2
1
System.out.println("i is " + i);
}
System.out.println("all done");
i is 0
i is 1
i is 2
all done
Variable i has gone
out of scope – it
is local to the loop
36
for vs. while

An example when a for loop can be directly translated into a while
loop:
int count;
for ( count = 0; count < 10; count++ ) {
System.out.println (count);
}

Translates to:
int count;
count = 0;
while (count < 10) {
System.out.println (count);
count++;
}
37
for vs. while
 An example when a for loop CANNOT be directly translated
into a while loop:
only difference
for ( int count = 0; count < 10; count++ ) {
System.out.println (count);
}
count is NOT defined here
 Would (mostly) translate as:
int count = 0;
while (count < 10) {
System.out.println (count);
count++;
}
count IS defined here
38
for loop indexing
 Java (and C and C++) indexes everything from zero
 Thus, a for loop like this:
for ( int i = 0; i < 10; i++ ) { ... }
 Will perform the action with i being value 0 through 9, but
not 10
 To do a for loop from 1 to 10, it would look like this:
for ( int i = 1; i <= 10; i++ ) { ... }
39
Nested loops
int m = 2;
int n = 3;
for (int i = 0; i < n; ++i) {
System.out.println("i is " + i);
for (int j = 0; j < m; ++j) {
System.out.println("
j is " + j);
}
i is 0
}
j is 0
j is 1
i is 1
j is 0
j is 1
i is 2
j is 0
j is 1
40
Nested loops
int m = 2;
int n = 4;
for (int i = 0; i < n; ++i) {
System.out.println("i is " + i);
for (int j = 0; j < i; ++j) {
System.out.println("
j is " + j);
}
}
i is 0
i is 1
j is
i is 2
j is
j is
i is 3
j is
j is
j is
0
0
1
0
1
2
41
How well do you understand for loops?
oo
...
so
oo
c.
..
da
I’m
at
a
ot
N
N
ot
w
el
l.
ll.
I’m
no
It’
s
y.
ki
n
tg
re
at
a
ith
w
ka
O
,b
u.
..
lit
t..
...
st
uf
fi
w
el
l–
Th
is
irl
y
5.
Fa
4.
w
el
l!
3.
20% 20% 20% 20% 20%
ry
2.
Very well! This stuff
is easy!
Fairly well – with a
little review, I’ll be
good
Okay. It’s not great,
but it’s not horrible,
either
Not well. I’m kinda
confused
Not at all. I’m
soooooo lost
Ve
1.
42
From Dubai
43
do-while loops
44
The do-while statement
 Syntax
do Action
while (Expression)
 Semantics
 Execute Action
 If Expression is true then
execute Action again
 Repeat this process until
Expression evaluates to
false
 Action is either a single
statement or a group of
statements within braces
Action
true
Expression
false
45
Picking off digits
 Consider
System.out.print("Enter a positive number: ");
int number = stdin.nextInt();
do {
int digit = number % 10;
System.out.println(digit);
number = number / 10;
} while (number != 0);
 Sample behavior
Enter a positive number: 1129
9
2
1
1
46
Guessing a number
 This program will allow the user to guess the number the
computer has “thought” of
 Main code block:
do {
System.out.print ("Enter your guess: ");
guessedNumber = stdin.nextInt();
count++;
} while ( guessedNumber != theNumber );
47
Program Demo

GuessMyNumber.java
48
while vs. do-while
 If the condition is false:
 while will not execute the action
 do-while will execute it once
while ( false ) {
System.out.println (“foo”);
}
do {
System.out.println (“foo”);
} while ( false );
never executed
executed once
49
while vs. do-while
 A do-while statement
statement as follows:
can
be
translated
into
a
while
do {
Action;
} while ( WhileExpression );
 can be translated into:
boolean flag = true;
while ( WhileExpression || flag ) {
flag = false;
Action;
}
50
How well do you understand do-while loops?
oo
...
so
oo
c.
..
da
I’m
at
a
ot
N
N
ot
w
el
l.
ll.
I’m
no
It’
s
y.
ki
n
tg
re
at
a
ith
w
ka
O
,b
u.
..
lit
t..
...
st
uf
fi
w
el
l–
Th
is
irl
y
5.
Fa
4.
w
el
l!
3.
20% 20% 20% 20% 20%
ry
2.
Very well! This stuff
is easy!
Fairly well – with a
little review, I’ll be
good
Okay. It’s not great,
but it’s not horrible,
either
Not well. I’m kinda
confused
Not at all. I’m
soooooo lost
Ve
1.
51
Today’s demotivators
52
Loop controls
54
The continue keyword

The continue keyword will immediately start the next iteration of the
loop
 The rest of the current loop is not executed
 But the ForUpdate part is, if continue is in a for loop
for ( int a = 0; a <= 10; a++ ) {
if ( a % 2 == 0 ) {
continue;
}
System.out.println (a + " is odd");
}

Output:
1
3
5
7
9
is
is
is
is
is
odd
odd
odd
odd
odd
55
The break keyword

The break keyword will immediately stop the execution of the loop
 Execution resumes after the end of the loop
for ( int a = 0; a <= 10; a++ ) {
if ( a == 5 ) {
break;
}
System.out.println (a + " is less than five");
}

Output:
0
1
2
3
4
is
is
is
is
is
less
less
less
less
less
than
than
than
than
than
five
five
five
five
five
56
Four Hobos
57
Four Hobos
 An example of a program that uses nested for loops
 Credited to Will Shortz, crossword puzzle editor of the New
York Times
 And NPR’s Sunday Morning Edition puzzle person
58
Problem
 Four hobos want to split up 200 hours of work
 The smart hobo suggests that they draw straws with numbers
on it
 If a straw has the number 3, then they work for 3 hours on 3
days (a total of 9 hours)
 The smart hobo manages to draw the shortest straw
 How many ways are there to split up such work?
 Which one did the smart hobo choose?
59
Analysis
 We are looking for integer solutions to the formula:
a2+b2+c2+d2 = 200
 Where a is the number of hours & days the first hobo
worked, b for the second hobo, etc.
 We know the following:
 Each number must be at least 1
 No number can be greater than 200 = 14
 That order doesn’t matter
 The combination (1,2,1,2) is the same as (2,1,2,1)
 Both combinations have two short and two long
straws
 We will implement this with nested for loops
60
Implementation
public class FourHobos {
public static void main (String[] args) {
for ( int a = 1; a <= 14; a++ ) {
for ( int b = 1; b <= 14; b++ ) {
for ( int c = 1; c <= 14; c++ ) {
for ( int d = 1; d <= 14; d++ ) {
if ( (a <= b) && (b <= c) && (c <= d) ) {
if ( a*a+b*b+c*c+d*d == 200 ) {
System.out.println ("(" + a + ", " + b
+ ", " + c + ", " + d + ")");
}
}
}
}
}
}
}
}
61
Program Demo

FourHobos.java
62
Results
 The output:
(2, 4, 6, 12)
(6, 6, 8, 8)
 Not surprisingly, the smart hobo picks the short straw of the
first combination
63
Today’s demotivators
64
Alternate implementation
 We are going to rewrite the old code in the inner most for
loop:
if ( (a <= b) && (b <= c) && (c <= d) ) {
if ( a*a+b*b+c*c+d*d == 200 ) {
System.out.println ("(" + a + ", " + b
+ ", " + c + ", " + d + ")");
}
}
 First, consider the negation of
( (a <= b) && (b <= c) && (c <= d) )
 It’s ( !(a <= b) || !(b <= c) || !(c <= d) )
 Or ( (a > b) || (b > c) || (c > d) )
65
Alternate implementation
 This is the new code for the inner-most for loop:
if ( (a > b) || (b > c)
continue;
}
if ( a*a+b*b+c*c+d*d !=
continue;
}
System.out.println ("("
+ c
|| (c > d) ) {
200 ) {
+ a + ", " + b + ", "
+ ", " + d + ")");
66
How well do you understand four hobos?
oo
...
so
oo
c.
..
da
I’m
at
a
ot
N
N
ot
w
el
l.
ll.
I’m
no
It’
s
y.
ki
n
tg
re
at
a
ith
w
ka
O
,b
u.
..
lit
t..
...
st
uf
fi
w
el
l–
Th
is
irl
y
5.
Fa
4.
w
el
l!
3.
20% 20% 20% 20% 20%
ry
2.
Very well! This stuff
is easy!
Fairly well – with a
little review, I’ll be
good
Okay. It’s not great,
but it’s not horrible,
either
Not well. I’m kinda
confused
Not at all. I’m
soooooo lost
Ve
1.
67
The 2006 Ig Nobel Prizes
Ornithology
 Nutrition
 Peace


Acoustics

Mathematics

Literature

Medicine


Physics
Chemistry

Biology
For explaining why woodpeckers don’t get headaches
For showing that Kuwaiti dung beetles are finicky eaters
For development of a high-pitched electronic teen-ager
repellent (and, later, ring tones)
For experiments to determine why people don’t like the sound
of fingernails scraping on a blackboard
For calculating the number of photos you must take to ensure
that (almost) nobody in a group will have their eyes closed
For a report entitled, “Consequences of Erudite Vernacular
Utilized Irrespective of Necessity: Problems with Using
Long Words Needlessly.“
For a medical case report titled, “"Termination of Intractable
Hiccups with Digital Rectal Massage“
For studying why dry spaghetti breaks into multiple pieces
For a study entitled, “Ultrasonic Velocity in Cheddar Cheese as
Affected by Temperature,"
For showing that the female malaria mosquito is equally
attracted to the smells of limburger cheese and human feet
68
3 card poker
69
3 Card Poker
 This is the looping HW from a previous fall
 The problem: count how many of each type of hand in a 3
card poker game
 Standard deck of 52 cards (no jokers)
 Four suits: spades, clubs, diamonds, hearts
 13 Faces: Ace, 2 through 10, Jack, Queen, King
 Possible 3-card poker hands
 Pair: two of the cards have the same face value
 Flush: all the cards have the same suit
 Straight: the face values of the cards are in succession
 Three of a kind: all three cards have the same face value
70
 Straight flush: both a flush and a straight
The Card class
 A Card class was provided
 Represents a single card in the deck
 Constructor: Card(int i)
 If i is in the inclusive interval 1 ... 52 then a card is
configured in the following manner
 If 1 <= i <= 13 then the card is a club
 If 14 <= i <= 26 then the card is a diamond
 If 27 <= i <= 39 then the card is a heart
 If 40 <= i <= 52 then the card is a spade
 If i % 13 is 1 then the card is an Ace;
 If i % 13 is 2, then the card is a 2, and so on.
71
Card class methods
 String getFace()
 Returns the face of the card as a String
 String getSuit()
 Returns the suit of the card as a String
 int getValue()
 Returns the value of the card
 boolean equals(Object c)
 Returns whether c is a card that has the same face and
suit as the invoking card
 String toString()
 Returns a text representation of the card. You may find
this method useful during debugging.
72
The Hand class
 A Hand class was (partially) provided
 Represents the three cards the player is holding
 Constuctor: Hand(Card c1, Card c2, Card c3)
 Takes those cards and puts them in sorted order
73
Provided Hand methods
 public Card getLow()
 Gets the low card in the hand
 public Card getMiddle()
 Gets the middle card in the hand
 public Card getHigh()
 Gets the high card in the hand
 public String toString()
 We’ll see the use of the toString() method later
 public boolean isValid()
 Returns if the hand is a valid hand (no two cards that are
the same)
 public boolean isNothing()
 Returns if the hand is not one of the “winning” hands
described before
74
Hand Methods to Implement
 The assignment required the students to implement the other
methods of the Hand class
 We haven’t seen this yet
 The methods returned true if the Hand contained a “winning”
combination of cards
 public boolean isPair()
 public boolean isThree()
 public boolean isStraight()
 public boolean isFlush()
 public boolean isStraightFlush()
75
Class HandEvaluation
 Required nested for loops to count the total number of each
hand
 Note that the code for this part may not appear on the
website
76
Program Demo

HandEvaluation.java
77
How well do you understand 3-card poker?
oo
...
so
oo
c.
..
da
I’m
at
a
ot
N
N
ot
w
el
l.
ll.
I’m
no
It’
s
y.
ki
n
tg
re
at
a
ith
w
ka
O
,b
u.
..
lit
t..
...
st
uf
fi
w
el
l–
Th
is
irl
y
5.
Fa
4.
w
el
l!
3.
20% 20% 20% 20% 20%
ry
2.
Very well! This stuff
is easy!
Fairly well – with a
little review, I’ll be
good
Okay. It’s not great,
but it’s not horrible,
either
Not well. I’m kinda
confused
Not at all. I’m
soooooo lost
Ve
1.
78
All your base are belong to us
Flash animation
 Reference: http://en.wikipedia.org/wiki/All_your_base_are_belong_to_us

79
The Halting Problem
81
What’s wrong with this program?
public class LoopsForever {
public static void main (String args[]) {
while ( true ) {
System.out.println ();
}
}
}
 Given a more complicated program, how do we tell if it gets
stuck in an infinite loop?
 Such as when an application “hangs”?
82
83
The Halting problem
 Given a Java program P, and input I
 Let P be a filename for a program file on a disk
somewhere
 Let I be a filename for a file that contains all the input the
program takes in
 Will the program P with input I ever terminate?
 Meaning will program P with input I loop forever or halt?
 Can a computer program determine this?
 Can a human?
 First shown by Alan Turing in 1936
 Before digital computers existed!
 (I’m ignoring which way he showed it for now)
84
A few notes
 To “solve” the halting problem means we have a method
Oracle.CheckHalt (String P, String I)
 Let Oracle be a class that can give lots of (truthful)
answers
 Oracle.PredictFuture(),
Oracle.GetNextLotteryNumbers(), etc.
 P is the (filename of the) program we are checking for
halting
 I is the (filename of the) input to that program
 And it will return “loops forever” or “halts”
 As a boolean: true means “loops forever”, false means
“halts”
 Note it must work for any (Java) program, not just some
programs
 Or simple programs
85
Take your best guess – do you think it’s
possible to solve the halting problem?
o
nd
e
rs
ta
n
d
w
h.
.
N
’t
u
on
Id
3.
33% 33% 33%
s
2.
Yes
No
I don’t understand
what the halting
problem is
Ye
1.
86
Can a human determine if a program halts?
 Given a program of 10 lines or less, can a human determine if
it halts?
 Assuming no tricks – the program is completely
understandable
 And assuming the computer works properly, of course
 And we ignore the fact that an int will max out at 4 billion
 As there are ways we can get around this…
 For the sample programs on the next page:
 Assume that the code is in a proper main() method in a
proper class
 Assume “…print” stands for “System.out.print”
 Likewise for “…println”
87
Halting problem examples: will they halt?

First sample program:

while (true)
...println (“hello world”);
System.exit();
...println (“Alan Turing”);
...println (“was a genius”);
System.exit();

Second sample program:
for (int n = 0; n < 10; n++)
...println (n);
System.exit();
Third sample program

Fourth sample program:
int x = 10;
while ( x > 0 ) {
...println (“hello world”);
x = x + 1;
}
System.exit();
88
Take your best guess – do you think it’s
possible to solve the halting problem?
o
nd
e
rs
ta
n
d
w
h.
.
N
’t
u
on
Id
3.
33% 33% 33%
s
2.
Yes
No
I don’t understand
what the halting
problem is
Ye
1.
89
Perfect numbers
 Numbers whose divisors (not including the number) add
up to the number
 6=1+2+3
 28 = 1 + 2 + 4 + 7 + 14
 The list of the first 10 perfect numbers:
6, 28, 496, 8128, 33550336, 8589869056,
137438691328, 2305843008139952128,
2658455991569831744654692615953842176,
1915619426082361072947933780843036381309973215
48169216
 The last one was 54 digits!
 All known perfect numbers are even; it’s an open (i.e.
unsolved) problem if odd perfect numbers exist
 Sequence A000396 in OEIS
90
Odd perfect number search
 Will this program ever halt?
int n = 1;
// arbitrary-precision integer
while (true) {
int sumOfFactors = 0;
for ( int factor = 1; factor < n; factor++ )
if ( n % factor == 0 ) // factor is a factor of n
sumOfFactors = sumOfFactors + factor;
if (sumOfFactors == n) then
break;
n = n + 2;
}
System.out.exit();
 Adapted from http://en.wikipedia.org/wiki/Halting_problem
91
Take your best guess – do you think it’s
possible to solve the halting problem?
o
nd
e
rs
ta
n
d
w
h.
.
N
’t
u
on
Id
3.
33% 33% 33%
s
2.
Yes
No
I don’t understand
what the halting
problem is
Ye
1.
92
Where does that leave us?
 If a human can’t figure out how to do the halting problem, we
can’t make a computer do it for us
 It turns out that it is impossible to write such a CheckHalt()
method
 But how to prove this?
93
CheckHalt()’s non-existence
 Consider a program P with input I
 Suppose that a method Oracle.CheckHalt(P,I) exists
 Tests if P(I) will either “loop forever” or “halt”
 A program is a series of bits
 And thus can be considered data as well
 Thus, we can call CheckHalt(P,P)
 It’s using the bytes of program P as the input to
program P
94
CheckHalt()’s non-existence
 Consider a new program:
public class Test {
public static void main (String args[]) {
if ( Oracle.CheckHalt(“Test.java”, “Test.java”) )
// if Test.java loops forever
System.exit();
// then halt
else
// else if Test.java halts
while (true) { }
// then loop forever
}
}
 Do we agree that class Test is a valid program?
95
CheckHalt()’s non-existence

A (somewhat condensed)
version of class Test:
public class Test {
… main … (String args[]) {

Two possibilities:

Either class Test halts…
 Then CheckHalt(Test,Test)
returns
true
(“loops
forever”)…
 Which means that class
Test loops forever
 Contradiction!

Or class Test loops forever…
 Then CheckHalt(Test,Test)
returns false (“halts”)…
 Which means that class
Test halts
96
 Contradiction!
if ( Oracle.CheckHalt
(“Test.java”,
“Test.java”) )
else
}
}
System.exit();
while (true) { }
How well do you understand
the halting problem?
oo
...
so
oo
c.
..
da
I’m
at
a
ot
N
N
ot
w
el
l.
ll.
I’m
no
It’
s
y.
ki
n
tg
re
at
a
ith
w
ka
O
,b
u.
..
lit
t..
...
st
uf
fi
w
el
l–
Th
is
irl
y
5.
Fa
4.
w
el
l!
3.
20% 20% 20% 20% 20%
ry
2.
Very well! This stuff
is easy!
Fairly well – with a
little review, I’ll be
good
Okay. It’s not great,
but it’s not horrible,
either
Not well. I’m kinda
confused
Not at all. I’m
soooooo lost
Ve
1.
97
Why do we care about the halting problem?
 It was the first algorithm that was shown to not be able to
exist by a computer
 You can prove something exists by showing an example (a
correct program)
 But it’s much harder to prove that a program can never
exist
 First shown by Alan Turing in 1936
 Before digital computers existed!
98
New 2005 demotivatiors!
99
Not going over any more
slides in this slide set
100
Triangle counting
101
The programming assignment
 This was the looping HW from two springs ago
 List all the possible triangles from (1,1,1) to (n,n,n)
 Where n is an inputted number
 In particular, list their triangle type
 Types are: equilateral, isosceles, right, and scalene
102
Sample execution
Enter n: 5
(1,1,1)
(1,2,2)
(1,3,3)
(1,4,4)
(1,5,5)
(2,2,2)
(2,2,3)
(2,3,3)
(2,3,4)
(2,4,4)
(2,4,5)
isosceles equilateral
isosceles
isosceles
isosceles
isosceles
isosceles equilateral
isosceles
isosceles
scalene
isosceles
scalene
(2,5,5)
(3,3,3)
(3,3,4)
(3,3,5)
(3,4,4)
(3,4,5)
(3,5,5)
(4,4,4)
(4,4,5)
(4,5,5)
(5,5,5)
isosceles
isosceles equilateral
isosceles
isosceles
isosceles
right scalene
isosceles
isosceles equilateral
isosceles
isosceles
isosceles equilateral
103
Program Demo

TriangleDemo.java
104
The Triangle class
 That semester we went over classes by this homework
 So they had to finish the class
 We will be seeing class creation after spring break
 Methods in the class:
 public Triangle()
 public Triangle (int x, int y, int z)
 public boolean isTriangle()
 public boolean isRight()
 public boolean isIsosceles()
 public boolean isScalene()
 public boolean isEquilateral()
 public String toString()
105
The TriangleDemo class

Contained a main() method that tested all the triangles

Steps required:
 Check if the sides are in sorted order (i.e. x < y < z)
 If not, then no output should be provided for that collection
of side lengths
 Create a new Triangle object using the current side lengths
 Check if it is a valid triangle
 If it is not, then no output should be provided for that
collection of side lengths
 Otherwise, indicate which properties the triangle possesses
 Some side length values will correspond to more than 1
triangle
 e.g., (3, 3, 3) is both isosceles and equilateral
 Thus, we can’t assume that once a property is present, the
106
others are not.
Look at that them there code…

TriangleDemo.java
107
How well do you understand triangle counting?
oo
...
so
oo
c.
..
da
I’m
at
a
ot
N
N
ot
w
el
l.
ll.
I’m
no
It’
s
y.
ki
n
tg
re
at
a
ith
w
ka
O
,b
u.
..
lit
t..
...
st
uf
fi
w
el
l–
Th
is
irl
y
5.
Fa
4.
w
el
l!
3.
20% 20% 20% 20% 20%
ry
2.
Very well! This stuff
is easy!
Fairly well – with a
little review, I’ll be
good
Okay. It’s not great,
but it’s not horrible,
either
Not well. I’m kinda
confused
Not at all. I’m
soooooo lost
Ve
1.
108
Fibonacci numbers
109
Fibonacci sequence
 Sequences can be neither geometric or arithmetic
 Fn = Fn-1 + Fn-2, where the first two terms are 1
 Alternative, F(n) = F(n-1) + F(n-2)
 Each term is the sum of the previous two terms
 Sequence: { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … }
 This is the Fibonacci sequence
 Full formula:

1  5   1  5 
F ( n) 
n
5  2n
n
110
Fibonacci sequence in nature
13
8
5
3
2
1
111
Reproducing rabbits
 You have one pair of rabbits on an island
 The rabbits repeat the following:
 Get pregnant one month
 Give birth (to another pair) the next month
 This process repeats indefinitely (no deaths)
 Rabbits get pregnant the month they are born
 How many rabbits are there after 10 months?
112
Reproducing rabbits
 First month: 1 pair
 The original pair
 Second month: 1 pair
 The original (and now pregnant) pair
 Third month: 2 pairs
 The child pair (which is pregnant) and the parent pair
(recovering)
 Fourth month: 3 pairs
 “Grandchildren”: Children from the baby pair (now
pregnant)
 Child pair (recovering)
 Parent pair (pregnant)
 Fifth month: 5 pairs
 Both the grandchildren and the parents reproduced
 3 pairs are pregnant (child and the two new born rabbits)
113
Reproducing rabbits
 Sixth month: 8 pairs
 All 3 new rabbit pairs are pregnant, as well
pregnant in the last month (2)
 Seventh month: 13 pairs
 All 5 new rabbit pairs are pregnant, as well
pregnant in the last month (3)
 Eighth month: 21 pairs
 All 8 new rabbit pairs are pregnant, as well
pregnant in the last month (5)
 Ninth month: 34 pairs
 All 13 new rabbit pairs are pregnant, as well
pregnant in the last month (8)
 Tenth month: 55 pairs
 All 21 new rabbit pairs are pregnant, as well
pregnant in the last month (13)
as those not
as those not
as those not
as those not
as those not
114
Reproducing rabbits
 Note the sequence:
{ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … }
 The Fibonacci sequence again
115
Fibonacci sequence
 Another application:

Fibonacci references from http://en.wikipedia.org/wiki/Fibonacci_sequence
116
Fibonacci sequence

As the terms increase,
approaches 1.618
the
ratio
between
successive
terms
F (n  1)
5 1
 
 1.618933989
n  F ( n)
2
lim

This is called the “golden ratio”
 Ratio of human leg length to arm length
 Ratio of successive layers in a conch shell

Reference: http://en.wikipedia.org/wiki/Golden_ratio
117
The Golden Ratio
118
119
Number counting
120
The programming assignment
 This was the looping HW from last fall
 Get an integer i from the user
 The homework had four parts
 Print all the Fibonacci numbers up to i
 Print all the powers of 2 up to i
 Print all the prime numbers up to i
 Time the previous three parts of the code
121
Sample execution
Input an integer i: 10
The 10th Fibonacci number is 55
Computation took 1 ms
2 3 5 7 11 13 17 19 23 29
The 10th prime is 29
Computation took 0 ms
The 10th power of 2 is 1024
Computation took 6 ms
2 4 8 16 32 64 128 256 512 1024
BigInteger: The 10th power of 2 is 1024
Computation took 2 ms
122
Background: Prime numbers
 Remember that a prime number is a number that is ONLY
divisible by itself and 1
 Note that 1 is not a prime number!
 Thus, 2 is the first prime number
 The first 10 prime numbers: 2 3 5 7 11 13 17 19 23 29
 The easiest way to determine prime numbers is with nested
loops
123
How to time your code
 Is actually pretty easy:
long start = System.currentTimeMillis();
// do the computation
long stop = System.currentTimeMillis();
long timeTakenMS = stop-start;
 This is in milliseconds, so to do the number of actual
seconds:
double timeTakenSec = timeTakenMS / 1000.0;
124
Program Demo

NumberGames.java

Note what happens when you enter 100


With the Fibonacci numbers
With the powers of 2
125
BigIntegers
 An int can only go up to 2^31 or about 2*109
 A long can only go up to 2^63, or about 9*1018
 What if we want to go higher?
 2100 = 1267650600228229401496703205376
 To do this, we can use the BigInteger class
 It can represent integers of any size
 This is called “arbitrary precision”
 Not surprisingly, it’s much slower than using ints and
longs
 The Fibonacci number part didn’t use BigIntegers
 That’s why we got -980107325 for the 100th term
 It “flowed over” the limit for ints – called “overflow”
126
BigInteger usage
 BigIntegers are in the java.math library
 import java.math.*;
 To get nn:
BigInteger bigN = new BigInteger (String.valueOf(n));
BigInteger biggie = new BigInteger (String.valueOf(1));
for ( int i = 0; i < n; i++ )
biggie = biggie.multiply (bigN);
System.out.println (biggie);
127
Look at that them there code…

NumberGames.java
128