Transcript pptx

Review Session
CS2110 Prelim #1
Java Basics
Primitive types vs classes
● Variabledeclarations:
o int i = 5;
o Animal a = new Animal(“Bob”);
● How does “==” behave?
a
Animal@0x36
i
5
Animal@0x36
name
“Bob”
Java Basics
Default values
● What value does a field contain when it is declared but not
instantiated?
o Animal a;
//null
o Object ob; //null
//0
o int i;
//false
o boolean b; //’\0’ (null byte)
o char c;
//0.0
o double d;
Java Basics
Wrapper Classes (Boxing)
class Character contains useful methods
● Examples of useful static Character methods:
o Character.isDigit(c)
o IntCharacter.isLetter(c)
● Autoboxing –should be called autowrapping!
o Integer x = 100;
o int y = x;
Java Basics
String literals
String instantiation:
● Constructor: String s = new String(“dog”);
● Literal: String s2 = “dog”;
● Roughly equivalent, but literal is preferred
s
String@0x62
s2
String@0x28
String@0x62
String@0x28
“dog”
“dog”
Java Basics
Strings are immutable
Once a String is created, it cannot be changed
● Methods such as toLowerCase and substring return new
Strings, leaving the original one untouched
● In order to “modify” Strings, you instead construct a new String
and then reassign it to the original variable:
o String name = “Gries”;
o name = name + “, “;
o name = name + “David”;
Java Basics
String catenation
Operator + operator is called catenation, or concatenation
● If one operand is a String and the other isn’t, the other is
converted to a String
● Important case: Use “” + exp to convert exp to a String.
● Evaluates left to right. Common mistake:
o System.out.println(“sum: “ + 5 + 6);
 Prints “sum: 56”
o System.out.println(“sum: “ + (5 + 6));
 Prints “sum: 11”
Java Basics
Other String info
● Always use equals to compare Strings:
o str1.equals(str2)
● Very useful methods:
o length, substring (overloaded), indexOf, charAt
● Useful methods:
o lastIndexOf, contains, compareTo
2D Arrays
1D Array Review
Animal[] pets = new Animal[3];
pets.length is 3
pets[0] = new Animal();
pets[0].walk();
pets null
Array@0x10
0
null
1
null
2
null
Why is the following illegal?
pets[1] = new Object();
Array@0x10
2D Arrays
Java arrays
Java arrays do not change size!
b A@0xab A@0x12
bBig A@0x12
A@0xab
0 “Cornell”
1 “Ithaca”
String[] b = {“Cornell”, “Ithaca”};
String[] bBig = Arrays.copyOf(b, 4);
b = bBig;
A@0x12
0 “Cornell”
1 “Ithaca”
2
3
2D Arrays
2D arrays: An array of 1D arrays.
Java only has 1D arrays, whose elements can also be arrays.
int[][] b = new int[2][3];
This array has 2 int[] arrays of length 3 each.
0
1
2
b
0
1
0
1
2
0
0
0
0
0
0
2D Arrays
2D arrays: An array of 1D arrays.
How many rows in b?
How many columns in row 0?
How many columns in row 1?
b.length
b[0].length
b[1].length
0
1
2
b
0
1
0
1
2
0
0
0
0
0
0
2D Arrays
2D arrays: An array of 1D arrays.
int[][] b = new int[2][];
The elements of b are of type int[].
b
nul
0 l
nul
1 l
2D Arrays
2D arrays: An array of 1D arrays.
int[][] b = new int[2][];
b[0] =
new int[] {0,4,1,3,9,3};
b[1] =
new int[] {1110,2110,3110};
b is called a ragged array
b
0
1
0
1
2
1110
2110
3110
0
1
2
3
4
5
0
4
1
3
9
3
Exceptions
The superclass of exceptions: Throwable
class Throwable:
● Superclass of Error and
Exception
● Does the “crashing”
● Contains the constructors
and methods
● Throwable()
● Throwable(String)
class Error:
● A very serious problem and
should not be handled
Example: StackOverflowError
class Exception:
● Reasonable application might
want to crash or handle the
Exception in some way
Exceptions
A Throwable instance: ArithmeticException
ArithmeticException@x2
Throwable
detailMessage
Exception
RuntimeException
ArithmeticException
“/ by zero”
There are so many exceptions
we need to organize them.
Throwable
Exception
RuntimeException
ArithmeticException
Error
Exceptions
Bubbling up exceptions
Exceptions will bubble up the call
stack and crash the methods that
called it.
AE
Method call: first();
Console:
Exception in thread “main”
java.lang.ArithmeticException:
at Ex.third(Ex.java:11)
at Ex.second(Ex.java:7)
at Ex.first(Ex.java:3)
AE
AE
1 class Ex {
2
void first() {
3
second();
4
}
5
6
void second() {
7
third();
8
}
9
10
void third() {
11
int c = 5/0;
12
}
13 }
AE = ArithmeticException
Exceptions
1
class Ex {
2
void first() {
3
second();
4
}
void second() {
An exception will bubble up the call 5
try {
stack and crash the methods that 6
7
called it
8
System.out.println(“in”);
… unless it is caught.
9
third();
10
catch will handle any exceptions 11
System.out.println(“out”);
of type Exception (and its
12
} catch (Exception e){
subclasses) that happened in the 13
try block
14
System.out.print(“error”);
Exception Type
15
}
Console:
16
}
in
17
ArithmeticException!
error
18
void third() {
int c = 5/0;
Try-catch blocks
Exceptions
How to write an exception class
/** An instance is an exception */
public class OurException extends Exception {
/** Constructor: an instance with message m*/
public OurException(String m) {
super(m);
}
/** Constructor: an instance with default message */
public OurException() {
this(“Default message!”);
}
}
Abstract Classes
A Little More Geometry!
Shape
x ____
y ____
Square
area()
size ____
Triangle
area()
base____
height ____
Circle
area()
radius ____
Abstract Classes
A Partial Solution:
Add method area to class Shape:
public double area() {
return 0;
}
public double area() {
throw new RuntimeException(“area not
overridden”);
}
Abstract Classes
Problems not solved
1. What is a Shape that isn’t a Circle, Square, Triangle,
etc? What is only a shape, nothing more specific?
a. Shape s = new Shape(...); Should be
disallowed
2. What if a subclass doesn’t override area()?
a. Can’t force the subclass to override it!
b. Incorrect value returned or exception thrown.
Abstract Classes
Solution: Abstract classes
Abstract class
Can’t be instantiated.
(new Shape() illegal)
public abstract class Shape {
public double area() {
return 0;
}
}
Abstract Classes
Solution: Abstract methods
public abstract class Shape {
● Can have
implemented
methods, too
public abstract double area(); ● Place abstract
method only in
abstract class.
}
Abstract method
Subclass must
override.
● Semicolon
instead of body.
Abstract Classes
Abstract Classes, Abstract Methods
1. Cannot instantiate an object of an abstract class.
(Cannot use new-expression)
1. A subclass must override abstract methods.
(but no multiple inheritance in Java, so…)
Interfaces
Interfaces
public interface Whistler { ● methods are automatically
void whistle();
public and abstract
int MEANING_OF_LIFE= 42;
● fields are automatically
}
public, static, and
final (i.e. constants)
class Human extends Mammal implements Whistler
{
}
Must implement all methods in the
implemented interfaces
Interfaces
Multiple interfaces
public interface Singer { Classes can implement several
void singTo(Human h); interfaces! They must implement
all the methods in those interfaces
}
they implement.
class Human extends Mammal implements Whistler, Singer {
}
Must implement singTo(Human h)
and whistle()
Interfaces
Solution: Interfaces
Interface Whistler offers
promised functionality to
classes Human and Parrot!
Animal
Mammal
Bird
Whistler
Human
Dog
Parrot
Interfaces
Casting
Human h
Object o
Animal a
Mammal m
=
=
=
=
new Human();
(Object) h;
(Animal) h;
(Mammal) h;
Singer s = (Singer) h;
Whistler w = (Whistler) h;
Object
Animal
Whistler
Mammal
All point to the same memory address!
Human
Singer
Interfaces
Casting
Human h
Object o
Animal a
Mammal m
Singer s
Whistler
=
=
=
=
=
w
new Human();
h;
h;
Automatic
h;
up-cast
h;
= h;
Object
Animal
Whistler
Mammal
Forced
down-cast
Human
Singer
Interfaces
Casting up to an interface automatically
class Human … implements Whistler {
void listenTo(Whistler w) {...}
}
Human h = new Human(...);
Human h1 = new Human(...);
h.listenTo(h1);
Parrot p = new Parrot(...);
Whistler
h.listenTo(p);
Arg h1 of the call has type Human. Its value is being stored
in w, which is of type Whistler. Java does an upward cast
automatically. Same thing for p of type Parrot.
Object
Animal
Mammal
Human
Interfaces
Shape implements Comparable<T>
public class Shape implements Comparable<Shape> {
...
/** … */
public int compareTo(Shape s) {
double diff= area() - s.area();
return (diff == 0 ? 0 : (diff < 0 ? -1 : +1));
}
}
Interfaces
Beauty of interfaces
Arrays.sort sorts an array of any class C, as long as C implements
interface Comparable<T> without needing to know any
implementation details of the class.
Classes that implement Comparable:
Boolean
String
Time
Byte
BigDecimal
Timestamp
Double
Integer
BigInteger Calendar
and 100 others
Interfaces
String sorting
Arrays.sort(Object[] b) sorts an array of any class C, as long
as C implements interface Comparable<T>.
String implements Comparable, so you can write
String[] strings= ...; ...
Arrays.sort(strings);
During the sorting, when comparing
elements, a String’s compareTo
function is used
Abstract Classes vs. Interfaces
● Abstract class represents
something
● Sharing common code
between subclasses
Similarities:
● Can’t instantiate
● Must implement abstract methods
● Interface is what something
can do
● A contract to fulfill
● Software Engineering
purpose
Loop Invariants
Four loopy questions
//Precondition
Initialization;
// invariant: P
while ( B ) { S }
2. Does it stop right?
Does P and !B imply
the desired result?
1. Does it start right?
Does initialization make
invariant P true?
3. Does repetend S make
progress toward
termination?
4. Does repetend S
keep invariant P true?
Loop Invariants
Add elements backwards
Precondition
???
b
h
Invariant
b
???
s = sum
h
Postcondition
b
s = sum
Loop Invariants
Add elements backwards
0
int s = 0;
int h = b.length-1;
while (h >= 0) {
s = s + b[h];
h--;
}
INV: b
1.
2.
3.
4.
h
???
s = sum
Does it start right?
Does it stop right?
Does it keep the invariant true?
Does it make progress toward
termination?
Prelim Review
Linear search time
Linear search for v in an array b of length n
0
b
n
???
worst-case time. v is not in b[0..n-1], so linear search has to look
at every element. Takes time proportional to n.
expected (average) case time. If you look at all possibilities where
v could be and average the number of elements linear search has
to look at, you would get close to n/2. Still time proportional to n.
Prelim Review
Binary search time (b[0..n-1] is sorted)
h= -1; t= n;
// invariant: P (below)
while (h < t-1) {
int e= (h+t)/2;
if (b[e] <= v) h= e;
else t= e;
}
// b[0..h] <= v < b[t..n-1]
b[h+1..t-1] starts out with n
elements in it.
Each iteration cuts size of
b[h+1..t-1] in half.
worst-case and expected
case time: log n
0
inv P: b
h
<= v
t
?
n
> v
Prelim Review
Insertion sort of b[0..n-1]
h= 0;
// invariant: P (below)
while (h < n) {
Push b[h] down into
its sorted position
in b[0..h];
h= h+1;
}
Worst-case time for Push: h swaps
Average case time for Push: h/2 swaps
1 + 2 + 3 + … + n-1 = n (n-1) / 2
Worst-case and average case time:
proportional to n^2
0
inv P: b
h
sorted
?
n
Prelim Review
Selection sort of b[0..n-1]
h= 0;
// invariant: P (below)
while (h < n) {
Swap b[h] with min
value in b[h..n-1];
h= h+1;
}
0
inv P: b
h
sorted
?
To find the min value of b[h..n-1] takes
time proportional to n - h.
n + (n-1) + … + 3 + 2 + 1 = n (n-1) / 2
Worst-case and average case time:
proportional to n^2
n
Prelim Review
Quicksort of b[0..n-1]
partition(b, h, k) takes time proportional to
size of b[h..k]
Best-case time: partition makes both sides
equal length
time n to partition
time n to partition
time n to partition
depth: proportional to log n
therefore: time n log n
Prelim Review
Quicksort of b[0..n-1]
/** Sort b[h..k] */
Someone proved that the
void QS(int[] b, int h, int k) {
average or expected time
if (b[h..k] size < 2)
for quicksort is n log n
return;
j= partition(b, h, k);
// b[h..j-1] <= b[j] <= b[j+1..k]
QS(h, j-1);
QS(j+1, k)
}
Prelim Review
Quicksort of b[0..n-1]
partition(b, h, k) takes time proportional to size of b[h..k]
Worst-case time: partition makes one side empty
time n to partition
time n-1 to partition
time n-2 to partition
depth: proportional to n
therefore: time n^2
Prelim Review
What method calls are legal
Animal an; …
an.m(args);
legal ONLY if Java can guarantee that
method m exists. How to guarantee?
m must be declared in Animal or inherited.
Java Summary
● On the “Resources” tab of the course website
● We have selected some useful snippets
● We recommend going over all the slides
Casting among types
(int) 3.2
casts double value 3.2 to an int
any number
type
any number
expression
may be automatic cast wider
narrow
byte short int long float double
must be explicit cast, may truncate
char is a number type:
(int) 'V'
Unicode representation: 86
Page A-9, inside back cover
(char) 86
'V'
48
Declaration of class Circle
Multi-line comment starts with /* ends with */
/** An instance (object) represents a circle */ Precede every class
with a comment
public class Circle {
Put declarations of
fields, methods in class
body: { … }
}
Put class
declaration in
file Circle.java
public: Code everywhere can refer to Circle.
Called access modifier
Page B-5
49
Overloading
Possible to have two or more methods with same name
/** instance represents a rectangle */
public class Rectangle {
private double sideH, sideV; // Horiz, vert side lengths
/** Constr: instance with horiz, vert side lengths sh, sv */
public Rectangle(double sh, double sv) {
sideH= sh; sideV= sv;
}
/** Constructor: square with side length s */
public Rectangle(double s) {
sideH= s; sideV= s;
Lists
}
…
must
}
of parameter types
differ in some way
50
Use of this
this evaluates to the name
of the object in which is appears
Memorize this!
/** Constr: instance with radius radius*/
public Circle(double radius) {
this.radius= radius;
}
Page B-28
51
/** An instance represents a shape at a point in the plane */
public class Shape {
private double x, y; // top-left point of bounding box
/** Constructor: a Shape at point (x1, y1) */
public Shape (double x1, double y1) {
x= x1; y= y1;
}
/** return x-coordinate of bounding box*/
public double getX() {
return x;
}
Class Shape
/** return y-coordinate of bounding box*/
public double getY() {
return y;
}
}
52
Object: superest class of them all
Class doesn’t explicitly extend another one? It automatically
extends class Object. Among other
components, Object contains:
Constructor: public Object() {}
/** return name of object */
public String toString()
c.toString() is “Circle@x1”
/** return value of “this object and ob
are same”, i.e. of this == ob */
public boolean equals(Object ob)
Page C-18
53
Java has 4 kinds of variable
public class Circle {
private double radius;
private static int t;
Field: declared non-static. Is in every object of
class. Default initial val depends on type, e.g. 0
for int
Class (static) var: declared static. Only one
copy of it. Default initial val depends on type,
e.g. 0 for int
public Circle(double r) {
double r1= r;
Parameter: declared in () of method header. Created during call
before exec. of method body, discarded when call completed.
radius= r1;
}
Initial value is value of corresp. arg of call. Scope: body.
Local variable: declared in method body. Created during call before exec. of body,
discarded when call completed. No initial value. Scope: from declaration to end of
54
block.
Basic class Box
public class Box {
private Object object;
parameter T (you choose name)
Written using generic type
public void set(Object ob) {
object = ob;
}
public Object get() {
return object;
} New
… code
Box<Integer> b= new Box<Integer>();
b.set(new Integer(35));
Integer x= b.get();
public class Box<T> {
private T object;
public void set(T ob) {
object = ob;
}
public T get() {
return object;
} …
Replace type Object
everywhere by T 55
Linked Lists
(These slides are from the class lectures and
available on the website as well)
Linked Lists
57
Idea: maintain a list (2, 5, 7) like this:
a1
h a1
a6
v
2
next a6
a8
v
5
next a8
v
7
next null
This is a singly linked list
To save space we write names like a6 instead of N@35abcd00
57
Easy to insert a node in the beginning!
58
h a1
(2, 5, 7)
h a3
a3
v 8
next a1
a1
a6
a8
v 2
next a6
v 5
next a8
v 7
next null
a1
a6
a8
v
2
v
next a6
5
next a8
(8, 2, 5, 7)
v
7
next null
58
Easy to remove a node if you have its predecessor!
59
h a1
a1
a6
a2
a8
v 2
next a6
v 5
next a2
v 8
next a8
v 7
next null
k a6
(2, 5, 8, 7)
a1
h a1
(2, 5, 7)
a6
v
a2
a8
2
v 5
v 8
next a6
next a8
next a8
k a6
v
7
next null
59
Recursion
Sum the digits in a non-negative integer
61
/** return sum of digits in n.
* Precondition: n >= 0 */
public static int sum(int n) {
if (n < 10) return n;
// { n has at least two digits }
// return first digit + sum of rest
return sum(n/10) + n%10 ;
}
E.g. sum(7) = 7
E.g. sum(8703) = sum(870) + 3;
sum calls itself!
Stack Frame
62
A “frame” contains information about a
local variables
method call:
parameters
At runtime, Java maintains a stack that
contains frames for all method calls that are
return info
being executed but have not completed.
Method call: push a frame for call on stack, assign argument
values to parameters, execute method body. Use the frame for
the call to reference local variables, parameters.
End of method call: pop its frame from the stack; if it is a
function, leave the return value on top of stack.