Transcript Quick Overview

CIT 594 Quick Overview
Jan 12, 2012
Pointers and References
Machine addresses
:
Computer memory consists of
one long list of addressable
bytes
A pointer is a data item that
contains an address

3FA71CF6
• A reference is a data item that
contains an address
3FA71CF6
• C has pointers, but Java has
references
• So what’s the difference?
3FA71CF2
3FA71CF3
3FA71CF4
3FA71CF5
3FA71CF6
3FA71CF7
3FA71CF8
3FA71CF9
3FA71CFA
3FA71CFB
3FA71CFC
3FA71CFD
3FA71CFE
3FA71CFF
3FA71D00
3FA71D01
:
C (and C++) vs. Java






In C you can dereference (follow) a pointer
In Java you can dereference (follow) a reference
In C you can assign one pointer variable to another
In Java you can assign one reference variable to another
In C you can determine whether one pointer is larger than, equal to, or
smaller than another pointer
In Java you can determine whether one reference is equal to another reference

In C you can create a pointer to anything
In Java you can have references to objects

In C you can do integer arithmetic on pointers

References

An Abstract Data Type (ADT) has a set of values and a
set of operations on those values


Pointers and references have the same set of values (memory
addresses)
Pointers have more defined operations than references




Pointers are more flexible and more general than references
References are safer than pointers (from error or malicious misuse)
References allow automatic garbage collection (pointers don’t)
A (non-abstract) Data Type also has an implementation


The implementations of pointers and references are similar
Java references carry information about the thing referenced;
in C, it’s up to the compiler to figure out what it can
Data structures


Basically, pointers and references are the same thing; they point
to (refer to) something else in memory
A Data Structure is a description of how data is organized in
memory



Many (not all) data structures are built from objects pointing/referring to
one another
Understanding pointers (references) is fundamental to this course
If this course were taught in C or C++ instead of Java, all the
“nuts and bolts” would be the same



This course is in Java, but it’s not about Java
You need to know how to create your own data structures
I will also teach some Java-specific packages

In real life, it’s stupid to redo work that’s already been done for you
A trivial example

We use a lot of references in Java:

class Person {
String name;
Person spouse;
Person (String n) {
name = n;
}
}
…
Person john = new Person("John");
Person mary = new Person("Mary");
john.spouse = mary;
mary.spouse = john;
"John"
john
name
spouse
"Mary"
mary
name
spouse
A more serious example


A binary tree is a data
structure in which every node
(object) has zero, one, or two
children (references to other
nodes)
Arithmetic expressions can be
represented as binary trees
To evaluate an arithmetic
expression:
If it is a leaf, return its value
Otherwise, evaluate its two
subtrees, and perform the
indicated operation
+
/
12
null
null
7
null
null
4
null
null
A binary tree representing the
arithmetic expression 12/4+7
Binary trees in Java

public class BinaryTree {
public Object value; // the information in this node
private BinaryTree leftChild;
private BinaryTree rightChild;
// Constructors and methods...


}
To make binary trees as useful as possible, we make the value in
a node an Object
As implementers of the BinaryTree class, our job is to make sure
that the structure of the binary tree is always valid

We don’t really care what the user puts in the value field
Size of objects

Objects in Java have, generally speaking, a fixed size



The size of all primitives is known
Objects don’t actually “contain” other objects—they just
have references to other objects, and a reference is 4 bytes
So what about Vectors?



A Vector is like an array, but it gets bigger as you put things
into it
A Vector actually has two “sizes”—its capacity, which is
how many references it can hold, and its size, which is how
many references are in it right now
When you exceed the capacity of a Vector, Java creates a
new Vector for you
The magic of Vectors


Suppose you have two
references to a Vector, and
you use one of them to add
elements to the Vector
What happens if Java decides
to replace this Vector with a
bigger one?
v1
v2
It looks like the second reference is a “dangling pointer,” referring
to nothing
This doesn’t happen! Java protects you from this error
But how?
Vector’s secret trick

A reference to a Vector is
actually a reference to a
reference to a Vector
v1
v2
In this way, the “real” reference has to be changed in only one
place, and all the other, indirect references automatically work
It’s clever, but it isn’t magic
Recursion
Jan 12, 2012
Definitions I


A recursive definition is a definition in which the thing
being defined occurs as part of its own definition
Example:


An atom is a name or a number
A list consists of:
 An open parenthesis, "("
 Zero or more atoms or lists, and
 A close parenthesis, ")"
14
Definitions II


Indirect recursion is when a thing is defined in terms of
other things, but those other things are defined in terms
of the first thing
Example: A list is:




An open parenthesis,
Zero or more Symbolic expressions, and
A close parenthesis
A Symbolic expression is an atom or a list
15
Recursive functions...er, methods

The mathematical definition of factorial is:
factorial(n) is

We can define this in Java as:



1, if n <= 1
n * factorial(n-1) otherwise
long factorial(long n) {
if (n <= 1) return 1;
else return n * factorial(n – 1);
}
This is a recursive function because it calls itself
Recursive functions are completely legal in Java
16
Anatomy of a recursion
Base case: does some work
without making a recursive
call
long factorial(long n) {
if (n <= 1) return 1;
else return n * factorial(n – 1);
}
Extra work to convert the
result of the recursive call
into the result of this call
Recursive case: recurs
with a simpler
parameter
17
The four rules



Do the base cases first
Recur only with simpler cases
Don't modify and use non-local variables



You can modify them or use them, just not both
Remember, parameters count as local variables,
but if a parameter is a reference to an object, only the
reference is local—not the referenced object
Don't look down
18
Do the base cases first



Every recursive function must have some things it can do without
recursion
These are the simple, or base, cases
Test for these cases, and do them first




The important part here is testing before you recur; the actual work can be
done in any order
long factorial(long n) {
if (n > 1) return n * factorial(n – 1);
else return 1;
}
However, it’s usually better style to do the base cases first
This is just writing ordinary, nonrecursive code
19
Recur only with a simpler case

If the problem isn't simple enough to be a base case,
break it into two parts:




A simpler problem of the same kind (for example, a smaller
number, or a shorter list)
Extra work not solved by the simpler problem
Combine the results of the recursion and the extra work
into a complete solution
“Simpler” means “more like a base case”
20
Don’t modify and use non-local variables

Consider the following code fragment:



int n = 10;
...
int factorial() {
if (n <= 1) return 1;
else {
n = n – 1;
return (n + 1) * factorial();
}
}
It is very difficult to determine (without trying it)
whether this method works
The problem is keeping track of the value of n at all the
various levels of the recursion
21
Don't look down




When you write or debug a recursive function, think
about this level only
Wherever there is a recursive call, assume that it works
correctly
If you can get this level correct, you will automatically
get all levels correct
You really can't understand more than one level at a
time, so don’t even try
22
We have small heads*




It's hard enough to understand one level of one function
at a time
It's almost impossible to keep track of many levels of
the same function all at once
But you can understand one level of one function at a
time...
...and that's all you need to understand in order to use
recursion well
*According to Edsger Dijkstra
23
Types of Algorithms
Algorithm classification




Algorithms that use a similar problem-solving approach
can be grouped together
We’ll talk about a classification scheme for algorithms
This classification scheme is neither exhaustive nor
disjoint
The purpose is not to be able to classify an algorithm as
one type or another, but to highlight the various ways in
which a problem can be attacked
25
A short list of categories

Algorithm types we will consider include:








Simple recursive algorithms
Backtracking algorithms
Divide and conquer algorithms
Dynamic programming algorithms
Greedy algorithms
Branch and bound algorithms
Brute force algorithms
Randomized algorithms
26
Analysis of Algorithms
Time and space

To analyze an algorithm means:



developing a formula for predicting how fast an
algorithm is, based on the size of the input (time
complexity), and/or
developing a formula for predicting how much memory
an algorithm requires, based on the size of the input
(space complexity)
Usually time is our biggest concern

Most algorithms require a fixed amount of space
28
What does “size of the input” mean?




If we are searching an array, the “size” of the input
could be the size of the array
If we are merging two arrays, the “size” could be the
sum of the two array sizes
If we are computing the nth Fibonacci number, or the
nth factorial, the “size” is n
We choose the “size” to be a parameter that determines
the actual time (or space) required


It is usually obvious what this parameter is
Sometimes we need two or more parameters
29
Characteristic operations

In computing time complexity, one good approach
is to count characteristic operations



What a “characteristic operation” is depends on the
particular problem
If searching, it might be comparing two values
If sorting an array, it might be:




comparing two values
swapping the contents of two array locations
both of the above
Sometimes we just look at how many times the
innermost loop is executed
30
Exact values

It is sometimes possible, in assembly language, to
compute exact time and space requirements



We know exactly how many bytes and how many cycles
each machine instruction takes
For a problem with a known sequence of steps (factorial,
Fibonacci), we can determine how many instructions of
each type are required
However, often the exact sequence of steps cannot
be known in advance

The steps required to sort an array depend on the actual
numbers in the array (which we do not know in advance)
31
Higher-level languages

In a higher-level language (such as Java), we do not
know how long each operation takes




Which is faster, x < 10 or x <= 9 ?
We don’t know exactly what the compiler does with this
The compiler almost certainly optimizes the test anyway
(replacing the slower version with the faster one)
In a higher-level language we cannot do an exact
analysis


Our timing analyses will use major oversimplifications
Nevertheless, we can get some very useful results
32
Average, best, and worst cases


Usually we would like to find the average time to perform an
algorithm
However,

Sometimes the “average” isn’t well defined

Example: Sorting an “average” array
 Time typically depends on how out of order the array is
How out of order is the “average” unsorted array?
Sometimes finding the average is too difficult



Often we have to be satisfied with finding the worst (longest)
time required


Sometimes this is even what we want (say, for time-critical operations)
The best (fastest) case is seldom of interest
33
Constant time



Constant time means there is some constant k such
that this operation always takes k nanoseconds
A Java statement takes constant time if:
 It does not include a loop
 It does not include calling a method whose time is
unknown or is not a constant
If a statement involves a choice (if or switch)
among operations, each of which takes constant
time, we consider the statement to take constant time

This is consistent with worst-case analysis
34
Linear time

We may not be able to predict to the nanosecond how long a
Java program will take, but do know some things about
timing:


for (i = 0, j = 1; i < n; i++) {
j = j * i;
}
This loop takes time k*n + c, for some constants k and c
k : How long it takes to go through the loop once
(the time for j = j * i, plus loop overhead)
n : The number of times through the loop
(we can use this as the “size” of the problem)
c : The time it takes to initialize the loop
The total time k*n + c is linear in n
35
Constant time is (usually)
better than linear time

Suppose we have two algorithms to solve a task:



Which is better?





Algorithm A takes 5000 time units
Algorithm B takes 100*n time units
Clearly, algorithm B is better if our problem size is small,
that is, if n < 50
Algorithm A is better for larger problems, with n > 50
So B is better on small problems that are quick anyway
But A is better for large problems, where it matters more
We usually care most about very large problems

But not always!
36
What about the constants?


An added constant, f(n)+c, becomes less and less
important as n gets larger
A constant multiplier, k*f(n), does not get less
important, but...




Improving k gives a linear speedup (cutting k in half cuts the
time required in half)
Improving k is usually accomplished by careful code
optimization, not by better algorithms
We aren’t that concerned with only linear speedups!
Bottom line: Forget the constants!
37
Simplifying the formulae

Throwing out the constants is one of two things we
do in analysis of algorithms


By throwing out constants, we simplify 12n2 + 35 to
just n2
Our timing formula is a polynomial, and may have
terms of various orders (constant, linear, quadratic,
cubic, etc.)

We usually discard all but the highest-order term

We simplify n2 + 3n + 5 to just n2
38
Big O notation

When we have a polynomial that describes the time
requirements of an algorithm, we simplify it by:




Throwing out all but the highest-order term
Throwing out all the constants
If an algorithm takes 12n3+4n2+8n+35 time, we
simplify this formula to just n3
We say the algorithm requires O(n3) time


We call this Big O notation
(More accurately, it’s Big , but we’ll talk about that later)
39
Big O for subset algorithm

Recall that, if n is the size of the set, and m is the size of
the (possible) subset:




We go through the loop in subset m times, calling
member each time
We go through the loop in member n times
Hence, the actual running time should be k*(m*n) + c,
for some constants k and c
We say that subset takes O(m*n) time
40
Can we justify Big O notation?

Big O notation is a huge simplification; can we
justify it?



It only makes sense for large problem sizes
For sufficiently large problem sizes, the
highest-order term swamps all the rest!
Consider R = x2 + 3x + 5 as x varies:
x=0
x2 = 0 3x = 0 5 = 5 R = 5
x = 10
x2 = 1003x = 30 5 = 5 R = 135
x = 100
x2 = 10000
3x = 300
x = 1000
x2 = 1000000
3x = 3000
x = 10,000 x2 = 108 3x = 3*104
5=5
x = 100,000 x2 = 1010
3x = 3*105
10,000,300,005
5 = 5 R = 10,305
5 = 5 R = 1,003,005
R = 100,030,005
5=5 R=
41
y = x2 + 3x + 5, for x=1..10
42
y = x2 + 3x + 5, for x=1..20
43
Common time complexities
BETTER







O(1)
O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
constant time
log time
linear time
log linear time
quadratic time
cubic time
exponential time
WORSE
44
The End