Recurrence 1
Download
Report
Transcript Recurrence 1
Recurrence 1
C N C N 1 N
for N 2 , C 1 1,
C N C N 2 ( N 1) N
C N C N 3 ( N 2 ) ( N 1) N
….
C N C 1 2 ... ( N 2 ) ( N 1) N
C N 1 2 ... ( N 2 ) ( N 1) N
N ( N 1)
CN
2
2
Page 1
Adapted after
Dr. Menezes
CN (N )
Recurrence 2
CN CN /2 1
N
2
is an integer
C 2 n C 2 n 1 1
C 2 n C 2 n2 2
C 2 n C 2 n 3 3
……
C 2n C 20 n
Page 1
Adapted after
Dr. Menezes
for N 2 , C 1 1,
C 2n n 1
C N (log N )
division.
Let N 2
n
Understanding Recurrences
But where do these recurrences come from?
How can we derive one from a real recursive problem?
Let's collectively think about a problem.
Try first to come up with any algorithm (brute-force)
Then try to improve it and possibly define a recursive solution for it.
After we have a recursive solution we'll derive the recurrence for the algorithm
What is the problem?
Pancake Flipping
This problem has been posed by Harry Dweighter on American Mathematical Monthly,
1975
Page 1
Adapted after
Dr. Menezes
Flipping Pancakes
5
4
1
6
3
2
H o w d o w e p il e t h e s e p a n c a k e s in t h e c o r r e c t o r d e r ?
OR
H o w m a n y f l ip s a r e n e c e s s a r y ( in t h e w o r s t c a s e )
to o r g a n i z e t h e p a n c a k e s
s o t h a t t h e la r g e s t is o n t h e b o t to m ?
Page 1
Adapted after
Dr. Menezes
Two-Flips method
(aka Bringing to the top method)
The problem above can be solved by doing the following
Bring the largest pancake to the top of the pile with one flip
With another flip place the largest pancake at the bottom of the pile
Bring the second largest pancake to the top of the pile with one flip
With another flip place the second largest pancake at the second position from the
bottom of the pile ... and so on.
The problem above is intrinsicaly recursive and can be stated as:
If the pile has size (n) == 1 then stop
Otherwise, perform a two-flip operation on the nth pancake
Solve the flip problem for (n-1) pancakes
Recurrence relation for this problem is: T(n) = T(n-1) + 2
The worst case number of raised pancake is T(n) = T(n-1) + 2n-1
Page 1
Adapted after
Dr. Menezes
Recurrence 3
CN CN /2 N
for N 2 , C 1 0 ,
first remember that:
CN CN /4
N
2
N
C N C N /8
N
4
CN N
N
2
C N N 1
CN N
Page 1
Adapted after
Dr. Menezes
1
2
1 0
2
N
2
N
4
1
4
a ar ar ar ... ar
2
3
n
N
1
8
N
8
...
...
1
N
N
N
12 1 12 2 12 3 ... 12 n
C N 2N (N )
a
1 r
(1 r
n 1
)
Recurrence 4
C N 2C N / 2 N
N
2
is an integer
C 2 n 2 C 2 n 1 2
C 2n
2
n
C 2n
2
C 2n
2
n
n 1
C 2 n 3
2
……
2
n
C 2 n 1
n2
1
11
n
C 2n n 2
Page 1
Adapted after
Dr. Menezes
n
n
C N ( N log N )
for N 2 , C 1 0 ,
division.
Let N 2
n
Data Structures
A data structure is the building block of programming
It defines how data is organized (and consequently) how data is allocated in a
computer memory
The importance of data structures for algorithm efficiency cannot be
overemphasized.
The efficiency of most algorithms is directly linked to the data structure choice
Some algorithms are basically a data structure definition (plus the operations
associated with the structure)
For the same amout of data, different data structures can take more or less space in
the computer memory
Page 1
Adapted after
Dr. Menezes
Abstract Data Types (ADT)
A formal specification defines a system independently of implementation
by describing its internal state as Abstract Data Types (objects),
characterized only by the operations allowed on them.
There are 2 types of specifications:
the algebraic specifications (OBJ) – leading to an algebraic structure (an algebra)
a data set
a set of operations (functions)
a set of properties (axioms) characterizing the operations
the constructive approach (VDM – Vienna Development Method)
explicit specification of operation (e.g. using the set theory)
Page 1
Adapted after
Dr. Menezes
Abstract Data Types (ADT)
Algebraic specifications follow the pattern:
obj <name object>
obj
{important sub-objects, objects parameters of functions…}
mode
{complete specification of this data type – e.g. with parameters for templates}
funct
{specify functions associated with the object}
vars
{specify universally quantified variables used in the following equations, e.g. “forall bool x”}
eqns
{specify axioms associated with the object}
jbo
Page 1
Adapted after
Dr. Menezes
Data Structures
We mentioned above the operations associated with the structure. What
are these?
A data structure is not passive, it consists of data and operations to manipulate the
data
They are implementation of (ADTs)
Page 1
Adapted after
Dr. Menezes
Elementary Data Structures
Elementary Data Structures
Linear
Nonlinear
Sequential
Access
Direct Access
Page 1
Adapted after
Dr. Menezes
Set
Homogeneous
Components
Heterogeneous
Components
General
LIFO
FIFO
Array
Record
List
Stack
Queue
Linear vs. Nonlinear
For a structure to be linear all of the above has to be true
There is a unique first element
There is a unique last element
Every component has a unique predecessor (except the first)
Every component has a unique successor (except the last)
If one or more of the above is not true, the structure is nonlinear
Page 1
Adapted after
Dr. Menezes
Direct vs. Sequential Access
In any linear data structure we have two methods of access the stored data
Sequential structures are such that we can only access the Nth element we have to
accessed all element preceding N.
This means that all elements from 1 to N-1 will have to be accessed first.
You can see this as trying to access a song recorded in a cassette tape
Direct access structures are such that any element of the structure can be accessed in
directly.
There is no need to access any other object besides the element required.
Rather than a cassette tape, think CD player.
Can we say that one is better than another?
Page 1
Adapted after
Dr. Menezes
Arrays
One of the most common types of data structures
Normally pre-defined in most programming languages
Has the advantages:
Direct access to elements
But also disadvantages:
Fixed size
Homogeneous elements
Normally implemented by using contiguous allocation of memory cells
This is not however required in the ADT definition of an array.
The array implementation may give the impression of contiguousness.
Page 1
Adapted after
Dr. Menezes
Arrays as ADTs
Domain
A collection of fixed number of components of the same type
A set of indexes used to access the data stored in the array.
There is a one-to-one relation between index and objects stored.
Operations
valueAt(i): Index i is used to access the value stored in the corresponding position of
the array
Most languages use the [ i ] as the index of an array
store(i,v): Stores the value v into the array position i
Most languages use the = operator
Page 1
Adapted after
Dr. Menezes
Sieve of Eratosthenes
(Prime Testing)
public class Sieve {
public static void main (String args[]) {
int n = Integer.parseInt(args[0]);
boolean numbers[] = new boolean[n+1];
for (int i = 2; i <= n; i++) {
numbers[i] = true;
}
for (int i = 2; i <= n; i++) {
if (numbers[i]) {
for (int j = i; j*i <= n; j++) {
if ((j*i) <= n) { // takes care of overflow in j*i
numbers[j*i] = false;
}
}
}
}
for (int i = 2; i <= n; i++) {
if (numbers[i]) {
System.out.println(i);
}
}
}
}
Page 1
Adapted after
Dr. Menezes
Coin Flipping Simulation
(simulation of Bernoulli trials)
public class CoinFlippingSimulation {
private static boolean heads() {
return (Math.random() < 0.5);
}
public static void main (String args[]) {
int cnt = 0, j;
int n = Integer.parseInt(args[0]);
int m = Integer.parseInt(args[1]);
int[] result = new int[n+1];
for (int i = 0; i < m; i++) {
cnt = 0;
for (j = 0; j < n; j++) {
if (heads()) cnt++;
}
result[cnt]++;
}
for (j = 0; j <= n; j++) {
if (result[j] == 0) {
System.out.print(".");
}
for (int i = 0; i < result[j]; i+=10) {
System.out.print("*");
}
System.out.println();
}
}
}
Page 1
Adapted after
Dr. Menezes
Reading Work
Required
Chapter 2: Sections 2.1 to 2.5
Highly recommended
Chapter 2: Sections 2.6 to the end of the chapter
Page 1
Adapted after
Dr. Menezes
Bibliography
(used to produce these slides)
[Sedgewick 2003]. Algorithms in Java. Parts 1-4.
[Cormen et al]. Introduction to Algorithms.
Page 1
Adapted after
Dr. Menezes