Computer Science
15-111 (Sections A & B), Spring 2007
Class Notes: 22-Jan-2007
Course web site update:
Schedule, HW/EC, Resources (submission, other 15-111’s)
Later today and tomorrow:
hw3, practice quiz (?), hw2 solutions
Extended Office Hours (if needed) and Review Session (ditto).
Reading:
Ch4: Methods + Recursion
Ch5: Arrays and
Containers
String, StringBuffer,
StringBuilder (online API)
Quiz: quiz1 on Chapters 1-3 and App A.1, B.1, and B.2, on Wed
24-Jan or Thu 25-Jan.
Topic Outline:
1. Static Method Invocation
a. Static (class) vs non-static
(member) methods
b. Static (class) methods cannot call
non-static (member) methods!
c. Static (class) methods cannot access
non-static (member) variables
d. public static void main(String[]
args) { … }
e. Foo.bar() vs bar()
// no class == this class. Don’t
do this for statics!
2. Variable scope
class
ScopingExample {
private
static int x = 9, y = 9;
private static void foo(int y) { x =
4; y = 5; }
public
static void main(String[] args) {
System.out.printf("%d,%d\n",x,y);
// prints 9,9
for
(int x=0; x<1; x++)
System.out.printf("%d,%d\n",x,y);
// prints 0,9
System.out.printf("%d,%d\n",x,y);
// prints 9,9
int
y = 0;
System.out.printf("%d,%d\n",x,y); //
prints 9,0
foo(x);
System.out.printf("%d,%d\n",x,y); //
prints 4,0
}
}
3. Math.random()
a. double in range [a,b): a + (b – a)*Math.random()
b.
int
in range [a,b]: (int)(a + ((b + 1) –
a)*Math.random())
class RandomExample {
private
static int n = 7, a = 2, b = 5;
private static
int[] counts = new int[n];
public
static void main(String[] args) {
for (int
i=0; i<10000; i++) {
//
index in [a,b]
int
index = (int)(a + ((b + 1) - a)*Math.random());
++counts[index];
}
System.out.println(java.util.Arrays.toString(counts));
}
}
4. Invocation and Call-by-Value
a. Failed swap example (Section 4.8)
b. But:
Objects, including arrays, are references,
so they do change!
5. Top-Down Design, Stubs, and Unit
Testing
6. Software Life Cycle
a. Requirements analysis / definition
b. Design
c. Implementation
d. Testing
e. Maintenance
7. Recursion
a. Recursion: when a method calls itself (directly or
indirectly)
b. Base Case and Recursive Case
c. Iteration is often faster, sometimes
less clear (counterexample: mazes, DFS)
d. Example
class RecursionExample {
public static int fib(int n) {
if (n <
2)
// base case
return 1;
else
return fib(n-1) + fib(n-2);
}
public
static int iterativeFib(int n) {
int fib0 = 1, fib1 = 1;
while (n-- > 0) {
int fib2 = fib0 + fib1;
fib0 = fib1;
fib1 = fib2;
}
return fib0;
}
public
static void main(String[] args) {
for (int i=0; i<42; i++)
System.out.printf("%d, %d, %d\n",
i,fib(i),iterativeFib(i));
long time0, time1;
time0 = System.currentTimeMillis();
fib(42); // 4.5sec
time1 = System.currentTimeMillis();
System.out.println(time1 - time0);
time0 = System.currentTimeMillis();
iterativeFib(42); // 0.0sec!
time1 = System.currentTimeMillis();
System.out.println(time1 - time0);
}
}
8. Method overloading
a. Overloading: Same name, different signature (name,
parameter # and types)
class OverloadExample {
public static int foo(int i)
{ return i+10; }
public
static double foo(double d) { return d/2; }
public
static void main(String[] args) {
System.out.println(foo(10 )); // prints 20
System.out.println(foo(10.0)); // prints 5.0
}
}
b. Cannot only differ by return type
class IllegalOverloadExample {
public static int foo(int i) { return i+10; }
public
static double foo(int i) { return i+1.5; }
public
static void main(String[] args) {
System.out.println(foo(10)); // which foo
would this call?
}
}
c. Can still be ambiguous
class AmbiguousOverloadExample {
public static int foo(int x, float y) {
}
public
static int foo(float x, int y) { }
public
static void main(String[] args) {
int x = 0, y = 0;
foo(x,y); // ambiguous! won't compile!
}
}
d. But this is not ambiguous: narrowest widening conversion wins!
class NarrowestOverloadExample {
public static float foo(float f)
{ return f+10; }
public
static double foo(double d) { return d/2; }
public
static void main(String[] args) {
System.out.println(foo(10)); // prints 20.0
System.out.println(foo(10.0)); // prints 5.0
}
}
9. Arrays
class ArrayPrintingExample {
private
static int[] primes = {2, 3, 5, 7, 11};
public
static void main(String[] args) {
System.out.println("Printing
element-by-element:");
for
(int i=0; i<primes.length; i++)
System.out.printf("%d
",primes[i]);
System.out.println("\nAgain,
with the new for-in loop:");
for
(int prime : primes) System.out.printf("%d ",prime);
System.out.println("\nUsing
Arrays.toString:");
System.out.println(java.util.Arrays.toString(primes));
}
}
a. For Iterator: for ( Type Identifier : Iterable Expression
) statement
i.
Convenient
– no index!
ii.
Only
simple indexing (eg, cannot visit only odd elements)
iii.
Cannot
mutate elements (eg, ++array[3])
b. Arrays as Methods
class ArrayParameterExample {
private static int[] a = {3, 2, 1}, b =
{5, 4, 3};
private
static void foo(int[] x) { x[0] = b[0]; }
private
static void bar(int[] x) { x = b; } // NO EFFECT!
public
static void main(String[] args) {
System.out.println(Arrays.toString(a)); // prints [3, 2, 1]
foo(a);
System.out.println(Arrays.toString(a)); // prints [5, 2, 1]
bar(a);
System.out.println(Arrays.toString(a)); // prints [5, 2, 1]
}
}
c. Array Assignment
i.
Copies
reference, not array; copies are ==, clons only Array.equals:
class ArrayCopyExample {
public static void main(String[] args) {
int[] a = {
1, 2, 3}, b = {1, 2, 3}, c = a;
System.out.printf("%b\n",(a==b));
// false (a != b)
System.out.printf("%b\n",(a==c));
// true (a == c)
System.out.printf("%b\n",(b==c));
// false (b != c)
System.out.printf("%b\n",(Arrays.equals(a,b)));
// true
System.out.printf("%b\n",(Arrays.equals(a,c)));
// true
System.out.printf("%b\n",(Arrays.equals(b,c)));
// true
a[0] = 99;
System.out.println(c[0]);
// prints 99
}
}
10. Two Dimensional Arrays
class
TwoDimensionalArrayExample {
public static void main(String[] args) {
int[][]
a = { { 1, 2 }, {3}, {4, 5, 6} };
for
(int row=0; row<a.length; row++) {
System.out.printf("row
%d: ",row);
for
(int col=0; col<a[row].length; col++)
System.out.printf("%d
",a[row][col]);
System.out.println();
}
int[] row2 = a[2];
System.out.printf("row2:
%s\n",Arrays.toString(row2));
}
}
11. Type and Array (Section 5.9)
a. Array of booleans: Sieve of Eratosthenes
b. Array of chars: Line buffer
c. Array of ChessPieces, TetrisPieces,
Students, etc, etc…